Submission #2883913


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
LL read(){ 
    LL 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; 
}
LL n,m,Min=1,Max=INF,val[MAXN+5],vis[MAXN+5];
struct edge{
	LL v,w;
	edge(){}
	edge(LL V,LL W){v=V,w=W;}
};
vector<edge> G[MAXN+5];
void DFS(LL x,LL u,LL fa,LL 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;
	LL 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);
				}
				if(Min>1+(w-(val[u]+val[v]))/2||Max<1+(w-(val[u]+val[v]))/2){
					printf("0\n");
					exit(0);
				}
				Max=Min=1+(w-(val[u]+val[v]))/2;
			}else{
				if(val[u]+val[v]!=w){
					printf("0\n");
					exit(0);
				}
				if(val[v]<=0){
					if(vis[v]-1){
						printf("0\n");
						exit(0);
					}
					Min=max(Min,-val[v]+1);
				}
			}
			return ;
		}
		DFS(w-x,v,u,(f+1)%2);
	}
	return ;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		LL 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);
	printf("%lld\n",max(0ll,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 1678 Byte
Status WA
Exec Time 55 ms
Memory 17152 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 28
WA × 30
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 32 ms 9472 KB
OK_1.txt WA 32 ms 9472 KB
OK_2.txt WA 32 ms 9472 KB
OK_3.txt WA 33 ms 9472 KB
OK_4.txt AC 34 ms 9472 KB
close_0.txt AC 40 ms 8832 KB
close_1.txt WA 37 ms 8576 KB
close_2.txt AC 39 ms 8576 KB
close_3.txt AC 39 ms 8576 KB
close_4.txt AC 37 ms 9472 KB
many_0.txt AC 36 ms 8064 KB
many_1.txt AC 37 ms 7680 KB
many_2.txt AC 40 ms 7936 KB
many_3.txt AC 37 ms 8064 KB
many_4.txt AC 37 ms 8320 KB
many_5.txt AC 37 ms 7680 KB
many_6.txt AC 37 ms 8320 KB
many_7.txt AC 37 ms 8448 KB
max.txt WA 20 ms 6528 KB
maxBip.txt AC 28 ms 7680 KB
multiple_0.txt WA 42 ms 9856 KB
multiple_1.txt WA 44 ms 9984 KB
multiple_2.txt WA 49 ms 10112 KB
multiple_3.txt WA 44 ms 10240 KB
multiple_4.txt WA 47 ms 10240 KB
multiple_5.txt WA 46 ms 10240 KB
multiple_6.txt WA 45 ms 10112 KB
multiple_7.txt WA 48 ms 9984 KB
oddLoop.txt AC 52 ms 17152 KB
oddLoop_0.txt AC 55 ms 17024 KB
oddLoop_1.txt AC 30 ms 11136 KB
oddLoop_2.txt AC 45 ms 14848 KB
rnd_0.txt AC 37 ms 9600 KB
rnd_1.txt WA 38 ms 9216 KB
rnd_2.txt WA 37 ms 9344 KB
rnd_3.txt AC 39 ms 8704 KB
rnd_4.txt AC 40 ms 8576 KB
rnd_5.txt AC 35 ms 8192 KB
rnd_6.txt AC 41 ms 8960 KB
rnd_7.txt WA 37 ms 8832 KB
rnd_8.txt AC 37 ms 8320 KB
rnd_9.txt AC 28 ms 7808 KB
sampleNo.txt AC 3 ms 2560 KB
samplePath.txt AC 3 ms 2560 KB
sampleTri.txt AC 3 ms 2560 KB
star.txt WA 33 ms 8816 KB
star_0.txt WA 33 ms 8816 KB
star_1.txt WA 32 ms 8816 KB
unique_0.txt WA 34 ms 7936 KB
unique_1.txt WA 34 ms 7936 KB
unique_2.txt WA 35 ms 8064 KB
unique_3.txt WA 34 ms 8192 KB
unique_4.txt WA 35 ms 7936 KB
unique_5.txt WA 34 ms 8448 KB
unique_6.txt WA 34 ms 8064 KB
unique_7.txt WA 35 ms 8320 KB
unique_8.txt WA 34 ms 8064 KB
unique_9.txt WA 34 ms 8192 KB