結果

問題 No.1502 Many Simple Additions
ユーザー monnumonnu
提出日時 2021-05-07 23:13:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 155 ms / 2,000 ms
コード長 3,091 bytes
コンパイル時間 2,118 ms
コンパイル使用メモリ 179,240 KB
実行使用メモリ 16,384 KB
最終ジャッジ日時 2024-09-15 18:21:15
合計ジャッジ時間 5,155 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
using ll=long long;
using Graph=vector<vector<pair<int,ll>>>;
#define MAX 200003
#define INF 1000000000000000000
#define MOD 1000000007

bool dfs(Graph &G,int v,int p,vector<ll> &a,vector<int> &color,ll &x,ll &min0,ll &max0,ll &min1,ll &max1){
  if(color[v]==0){
    min0=min<ll>(min0,a[v]);
    max0=max<ll>(max0,a[v]);
  }else{
    min1=min<ll>(min1,a[v]);
    max1=max<ll>(max1,a[v]);
  }
  for(auto e:G[v]){
    int nv=e.first;
    int sum=e.second;
    if(nv==p){
      continue;
    }
    if(a[nv]==INF){
      a[nv]=sum-a[v];
      color[nv]=1-color[v];
      if(dfs(G,nv,v,a,color,x,min0,max0,min1,max1)==false){
        return false;
      }
    }else{
      if(color[v]!=color[nv]){
        if(a[v]+a[nv]!=sum){
          return false;
        }
      }else{
        if(x!=INF){
          if(color[v]==0){
            if(a[v]+a[nv]+2*x!=sum){
              return false;
            }
          }else{
            if(a[v]+a[nv]-2*x!=sum){
              return false;
            }
          }
        }else{
          if((sum-a[v]-a[nv])%2==1){
            return false;
          }
          if(color[v]==0){
            x=(sum-a[v]-a[nv])/2;
          }else{
            x=(a[v]+a[nv]-sum)/2;
          }
        }
      }
    }
  }
  return true;
}

int main(){
  int N,M;
  ll K;
  cin>>N>>M>>K;
  Graph G(N);
  for(int i=0;i<M;i++){
    int x,y;
    ll z;
    cin>>x>>y>>z;
    x--;y--;
    G[x].push_back(make_pair(y,z));
    G[y].push_back(make_pair(x,z));
  }

  vector<ll> a(N,INF);
  vector<int> color(N,-1);
  bool flag=false;
  vector<pair<ll,ll>> v;
  for(int i=0;i<N;i++){
    if(a[i]==INF){
      ll x=INF;
      a[i]=0;
      color[i]=0;
      ll min0=0;
      ll max0=0;
      ll min1=INF;
      ll max1=-INF;
      if(dfs(G,i,-1,a,color,x,min0,max0,min1,max1)==false){
        cout<<0<<endl;
        return 0;
      }
      if(x!=INF){
        if(min0+x<=0||min1-x<=0||max0+x>K||max1-x>K){
          cout<<0<<endl;
          return 0;
        }
        if(max0+x==K||max1-x==K){
          flag=true;
        }
      }else{
        ll p=K-max0;
        ll q=-K+max1;//q<=x<=p
        if(min0+p<=0||max1-p>K){
          cout<<0<<endl;
          return 0;
        }
        if(min1-q<=0||max0+q>K){
          cout<<0<<endl;
          return 0;
        }
        ll ans1=0;
        ll ans2=0;
        if(min1-p>0){
          ans1++;
        }else{
          p=min1-1;
        }
        if(min0+q>0){
          ans1++;
        }else{
          q=-min0+1;
        }
        ans2=max<ll>(0,p-q+1);
        ans1=min<ll>(ans1,ans2);
        v.push_back(make_pair(ans1,ans2));
      }
    }
  }

  if(flag==true){
    ll ans=1;
    for(int i=0;i<v.size();i++){
      ans=ans*v[i].second%MOD;
    }
    cout<<ans<<endl;
  }else{
    if(v.size()==0){
      cout<<0<<endl;
      return 0;
    }
    ll x=1;
    ll y=1;
    for(int i=0;i<v.size();i++){
      x=x*v[i].second%MOD;
      y=y*(v[i].second-v[i].first)%MOD;
    }
    ll ans=(x-y+MOD)%MOD;
    cout<<ans<<endl;
  }
}
0