歧视!对C++IO的歧视

这道题最后三个点总是超时TAT
用了各种手段优化代码
最后一气之下注释掉所有处理代码,只剩下读入
而且还关了流同步
结果见下
真是去了皮的土豆
测试数据 #0: WrongAnswer, time = 0 ms, mem = 5204 KiB, score = 0
测试数据 #1: WrongAnswer, time = 0 ms, mem = 5204 KiB, score = 0
测试数据 #2: WrongAnswer, time = 4 ms, mem = 5208 KiB, score = 0
测试数据 #3: WrongAnswer, time = 15 ms, mem = 5204 KiB, score = 0
测试数据 #4: WrongAnswer, time = 31 ms, mem = 5208 KiB, score = 0
测试数据 #5: WrongAnswer, time = 15 ms, mem = 5208 KiB, score = 0
测试数据 #6: WrongAnswer, time = 609 ms, mem = 5204 KiB, score = 0
测试数据 #7: TimeLimitExceeded, time = 1015 ms, mem = 5196 KiB, score = 0
测试数据 #8: TimeLimitExceeded, time = 1015 ms, mem = 5200 KiB, score = 0
测试数据 #9: TimeLimitExceeded, time = 1015 ms, mem = 5196 KiB, score = 0
TimeLimitExceeded, time = 3719 ms, mem = 5208 KiB, score = 0
代码
//written by AH-360
#include<iostream>
#define maxn 200001
#define moder 10007
using namespace std;
int n,max_w,sum_w=0,u[maxn]={0},v[maxn]={0},w[maxn]={0};
int first[maxn]={0},second[maxn]={0},sum[maxn]={0};
int main()
{
ios::sync_with_stdio(0);//关闭流同步
cin>>n;
for(int i=1;i<n;++i)cin>>u[i]>>v[i];
for(int i=1;i<=n;++i)cin>>w[i];
/*for(int i=1;i<n;++i)
for(int j=0;j<=1;++j,swap(u[i],v[i]))
{
if(w[v[i]]>first[u[i]])
{
second[u[i]]=first[u[i]];
first[u[i]]=w[v[i]];
}else
if(w[v[i]]>second[u[i]])
second[u[i]]=w[v[i]];
sum_w=(w[v[i]]*sum[u[i]]+sum_w)%moder;
sum[u[i]]=(sum[u[i]]+w[v[i]])%moder;
}
for(int i=1;i<=n;++i)
if(max_w<first[i]*second[i])
max_w=first[i]*second[i];*/
cout<<max_w<<' '<<(2*sum_w)%moder;
}

