Submission #2875890
Source Code Expand
#include<iostream> #include<cstdio> #include<cstring> #include<climits> #include<algorithm> #include<cmath> #include<queue> using namespace std; #define MAXN 100000 #define MAXM 100000 #define INF 1000000000000000 struct node { int next,to; long long w; }e[MAXM*2+5]; struct Qr { int xr,dec; long long lim; }; long long T; int cnt,m,n; int x,y,z,flag; long long ri=INF,le=-INF; long long vis[2][MAXN+5]; int b[MAXN+5]; void fpush(int u,int v,long long w) { e[++cnt].next=b[u]; e[cnt].w=w; e[cnt].to=v; b[u]=cnt; } int Ch(int x){if(x==-1)x=0;return x;} int main() { fill(vis[0],vis[0]+MAXN+1,INF); fill(vis[1],vis[1]+MAXN+1,INF); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); fpush(x,y,z);fpush(y,x,z); } queue<Qr> Q; Q.push((Qr){1,1,0}); while(!Q.empty()) { Qr A=Q.front(); Q.pop(); int xr=A.xr,dec=A.dec; long long lim=A.lim; for(int i=b[xr];i;i=e[i].next) { int xnext=e[i].to; long long nlim=e[i].w-lim; int FD=Ch(dec); if(vis[FD][xnext]!=INF) { if(vis[FD][xnext]!=nlim){printf("0\n");return 0;} else continue; } vis[FD][xnext]=nlim; if(!FD)le=max(le,-vis[FD][xnext]); else ri=min(ri,vis[FD][xnext]); Q.push((Qr){xnext,-dec,nlim}); } } long long T=-1; for(int i=1;i<=n;i++) if(vis[0][i]!=INF&&vis[1][i]!=INF) { long long NT=(vis[1][i]-vis[0][i])/2; if(NT<0){flag=1;break;} if(T==-1)T=NT; else if(T!=NT){flag=1;break;} } if(flag){printf("0\n");} if(T!=-1) { if(T>le&&T<ri)printf("1\n"); else printf("0\n"); } else printf("%lld",max((long long)0,ri-le-1)); }
Submission Info
Submission Time | |
---|---|
Task | E - + Graph |
User | vjudge3 |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1872 Byte |
Status | AC |
Exec Time | 40 ms |
Memory | 6912 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:40:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&n,&m); ^ ./Main.cpp:43:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d",&x,&y,&z); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sampleNo.txt, samplePath.txt, sampleTri.txt |
All | OK_0.txt, OK_1.txt, OK_2.txt, OK_3.txt, OK_4.txt, close_0.txt, close_1.txt, close_2.txt, close_3.txt, close_4.txt, many_0.txt, many_1.txt, many_2.txt, many_3.txt, many_4.txt, many_5.txt, many_6.txt, many_7.txt, max.txt, maxBip.txt, multiple_0.txt, multiple_1.txt, multiple_2.txt, multiple_3.txt, multiple_4.txt, multiple_5.txt, multiple_6.txt, multiple_7.txt, oddLoop.txt, oddLoop_0.txt, oddLoop_1.txt, oddLoop_2.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, rnd_5.txt, rnd_6.txt, rnd_7.txt, rnd_8.txt, rnd_9.txt, sampleNo.txt, samplePath.txt, sampleTri.txt, star.txt, star_0.txt, star_1.txt, unique_0.txt, unique_1.txt, unique_2.txt, unique_3.txt, unique_4.txt, unique_5.txt, unique_6.txt, unique_7.txt, unique_8.txt, unique_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
OK_0.txt | AC | 34 ms | 5760 KB |
OK_1.txt | AC | 34 ms | 5760 KB |
OK_2.txt | AC | 34 ms | 5760 KB |
OK_3.txt | AC | 34 ms | 5760 KB |
OK_4.txt | AC | 34 ms | 5760 KB |
close_0.txt | AC | 32 ms | 5760 KB |
close_1.txt | AC | 38 ms | 5888 KB |
close_2.txt | AC | 29 ms | 5376 KB |
close_3.txt | AC | 34 ms | 6016 KB |
close_4.txt | AC | 36 ms | 5888 KB |
many_0.txt | AC | 29 ms | 5248 KB |
many_1.txt | AC | 29 ms | 5248 KB |
many_2.txt | AC | 29 ms | 5248 KB |
many_3.txt | AC | 29 ms | 5248 KB |
many_4.txt | AC | 29 ms | 5248 KB |
many_5.txt | AC | 29 ms | 5248 KB |
many_6.txt | AC | 29 ms | 5248 KB |
many_7.txt | AC | 29 ms | 5248 KB |
max.txt | AC | 32 ms | 4992 KB |
maxBip.txt | AC | 27 ms | 4992 KB |
multiple_0.txt | AC | 33 ms | 5888 KB |
multiple_1.txt | AC | 34 ms | 5760 KB |
multiple_2.txt | AC | 35 ms | 5632 KB |
multiple_3.txt | AC | 34 ms | 5632 KB |
multiple_4.txt | AC | 34 ms | 5632 KB |
multiple_5.txt | AC | 34 ms | 5632 KB |
multiple_6.txt | AC | 34 ms | 5632 KB |
multiple_7.txt | AC | 34 ms | 5752 KB |
oddLoop.txt | AC | 33 ms | 5376 KB |
oddLoop_0.txt | AC | 33 ms | 5248 KB |
oddLoop_1.txt | AC | 22 ms | 4224 KB |
oddLoop_2.txt | AC | 32 ms | 4736 KB |
rnd_0.txt | AC | 37 ms | 6016 KB |
rnd_1.txt | AC | 40 ms | 5888 KB |
rnd_2.txt | AC | 37 ms | 6016 KB |
rnd_3.txt | AC | 31 ms | 5760 KB |
rnd_4.txt | AC | 33 ms | 5888 KB |
rnd_5.txt | AC | 32 ms | 5632 KB |
rnd_6.txt | AC | 32 ms | 6016 KB |
rnd_7.txt | AC | 38 ms | 6016 KB |
rnd_8.txt | AC | 32 ms | 6400 KB |
rnd_9.txt | AC | 28 ms | 5164 KB |
sampleNo.txt | AC | 2 ms | 1792 KB |
samplePath.txt | AC | 2 ms | 1792 KB |
sampleTri.txt | AC | 2 ms | 1792 KB |
star.txt | AC | 31 ms | 6912 KB |
star_0.txt | AC | 31 ms | 6912 KB |
star_1.txt | AC | 31 ms | 6912 KB |
unique_0.txt | AC | 37 ms | 5888 KB |
unique_1.txt | AC | 37 ms | 5888 KB |
unique_2.txt | AC | 37 ms | 5888 KB |
unique_3.txt | AC | 37 ms | 5888 KB |
unique_4.txt | AC | 37 ms | 5888 KB |
unique_5.txt | AC | 37 ms | 5888 KB |
unique_6.txt | AC | 37 ms | 5888 KB |
unique_7.txt | AC | 37 ms | 5888 KB |
unique_8.txt | AC | 39 ms | 5888 KB |
unique_9.txt | AC | 37 ms | 5888 KB |