結果

問題 No.3482 Quod Erat Demonstrandum
コンテスト
ユーザー joijoy
提出日時 2026-03-27 21:31:13
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,301 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,241 ms
コンパイル使用メモリ 350,720 KB
実行使用メモリ 18,224 KB
最終ジャッジ日時 2026-03-27 21:31:34
合計ジャッジ時間 17,718 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")

using ll=long long;
using current=pair<int, pair<int, int>>;
int nibutan(int n, vector<int> A, int key){
    int ok=n;
    int ng=-1;
    while(ok-ng>1){
        int mid=(ok+ng)/2;
        if(A[mid]>key){
            ok=mid;
        }else{
            ng=mid;
        }
    }
    return ok;
}
void update(int i, int n, int x, vector<int> &data){
    i+=n-1;    
    data[i]= x;
        while(i>1){
            i/=2;
            data[i]=max(data[i*2], data[i*2+1]);
        }
    }
int get(int n, int l, int r, vector<int> &data){
        int res=0;
        l+=n-1;
        r+=n-1;
        while(r>l){
            if(l&1){
                res=max(data[l], res);
                l++;
            }
            l>>=1;
            if(r&1){
                r--;
                res=max(res, data[r]);
            }
            r>>=1;
        }
        return res;
}
int main(){
    int T;
    cin >> T;
    for(int o=0;o<T;o++){
        int N, M;
        cin >> N >> M;
        vector<vector<pair<int, int>>> G(N+1);
        for(int i=0;i<M;i++){
            int a, b, c;
            cin >> a >> b >> c;
            G[a].push_back({b, c});
            G[b].push_back({a, c});
        }
        vector<int> res(N+1, 0), dist(N+1, -1);
        vector<bool> seen(N+1, false);
        queue<int> q;
        res[1]=1;
        dist[1]=0;
        seen[1]=true;
        q.push(1);
        while(!q.empty()){
            int p=q.front();
            for(pair<int, int> r:G[p]){
                int nex=r.first;
                int c=r.second;
                if(seen[nex]){
                    continue;
                }
                seen[nex]=true;
                if(c==1){
                    res[nex]=res[p];
                }else{
                    res[nex]=3-res[p];
                }
                dist[nex]=dist[p]+1;
                q.push(nex);
            }
            q.pop();
        }
        if(res[N]==0){
            cout << "Unknown" << endl;
            continue;
        }
        if(res[N]==1){
            cout << "Same";
        }else{
            cout << "Different";
        }
        cout << endl;
        cout << dist[N] << endl;

    }
}
0