16 条评论

  • @ 2016-10-21 14:30:11

    实际上这是Vijos的原因,不是C++的STL慢。
    Vijos不开优化,那自然是比不过libc的那一套函数。
    libc都是预编译过的,编译时就已经优化过了。而STL绝大部分都是模板,没有编译过,因此STL的速度全靠编译器来做展开与各种优化。加上Vijos本身机子速度不是很快,导致Vijos上会出现这样的原因。因此不能说是C++ Streams慢。
    这题vector被卡也是一样的原因。

  • @ 2016-10-05 23:56:08

    另外针对LZ提出的往函数里面传引用的问题,引用其实就是阉割了的指针,可以类比理解。
    传引用的常见目的有:
    1. 使函数体内能直接修改函数外给参数赋值的那个变量的值,因为被赋值的参数是它的引用而不是它的拷贝
    2. 对于类(或结构体)整体作为参数来说,传引用比传值更快,因为传值要把类中每一个元素挨个拷贝一次。

    但是并不是所有时候都推荐传引用,例如:
    1. 对于常规类型(int ,float等非类的类型),传引用反而更慢
    2. 如果调用函数时把右值赋给了这个引用,是非常危险的,其效果等于野指针。(当然较新的C++里面貌似有了 && 这样的 universal reference 能够兼容右值,但是深究起来也挺麻烦的,就不提了)

  • @ 2016-10-05 23:47:16

    好奇为什么楼下一群人刷 getchar()getchar() 不是C++的IO方法,是C的IO方法!费那么大劲写一大串 getchar() 的优化,运行结果也只能和 scanf() 比较,和 cin >> 比较毫无意义。具体是不是真的变快了我倒也不知道,自己没用过这种优化。C++的单个字符输入方法是 cin.get();

  • @ 2016-07-18 15:15:11

    cin读入确实很慢,用c语言风格的读入会好很多。但大部分情况,比如要读入十万以上的数据我会选择手写快速读入。代码如下,仅供参考:
    inline int read()
    {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
    }
    风格承自黄学长(orz hzwer)

  • @ 2016-07-18 09:54:29

    cin爆炸

  • @ 2015-11-06 20:13:08

    并不知道vijos是什么状况,C++的流确实略慢,但我实测上上千万的数据读入只有级毫秒的差别

    所以还是用scanf吧...

  • @ 2015-11-04 07:55:06

    assb

  • @ 2015-10-31 17:15:33

    多谢各位大牛相助,已经学会读入优化。不过大家为什么都喜欢往读入函数里传引用,而不是直接把读入的值像下面这个函数一样直接返回呢?总不至于是因为传引用便于函数重载吧。
    ###C++ Code
    int getint()
    {
    int ans=0;
    for(char ch=getchar(); ch>='0'&&ch<='9'; ch=getchar())
    ans=ans*10+ch-'0';
    return ans;
    }

  • @ 2015-10-21 17:30:12

    读入优化大法好!!
    void read(int &x) {
    char chr = getchar();
    int minus = 1;
    x = 0;
    while (!isdigit(chr) && chr != '-')
    getchar();
    if (chr == '-') {
    minus = -1;
    chr = getchar();
    }
    while (isdigit(chr)) {
    x *= 10; x += chr - 48;
    chr = getchar();
    }
    x *= minus;
    }javascript:;

    • @ 2015-10-21 17:32:57

      记得 include <cctype>
      ###Block code
      void read(int &x) {
      char chr = getchar();
      int minus = 1;
      x = 0;
      while (!isdigit(chr) && chr != '-')
      getchar();
      if (chr == '-') {
      minus = -1;
      chr = getchar();
      }
      while (isdigit(chr)) {
      x *= 10; x += chr - 48;
      chr = getchar();
      }
      x *= minus;
      }

  • @ 2015-10-17 10:25:02

    用scanf吧

  • @ 2015-09-11 15:54:31

    那是因为你没用过_getchar()_

  • @ 2015-09-10 10:04:04

    我有一次测试了一下,得到了这样的经验:
    不开编译优化,关流同步,cin读入,printf输出是最快的方法
    但开了编译优化后好像就慢得超时
    所以我想可能是vijos开了个-O2优化,把cin卡超时了
    我当年NOIP就是这么写的,因为比赛时编译不会开优化
    在此我建议Vijos看下是不是C++编译命令有什么问题,或者TDM-GCC有什么猫腻
    希望能回答你的问题

  • @ 2015-09-08 21:09:48

    我也不清楚...不过楼上根本就不懂关闭流同步是什么》。

  • @ 2015-09-04 11:42:31

    vijos是用的tdm-gcc

    • @ 2015-09-04 16:38:00

      是5.1吗?

    • @ 2015-09-04 18:32:17

      似乎是4.8还是啥的 忘记啦

  • @ 2015-09-03 18:34:41

    scanf要比cin快

  • @ 2015-09-03 15:54:56

    就在我把cin换成scanf的时候果断AC了
    我知道C++IO慢,但是不可能读取两万个整数就用超过1S吧?
    况且有大神评测过地址,在关闭流同步后C++IO不比C的IO慢
    那么问题就来了
    VIJOS的iostream是怎么实现的呢?为何在关闭流同步后还差了这么多呢
    测试数据 #0: Accepted, time = 0 ms, mem = 5184 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 5184 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 5184 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 5188 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 5184 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 5184 KiB, score = 10
    测试数据 #6: Accepted, time = 46 ms, mem = 5184 KiB, score = 10
    测试数据 #7: Accepted, time = 125 ms, mem = 5184 KiB, score = 10
    测试数据 #8: Accepted, time = 203 ms, mem = 5184 KiB, score = 10
    测试数据 #9: Accepted, time = 187 ms, mem = 5184 KiB, score = 10
    Accepted, time = 576 ms, mem = 5188 KiB, score = 100
    代码
    //written by AH-360
    #include<cstdio>
    #define maxn 200001
    #define moder 10007
    int n,max_w,sum_w=0,u[maxn]={0},v[maxn]={0},w[maxn]={0};
    int first[maxn]={0},second[maxn]={0},sum[maxn]={0};
    void swap(int &p,int &q)
    {
    int temp=p;
    p=q;
    q=temp;
    }
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<n;++i)scanf("%d %d",&u[i],&v[i]);
    for(int i=1;i<=n;++i)scanf("%d",&w[i]);
    for(int i=1;i<n;++i)
    for(int j=0;j<=1;++j,swap(u[i],v[i]))
    {
    if(w[v[i]]>first[u[i]])
    {
    second[u[i]]=first[u[i]];
    first[u[i]]=w[v[i]];
    }else
    if(w[v[i]]>second[u[i]])
    second[u[i]]=w[v[i]];
    sum_w=(w[v[i]]*sum[u[i]]+sum_w)%moder;
    sum[u[i]]=(sum[u[i]]+w[v[i]])%moder;
    }
    for(int i=1;i<=n;++i)
    if(max_w<first[i]*second[i])
    max_w=first[i]*second[i];
    printf("%d %d",max_w,(2*sum_w)%moder);
    }

    • @ 2015-09-05 10:37:13

      这和 Vijos 无关好吗?
      这显然是 C++ 的问题呀
      cin 的速度本来就比 scanf 慢

    • @ 2015-10-20 06:34:18

      你似乎读入了60万个整数。

    • @ 2015-11-04 14:37:00

      呵呵

  • 1

信息

ID
1906
难度
7
分类
图结构 点击显示
标签
递交数
5638
已通过
914
通过率
16%
被复制
9
上传者