結果

問題 No.1502 Many Simple Additions
ユーザー monnumonnu
提出日時 2021-05-07 23:13:05
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 3,091 bytes
コンパイル時間 1,730 ms
コンパイル使用メモリ 177,804 KB
実行使用メモリ 16,304 KB
最終ジャッジ日時 2023-10-13 22:36:26
合計ジャッジ時間 5,364 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,352 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 AC 1 ms
4,348 KB
testcase_07 AC 2 ms
4,352 KB
testcase_08 AC 2 ms
4,352 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,352 KB
testcase_11 AC 1 ms
4,348 KB
testcase_12 AC 1 ms
4,348 KB
testcase_13 AC 1 ms
4,348 KB
testcase_14 AC 2 ms
4,352 KB
testcase_15 AC 1 ms
4,348 KB
testcase_16 AC 2 ms
4,352 KB
testcase_17 AC 1 ms
4,348 KB
testcase_18 AC 1 ms
4,348 KB
testcase_19 AC 2 ms
4,356 KB
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 2 ms
4,352 KB
testcase_22 AC 1 ms
4,352 KB
testcase_23 AC 1 ms
4,348 KB
testcase_24 AC 2 ms
4,352 KB
testcase_25 AC 2 ms
4,352 KB
testcase_26 AC 1 ms
4,352 KB
testcase_27 AC 108 ms
11,844 KB
testcase_28 AC 108 ms
12,352 KB
testcase_29 AC 9 ms
8,680 KB
testcase_30 AC 160 ms
16,176 KB
testcase_31 AC 161 ms
16,188 KB
testcase_32 AC 161 ms
16,304 KB
testcase_33 AC 125 ms
12,044 KB
testcase_34 AC 130 ms
13,000 KB
testcase_35 AC 129 ms
12,216 KB
testcase_36 AC 83 ms
6,716 KB
testcase_37 AC 83 ms
6,784 KB
testcase_38 AC 95 ms
8,620 KB
testcase_39 AC 59 ms
6,396 KB
testcase_40 AC 27 ms
5,832 KB
testcase_41 AC 5 ms
4,356 KB
testcase_42 AC 107 ms
10,620 KB
testcase_43 AC 1 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

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