結果

問題 No.1502 Many Simple Additions
ユーザー 沙耶花
提出日時 2021-05-07 22:28:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 137 ms / 2,000 ms
コード長 2,870 bytes
コンパイル時間 4,603 ms
コンパイル使用メモリ 271,244 KB
最終ジャッジ日時 2025-01-21 08:25:08
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:10:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   10 | vector<int> get_dis(auto &E){
      |                     ^~~~
main.cpp:31:30: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   31 | vector<long long> assign_all(auto &E,long long fir){
      |                              ^~~~
main.cpp:51:20: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   51 | long long get_diff(auto &E,vector<long long> v){
      |                    ^~~~
main.cpp: In function ‘int main()’:
main.cpp:120:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  120 |                 scanf("%d %d %d",&X[i],&Y[i],&Z[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000000001
vector<int> get_dis(auto &E){
    vector<int> ret(E.size(),-1);
    queue<int> Q;
    Q.push(0);
    ret[0] = 0;
    
    while(Q.size()!=0){
        int u = Q.front();
        Q.pop();
        for(int i=0;i<E[u].size();i++){
            int v = E[u][i].first;
            if(ret[v]==-1){
                ret[v] = ret[u]^1;
                Q.push(v);
            }
        }
    }
    
    return ret;
}
 
vector<long long> assign_all(auto &E,long long fir){
    vector<long long> ret(E.size(),Inf);
    queue<int> Q;
    Q.push(0);
    ret[0] = fir;
    while(Q.size()!=0){
        int u = Q.front();
        Q.pop();
        for(int i=0;i<E[u].size();i++){
            int v = E[u][i].first;
            long long s = E[u][i].second;
            if(ret[v]==Inf){
                ret[v] = s - ret[u];
                Q.push(v);
            }
        }
    }
    return ret;
}
 
long long get_diff(auto &E,vector<long long> v){
    long long ret = 0;
    for(int i=0;i<E.size();i++){
        for(int j=0;j<E[i].size();j++){
            ret = max(ret,abs((v[i]+v[E[i][j].first])-E[i][j].second));
        }
    }
    return ret;
}
long long solve(int n,int m,vector<vector<pair<int,long long>>> E,long long K){
    if(n==1)return K;
    vector<int> parity = get_dis(E);
    
    bool is_bin = true;
    for(int i=0;i<n;i++){
        for(int j=0;j<E[i].size();j++){
            if(parity[i]==parity[E[i][j].first]){
                is_bin = false;
            }
        }
    }
    vector<long long> V = assign_all(E,1);
    
    if(is_bin){
        if(get_diff(E,V)!=0){
            return 0;
        }
        long long L = 0,R = K-1;
        for(int i=0;i<n;i++){
            if(parity[i]==0){
                L = max(L,1-V[i]);
                R = min(R,K-V[i]);
            }
            else{
                R = min(R,V[i]-1);
                L = max(L,V[i]-K);
            }
        }
        if(R<L)return 0;
        else return R-L+1;
    }
    else{
        long long t = get_diff(E,V);
        ///cout<<t<<endl;
        V = assign_all(E,t/2+1LL);
        if(get_diff(E,V)!=0){
            return 0;
        }
        for(int i=0;i<n;i++){
            if(V[i]<=0){
                return 0;
            }
            if(V[i]>K){
                return 0;
            }
        }
        return 1;
    }
}
int main(){
    int N,M,K;
    cin>>N>>M>>K;
    
    vector<int> X(M),Y(M),Z(M);
    rep(i,M){
        scanf("%d %d %d",&X[i],&Y[i],&Z[i]);
        X[i]--;Y[i]--;
    }
    
    dsu D(N);
    rep(i,M){
        D.merge(X[i],Y[i]);
    }
    
    vector<vector<vector<pair<int,long long>>>> E;
    
    vector<pair<int,int>> par(N);
    {
        auto g = D.groups();
        E.resize(g.size());
        rep(i,g.size()){
            E[i].resize(g[i].size());
            rep(j,g[i].size()){
                par[g[i][j]] = make_pair(i,j);
            }
        }
    }
    
    rep(i,M){
        int ind = par[X[i]].first;
        int a = par[X[i]].second,b = par[Y[i]].second;
        
        E[ind][a].emplace_back(b,Z[i]);
        E[ind][b].emplace_back(a,Z[i]);
    }
    
    mint ans = 0;
    
    {
        mint temp = 1;
        rep(i,E.size()){
            temp *= solve(E[i].size(),0,E[i],K);
        }
        ans += temp;
    }
    //cout<<ans.val()<<endl;
    {
        mint temp = 1;
        rep(i,E.size()){
            temp *= solve(E[i].size(),0,E[i],K-1);
        }
        ans -= temp;
    }
    
    
    cout<<ans.val()<<endl;
    
        
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0