Submission #2882609


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);
				}
				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++){
		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 1713 Byte
Status WA
Exec Time 44 ms
Memory 14336 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 29 ms 7424 KB
OK_1.txt WA 30 ms 7424 KB
OK_2.txt WA 29 ms 7424 KB
OK_3.txt WA 28 ms 7424 KB
OK_4.txt AC 30 ms 7424 KB
close_0.txt AC 33 ms 6400 KB
close_1.txt WA 32 ms 6272 KB
close_2.txt AC 41 ms 6272 KB
close_3.txt AC 34 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 35 ms 6400 KB
many_3.txt AC 34 ms 6400 KB
many_4.txt AC 33 ms 6400 KB
many_5.txt AC 33 ms 6144 KB
many_6.txt AC 33 ms 6656 KB
many_7.txt AC 34 ms 6656 KB
max.txt WA 18 ms 4608 KB
maxBip.txt AC 25 ms 5248 KB
multiple_0.txt WA 36 ms 7808 KB
multiple_1.txt WA 38 ms 7808 KB
multiple_2.txt WA 39 ms 7936 KB
multiple_3.txt WA 40 ms 7936 KB
multiple_4.txt WA 41 ms 7936 KB
multiple_5.txt WA 39 ms 7936 KB
multiple_6.txt WA 39 ms 7936 KB
multiple_7.txt WA 38 ms 7808 KB
oddLoop.txt AC 44 ms 14336 KB
oddLoop_0.txt AC 42 ms 14208 KB
oddLoop_1.txt AC 25 ms 9472 KB
oddLoop_2.txt AC 36 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 35 ms 6656 KB
rnd_4.txt AC 35 ms 6528 KB
rnd_5.txt AC 31 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 29 ms 7284 KB
star_0.txt WA 29 ms 7284 KB
star_1.txt WA 29 ms 7284 KB
unique_0.txt WA 30 ms 6016 KB
unique_1.txt WA 30 ms 5888 KB
unique_2.txt WA 30 ms 6016 KB
unique_3.txt WA 31 ms 6144 KB
unique_4.txt WA 31 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 31 ms 6016 KB
unique_9.txt WA 30 ms 6144 KB