oj.uz

Submission #781394

# Submission time Handle Problem Language Result Execution time Memory
781394 2023-07-13T05:12:57 Z 이동현(#10013) JOI15_road_development (JOI15_road_development) C++14
10 / 100
 2000 ms 52476 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

struct Dsu{
    int n;
    vector<int> pr;
    Dsu(int N){
        n = N + 4;
        pr.resize(n);
        iota(pr.begin(), pr.end(), 0);
    }
    int fd(int x){
        return (x == pr[x] ? x : pr[x] = fd(pr[x]));
    }
    bool unite(int x, int y){
        x = fd(x), y = fd(y);
        if(x != y){
            pr[x] = y;
            return true;
        }
        return false;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<vector<int>> que(q, vector<int>(3));
    vector<vector<int>> way(n);
    Dsu gr(n + 4);
    for(int i = 0; i < q; ++i){
        cin >> que[i][0] >> que[i][1] >> que[i][2];
        --que[i][1], --que[i][2];
        if(que[i][0] == 1){
            if(gr.unite(que[i][1], que[i][2])){
                // cout << que[i][1] << ' ' << que[i][2] << endl;
                way[que[i][1]].push_back(que[i][2]);
                way[que[i][2]].push_back(que[i][1]);
            }
        }
    }

    vector<int> dep(n);
    vector<vector<int>> spa(n, vector<int>(20));
    auto dfs = [&](auto&&self, int x)->void{
        for(auto&nxt:way[x]){
            if(nxt == spa[x][0]) continue;
            spa[nxt][0] = x;
            dep[nxt] = dep[x] + 1;
            self(self, nxt);
        }
    };
    for(int i = 0; i < n; ++i){
        if(!dep[i]){
            dep[i] = 1;
            spa[i][0] = i;
            dfs(dfs, i);
        }
    }

    vector<int> cnt(n);
    gr = Dsu(n);
    for(int i = 0; i < q; ++i){
        int x = que[i][1], y = que[i][2];
        if(dep[x] > dep[y]) swap(x, y);

        if(que[i][0] == 1){
            if(gr.unite(x, y)){
                continue;
            }

            while(dep[y] > dep[x]){
                cnt[y] = 1;
                y = spa[y][0];
            }
            while(x != y){
                cnt[x] = cnt[y] = 1;
                x = spa[x][0], y = spa[y][0];
            }
        }
        else{
            if(gr.fd(x) != gr.fd(y)){
                cout << "-1\n";
                continue;
            }

            int ans = 0;
            // cout << x << ' ' << y << ' ' << dep[x] << ' ' << dep[y] << endl;
            while(dep[y] > dep[x]){
                // cout << x << ' ' << y << endl;
                ans += !cnt[y];
                y = spa[y][0];
            }
            while(x != y){
                ans += !cnt[x] + !cnt[y];
                x = spa[x][0], y = spa[y][0];
            }

            cout << ans << '\n';
        }
    }
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 6 ms 720 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 5 ms 832 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 49616 KB Output is correct
2 Correct 239 ms 49536 KB Output is correct
3 Execution timed out 2092 ms 52476 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 49728 KB Output is correct
2 Correct 213 ms 49504 KB Output is correct
3 Execution timed out 2043 ms 51656 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 42828 KB Output is correct
2 Correct 150 ms 42664 KB Output is correct
3 Execution timed out 2077 ms 44708 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 6 ms 720 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 5 ms 832 KB Output is correct
9 Correct 142 ms 49616 KB Output is correct
10 Correct 239 ms 49536 KB Output is correct
11 Execution timed out 2092 ms 52476 KB Time limit exceeded
12 Halted 0 ms 0 KB -