結果

問題 No.2301 Namorientation
ユーザー 👑 AngrySadEightAngrySadEight
提出日時 2023-03-16 16:16:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 937 ms / 3,000 ms
コード長 3,590 bytes
コンパイル時間 1,477 ms
コンパイル使用メモリ 103,096 KB
実行使用メモリ 40,752 KB
最終ジャッジ日時 2024-09-18 09:24:40
合計ジャッジ時間 22,152 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 493 ms
22,400 KB
testcase_13 AC 447 ms
20,480 KB
testcase_14 AC 925 ms
34,944 KB
testcase_15 AC 550 ms
24,320 KB
testcase_16 AC 756 ms
30,464 KB
testcase_17 AC 499 ms
23,040 KB
testcase_18 AC 764 ms
30,976 KB
testcase_19 AC 389 ms
19,584 KB
testcase_20 AC 784 ms
30,848 KB
testcase_21 AC 551 ms
24,064 KB
testcase_22 AC 521 ms
40,752 KB
testcase_23 AC 504 ms
40,120 KB
testcase_24 AC 424 ms
34,048 KB
testcase_25 AC 387 ms
28,336 KB
testcase_26 AC 496 ms
35,816 KB
testcase_27 AC 932 ms
35,040 KB
testcase_28 AC 926 ms
35,072 KB
testcase_29 AC 936 ms
35,060 KB
testcase_30 AC 911 ms
35,196 KB
testcase_31 AC 937 ms
34,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    int N;
    cin >> N;
    assert(N >= 3 && N <= 200000);
    vector<int> A(N);
    vector<int> B(N);
    for (int i = 0; i < N; i++){
        cin >> A[i] >> B[i];
        assert (1 <= A[i] && A[i] < B[i] && B[i] <= N);
        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