Submission #3232918

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

vector<pair<int,ll>> g[100005];
int color[100005];
int num[100005];

int low,up;

bool dfs(int u,int c,int tmp){

  if(color[u]!=-1){
    if(color[u]==c) return tmp==num[u];
    int z;
    if(c) z=tmp-num[u];
    else z=num[u]-tmp;

    if(z%2||z<=0) return false;
    if(low==up&&z/2!=low) return false;
    if(z/2<low||z/2>up) return false;
    low=up=z/2;
    return true;
  }

  color[u]=c;
  num[u]=tmp;
  if(c) if(up>tmp-1) up=tmp-1;
  if(!c) if(low<1-tmp) low=1-tmp;
  if(low>up) return false;

  for(int i=0;i<g[u].size();i++){
    if(!dfs(g[u][i].first,1-c,g[u][i].second-tmp)) return false;
  }
  return true;
}

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int u,v;
    ll s;
    cin>>u>>v>>s;
    g[u].push_back(make_pair(v,s));
    g[v].push_back(make_pair(u,s));
  }

  memset(color,-1,sizeof(color));
  low=-1;
  up=1e9+1;

  if(dfs(1,0,0)) cout<<up-low+1<<endl;
  else cout<<0<<endl;

  return 0;
}

Submission Info

Judge Result