- 联合权值
- 2015-09-03 15:38:50 @
这道题最后三个点总是超时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 条评论
-
riteme LV 8 @ 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-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-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);
}
- 1