結果

問題 No.3719 Share the Tree
コンテスト
ユーザー GOTKAKO
提出日時 2026-09-18 22:24:59
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 109 ms / 2,000 ms
+ 1µs
コード長 1,594 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,319 ms
コンパイル使用メモリ 218,800 KB
実行使用メモリ 6,528 KB
平均クエリ数 2.00
最終ジャッジ日時 2026-09-18 22:25:10
合計ジャッジ時間 5,502 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s; cin >> s;
    if(s == "Alice") s = "Akane";
    else s = "Aoi";
    
    if(s == "Akane"){
        int N; cin >> N;
        cout << N-2 << endl;
        vector<vector<int>> Graph(N);
        for(int i=0; i<N-1; i++){
            int u,v; cin >> u >> v;
            u--; v--;
            Graph.at(u).push_back(v);
            Graph.at(v).push_back(u);
        }
        for(int t=0; t<N-2; t++){
            if(t) cout << " ";
            for(int i=0; i<N; i++) if(Graph.at(i).size() == 1){
                int k = Graph.at(i).at(0);
                for(int p=0; ; p++) if(Graph.at(k).at(p) == i){
                    Graph.at(k).erase(Graph.at(k).begin()+p); break;
                }
                cout << k+1;
                Graph.at(i) = {};
                break;
            }
        }         
        cout << endl;
    }
    if(s == "Aoi"){
        int N; cin >> N;
        cout << N-2 << endl;
        vector<int> C(N),A(N-2);
        for(auto &a : A) cin >> a,a--,C.at(a)++;
        for(int i=0; i<N-2; i++){
            int a = A.at(i);
            for(int k=0; k<N; k++) if(C.at(k) == 0){
                cout << a+1 << " " << k+1 << endl;
                C.at(k)++,C.at(a)--,A.at(i) = k; break;
            }
        }
        int a = -1,b = -1;
        for(int i=0; i<N; i++){
            if(C.at(i) == 0){
                if(a == -1) a = i;
                else b = i;
            }
        }
        cout << a+1 << " " << b+1 << endl;
    }
}
0