#1154314 (C++23) No.3482 Quod Erat Demonstrandum

• 問題: No.3482 Quod Erat Demonstrandum
• ユーザー: ZeriToki
• 提出日時: 2026-03-27 23:01:54
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 2,737 bytes
• コンパイル時間: 3,946 ms
• コンパイル使用メモリ: 344,128 KB
• 実行使用メモリ: 23,160 KB
• 最終ジャッジ日時: 2026-03-27 23:02:10
• 合計ジャッジ時間: 7,788 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 35 WA * 10

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const long long mod=998244353;
const long long mod2=469762049;
struct UnionFind{
    int n;
    vector<int>siz,par;
    UnionFind(int N):n(N){
        siz.assign(N+1,1);
        par.assign(N+1,-1);
    }
    int root(int p){
        assert(1<=p && p<=n);
        int res=p;
        while(true){
            if(par[res]==-1) break;
            res=par[res];
        }
        int a;
        while(true){
            if(par[p]==-1) return p;
            a=p;
            p=par[p];
            par[a]=res;
        }
    }
    bool unite(int u,int v){
        int rootU=root(u),rootV=root(v);
        if(rootU==rootV) return 0;
        if(siz[rootU]>=siz[rootV]){
            siz[rootU]+=siz[rootV];
            par[rootV]=rootU;
        }
        else{
            siz[rootV]+=siz[rootU];
            par[rootU]=rootV;
        }
        return 1;
    }
    bool same(int a,int b){
        return root(a)==root(b);
    }
};
void solve(){
    int N,M;cin>>N>>M;
    int A[M+1],B[M+1],C[M+1];
    vector<pair<int,int>>G[N+1];
    UnionFind UF(N);
    for(int i=1;i<=M;i++){
        cin>>A[i]>>B[i]>>C[i];
        G[A[i]].push_back({C[i],B[i]});
        G[B[i]].push_back({C[i],A[i]});
        UF.unite(A[i],B[i]);
    }
    if(UF.same(1,N)==false){
        cout<<"Unknown"<<endl;
        return;
    }
    int color[N+1],dist[N+1];
    bool already[N+1];
    for(int i=1;i<=N;i++){
        color[i]=-1;
        dist[i]=1e9;
        already[i]=false;
    }
    queue<int>que;
    que.push(1);
    color[1]=0;
    dist[1]=0;
    while(!que.empty()){
        int pos=que.front();
        que.pop();
        if(already[pos]) continue;
        already[pos]=true;
        for(auto nex:G[pos]){
            if(already[nex.second]) continue;
            if(nex.first==1){
                que.push(nex.second);
                color[nex.second]=color[pos];
            }
            else{
                if(color[nex.second]==-1){
                    que.push(nex.second);
                }
                color[nex.second]=color[pos]^1;
            }
            if(dist[nex.second]>dist[pos]+1){
                dist[nex.second]=dist[pos]+1;
                que.push(nex.second);
            }
        }
    }
    if(color[N]==0){
        cout<<"Same"<<endl;
    }
    else {
        cout<<"Different"<<endl;
    }
    cout<<dist[N]<<endl;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int T;cin>>T;
    while(T--) solve();
}