結果

問題 No.2301 Namorientation
ユーザー AngrySadEightAngrySadEight
提出日時 2023-03-16 16:14:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 956 ms / 3,000 ms
コード長 3,480 bytes
コンパイル時間 1,224 ms
コンパイル使用メモリ 103,032 KB
実行使用メモリ 40,952 KB
最終ジャッジ日時 2023-10-18 13:05:03
合計ジャッジ時間 21,997 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 474 ms
22,276 KB
testcase_13 AC 428 ms
20,776 KB
testcase_14 AC 901 ms
35,152 KB
testcase_15 AC 552 ms
24,584 KB
testcase_16 AC 732 ms
30,656 KB
testcase_17 AC 498 ms
23,264 KB
testcase_18 AC 774 ms
31,136 KB
testcase_19 AC 402 ms
19,536 KB
testcase_20 AC 742 ms
30,920 KB
testcase_21 AC 535 ms
24,056 KB
testcase_22 AC 511 ms
40,952 KB
testcase_23 AC 506 ms
40,424 KB
testcase_24 AC 420 ms
34,352 KB
testcase_25 AC 373 ms
28,388 KB
testcase_26 AC 487 ms
36,108 KB
testcase_27 AC 901 ms
35,276 KB
testcase_28 AC 902 ms
35,272 KB
testcase_29 AC 905 ms
35,272 KB
testcase_30 AC 915 ms
35,144 KB
testcase_31 AC 956 ms
35,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <queue>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    for (int i = 0; i < N; i++){
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }
    map<pair<int,int>, int> mp;
    for (int i = 0; i < N; i++){
        mp[pair<int,int>(A[i], B[i])] = i;
    }

    vector<vector<int>> graph(N, vector<int>(0));
    for (int i = 0; i < N; i++){
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }
    
    vector<bool> tag(N, true);
    vector<int> count(N, 0);
    for (int i = 0; i < N; i++){
        count[A[i]]++;
        count[B[i]]++;
    }
    
    //ループ以外の辺を削除するために BFS
    vector<bool> isvisited(N, false);
    queue<int> que;
    for (int i = 0; i < N; i++){
        if (count[i] == 1) que.push(i);
    }
    while(que.size()){
        int p = que.front();
        que.pop();
        if (isvisited[p]){
            continue;
        }
        isvisited[p] = true;
        for (int x: graph[p]){
            tag[mp[pair<int,int>(min(p, x), max(p, x))]] = false;
            count[x]--;
            if (count[x] == 1){
                que.push(x);
            }
        }
    }
    vector<int> ans(N);

    // ループのみのグラフ
    vector<vector<int>> graph2(N, vector<int>(0));
    int start = -1;
    for (int i = 0; i < N; i++){
        if (tag[i]){
            start = A[i];
            graph2[A[i]].push_back(B[i]);
            graph2[B[i]].push_back(A[i]);
        }
    }

    // ループの中だけをみる
    for (int i = 0; i < N; i++) isvisited[i] = false;
    
    int now = start;
    while(true){
        isvisited[now] = true;
        bool seen = false;
        for (int i = 0; i < graph2[now].size(); i++){
            if (isvisited[graph2[now][i]]){
                continue;
            }
            seen = true;
            if (graph2[now][i] > now){
                ans[mp[pair<int,int>(now, graph2[now][i])]] = 1;
            }
            else{
                ans[mp[pair<int,int>(graph2[now][i], now)]] = 0;
            }
            now = graph2[now][i];
            break;
        }
        if (!seen){
            for (int i = 0; i < graph2[now].size(); i++){
                if (graph2[now][i] == start){
                    if (graph2[now][i] > now){
                        ans[mp[pair<int,int>(now, graph2[now][i])]] = 1;
                    }
                    else{
                        ans[mp[pair<int,int>(graph2[now][i], now)]] = 0;
                    }
                }
            }
            break;
        }
    }

    // ループの外だけで BFS

    
    for (int i = 0; i < N; i++){
        if (isvisited[i]){
            que.push(i);
            while(que.size()){
                int p = que.front();
                que.pop();
                for (int x: graph[p]){
                    if (isvisited[x]) continue;
                    isvisited[x] = true;
                    if (p > x){
                        ans[mp[pair<int,int>(x, p)]] = 1;
                    }
                    else{
                        ans[mp[pair<int,int>(p, x)]] = 0;
                    }
                    que.push(x);
                }
            }
        }
    }
    for (int i = 0; i < N; i++){
        if (ans[i] == 1) cout << "->" << endl;
        else cout << "<-" << endl;
    }
    
    return 0;
}
0