結果
問題 |
No.1502 Many Simple Additions
|
ユーザー |
![]() |
提出日時 | 2021-05-09 13:36:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 151 ms / 2,000 ms |
コード長 | 2,117 bytes |
コンパイル時間 | 3,209 ms |
コンパイル使用メモリ | 185,644 KB |
最終ジャッジ日時 | 2025-01-21 09:34:33 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 39 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; int n, m; ll k; ll v[100010]; int p[100010]; using mint=modint1000000007; vector<P> g[100010]; int main() { cin>>n>>m>>k; for(int i=0; i<m; i++){ int x, y, z; cin>>x>>y>>z; x--; y--; g[x].push_back({y, z}); g[y].push_back({x, z}); } mint c1=1, c2=1; bool dame=0; vector<int> w; ll val=-1; auto dfs=[&](auto dfs, int x)->void{ w.push_back(x); for(auto q:g[x]){ int y=q.first; if(p[y]==0){ p[y]=-p[x]; v[y]=q.second-v[x]; dfs(dfs, y); }else if(p[y]!=p[x]){ if(v[y]!=q.second-v[x]){ dame=1; } }else{ ll v1=(q.second-v[x]-v[y])*p[x]; if(v1%2!=0 || v1<=0 || (val!=-1 && val!=v1/2)){ dame=1; } val=v1/2; } } }; for(int i=0; i<n; i++){ if(p[i]!=0) continue; p[i]=1; w.clear(); val=-1; dfs(dfs, i); if(dame){ cout<<0<<endl; return 0; } if(val==-1){ ll l=1, r=k; for(auto x:w){ if(p[x]==1){ l=max(l, 1-v[x]); r=min(r, k-v[x]); }else{ l=max(l, v[x]-k); r=min(r, v[x]-1); } } c1*=mint(max(0ll, r-l+1)); l=1, r=k-1; for(auto x:w){ if(p[x]==1){ l=max(l, 1-v[x]); r=min(r, k-1-v[x]); }else{ l=max(l, v[x]-(k-1)); r=min(r, v[x]-1); } } c2*=mint(max(0ll, r-l+1)); }else{ for(auto x:w){ if(p[x]==1) v[x]+=val; else v[x]-=val; if(v[x]<=0){ c1=0, c2=0; }else if(v[x]==k){ c2=0; }else if(v[x]>k){ c1=0, c2=0; } } } } if(dame) cout<<0<<endl; else cout<<(c1-c2).val()<<endl; return 0; }