Submission #2880409
Source Code Expand
#include<set> #include<map> #include<stack> #include<cmath> #include<cstdio> #include<queue> #include<vector> #include<cstring> #include<climits> #include<iostream> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f #define MAXN 100000 #define LL long long int read(){ int f=1,x=0; char c=getchar(); while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();} while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();} return f*x; } int n,m,Min=1,Max=INF,val[MAXN+5],vis[MAXN+5]; struct edge{ int v,w; edge(){} edge(int V,int W){v=V,w=W;} }; vector<edge> G[MAXN+5]; void DFS(int x,int u,int fa,int f){ if(x<=0){ if(f){ printf("0\n"); exit(0); } Min=max(Min,-x+1); } if(f) Max=min(Max,x); vis[u]=f+1,val[u]=x; int v,w,siz=G[u].size(); for(int i=0;i<siz;i++){ v=G[u][i].v,w=G[u][i].w; if(v==fa) continue; if(vis[v]){ if(vis[u]==vis[v]){ if(val[u]+val[v]>w||(val[u]+val[v])%2!=w%2){ printf("0\n"); exit(0); } Max=Min=(val[u]+val[v]-w)/2; }else{ if(val[u]+val[v]!=w){ printf("0\n"); exit(0); } if(val[v]<=0) Min=max(Min,-val[v]+1); else Max=min(Max,val[v]); } return ; } DFS(w-x,v,u,(f+1)%2); } return ; } int main(){ n=read(),m=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(),w=read(); G[u].push_back(edge(v,w)); G[v].push_back(edge(u,w)); } DFS(1,1,-1,0); if(Max<Min) printf("0\n"); else printf("%d\n",Max-Min+1); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - + Graph |
User | C20192413 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1550 Byte |
Status | WA |
Exec Time | 45 ms |
Memory | 14336 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | WA | 29 ms | 7424 KB |
OK_1.txt | WA | 29 ms | 7424 KB |
OK_2.txt | WA | 28 ms | 7424 KB |
OK_3.txt | WA | 28 ms | 7424 KB |
OK_4.txt | WA | 30 ms | 7424 KB |
close_0.txt | AC | 34 ms | 6400 KB |
close_1.txt | WA | 33 ms | 6272 KB |
close_2.txt | AC | 33 ms | 6272 KB |
close_3.txt | AC | 35 ms | 6400 KB |
close_4.txt | AC | 34 ms | 7296 KB |
many_0.txt | AC | 32 ms | 6656 KB |
many_1.txt | AC | 33 ms | 6272 KB |
many_2.txt | AC | 36 ms | 6400 KB |
many_3.txt | AC | 34 ms | 6400 KB |
many_4.txt | AC | 34 ms | 6400 KB |
many_5.txt | AC | 34 ms | 6144 KB |
many_6.txt | AC | 34 ms | 6656 KB |
many_7.txt | AC | 33 ms | 6656 KB |
max.txt | WA | 18 ms | 4736 KB |
maxBip.txt | AC | 26 ms | 5248 KB |
multiple_0.txt | WA | 36 ms | 7808 KB |
multiple_1.txt | WA | 40 ms | 7808 KB |
multiple_2.txt | WA | 39 ms | 7936 KB |
multiple_3.txt | WA | 40 ms | 7936 KB |
multiple_4.txt | WA | 40 ms | 7936 KB |
multiple_5.txt | WA | 43 ms | 7936 KB |
multiple_6.txt | WA | 41 ms | 7936 KB |
multiple_7.txt | WA | 39 ms | 7808 KB |
oddLoop.txt | AC | 43 ms | 14336 KB |
oddLoop_0.txt | AC | 45 ms | 14208 KB |
oddLoop_1.txt | AC | 25 ms | 9472 KB |
oddLoop_2.txt | AC | 37 ms | 12416 KB |
rnd_0.txt | AC | 32 ms | 7552 KB |
rnd_1.txt | WA | 34 ms | 6912 KB |
rnd_2.txt | WA | 33 ms | 7296 KB |
rnd_3.txt | AC | 33 ms | 6656 KB |
rnd_4.txt | AC | 35 ms | 6528 KB |
rnd_5.txt | AC | 32 ms | 5760 KB |
rnd_6.txt | AC | 34 ms | 6784 KB |
rnd_7.txt | WA | 34 ms | 6656 KB |
rnd_8.txt | AC | 32 ms | 6144 KB |
rnd_9.txt | AC | 25 ms | 5248 KB |
sampleNo.txt | AC | 2 ms | 2560 KB |
samplePath.txt | AC | 2 ms | 2560 KB |
sampleTri.txt | AC | 2 ms | 2560 KB |
star.txt | WA | 32 ms | 7284 KB |
star_0.txt | WA | 31 ms | 7284 KB |
star_1.txt | WA | 33 ms | 7284 KB |
unique_0.txt | WA | 32 ms | 6016 KB |
unique_1.txt | WA | 35 ms | 5888 KB |
unique_2.txt | WA | 30 ms | 6016 KB |
unique_3.txt | WA | 30 ms | 6144 KB |
unique_4.txt | WA | 30 ms | 6016 KB |
unique_5.txt | WA | 30 ms | 6272 KB |
unique_6.txt | WA | 30 ms | 6016 KB |
unique_7.txt | WA | 31 ms | 6144 KB |
unique_8.txt | WA | 30 ms | 6016 KB |
unique_9.txt | WA | 30 ms | 6144 KB |