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
AC × 3
AC × 58
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