oj.uz

Submission #781410

# Submission time Handle Problem Language Result Execution time Memory
781410 2023-07-13T05:37:20 Z 이동현(#10013) JOI15_road_development (JOI15_road_development) C++14
10 / 100
 2000 ms 56160 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;
    }
};

struct Seg{
    int n;
    vector<int> tr, chk;
    Seg(int N){
        n = N + 4;
        tr.resize(n * 4 + 4);
        chk.resize(n * 4 + 4);
    }
    void push(int x, int s, int e, int ps, int pe){
        // if(pe < s || ps > e) return;
        // if(ps <= s && pe >= e){
        //     chk[x] = 1;
        //     tr[x] = e - s + 1;
        //     return;
        // }
        // int m = s + e >> 1;
        // push(x * 2, s, m, ps, pe);
        // push(x * 2 + 1, m + 1, e, ps, pe);
        // if(chk[x]) tr[x] = e - s + 1;
        // else tr[x] = tr[x * 2] + tr[x * 2 + 1];
        // assert(ps == pe);
        chk[ps] = 1;
    }
    int get(int x, int s, int e, int fs, int fe){
        // if(fe < s || fs > e || fs > fe) return 0;
        // if(chk[x]) return min(fe, e) - max(fs, s) + 1;
        // if(fs <= s && fe >= e) return tr[x];
        // int m = s + e >> 1;
        // return get(x * 2, s, m, fs, fe) + get(x * 2 + 1, m + 1, e, fs, fe);
        // assert(fs == fe);
        return chk[fs];
    }
};

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), sz(n), up(n), in(n);
    vector<vector<int>> spa(n, vector<int>(20));
    int inN = 0;
    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);
            sz[x] += sz[nxt];
        }
        sz[x] += 1;
    };
    for(int i = 0; i < n; ++i){
        if(!dep[i]){
            dep[i] = 1;
            spa[i][0] = i;
            dfs(dfs, i);
        }
    }

    for(int j = 1; j < 20; ++j){
        for(int i = 0; i < n; ++i){
            spa[i][j] = spa[spa[i][j - 1]][j - 1];
        }
    }

    auto dfshld = [&](auto&&self, int x)->void{
        in[x] = ++inN;
        for(int i = 0; i < (int)way[x].size(); ++i){
            if(way[x][i] == spa[x][0]){
                swap(way[x][i], way[x].back());
                way[x].pop_back();
                break;
            }
        }
        for(int i = 1; i < (int)way[x].size(); ++i){
            if(sz[way[x][i]] > sz[way[x][0]]){
                swap(way[x][i], way[x][0]);
            }
        }
        for(int i = 0; i < (int)way[x].size(); ++i){
            // if(!i) up[way[x][i]] = up[x];
            // else up[way[x][i]] = way[x][i];
            up[way[x][i]] = way[x][i];
            self(self, way[x][i]);
        }
    };
    for(int i = 0; i < n; ++i){
        if(i == spa[i][0]){
            up[i] = i;
            dfshld(dfshld, i);
        }
    }

    vector<int> cnt(n);
    gr = Dsu(n);

    auto getlca = [&](int x, int y){
        if(dep[x] > dep[y]) swap(x, y);
        for(int i = 19; i >= 0; --i){
            if(dep[y] - (1 << i) >= dep[x]){
                y = spa[y][i];
            }
        }
        if(x == y) return x;
        for(int i = 19; i >= 0; --i){
            if(spa[x][i] != spa[y][i]){
                x = spa[x][i];
                y = spa[y][i];
            }
        }
        return spa[x][0];
    };

    Seg tr(n + 4);
    for(int i = 0; i < q; ++i){
        int x = que[i][1], y = que[i][2];

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

            int lca = getlca(x, y);
            while(x != lca){
                int u = up[x];
                if(dep[u] <= dep[lca]) u = way[lca][0];
                tr.push(1, 1, n, in[u], in[x]);
                x = spa[u][0];
            }
            while(y != lca){
                int u = up[y];
                if(dep[u] <= dep[lca]) u = way[lca][0];
                tr.push(1, 1, n, in[u], in[y]);
                y = spa[u][0];
            }
        }
        else{
            if(gr.fd(x) != gr.fd(y)){
                cout << "-1\n";
                continue;
            }

            int lca = getlca(x, y);
            int ans = dep[x] + dep[y] - dep[lca] * 2;
            while(x != lca){
                int u = up[x];
                if(dep[u] <= dep[lca]) u = way[lca][0];
                ans -= tr.get(1, 1, n, in[u], in[x]);
                x = spa[u][0];
            }
            while(y != lca){
                int u = up[y];
                if(dep[u] <= dep[lca]) u = way[lca][0];
                ans -= tr.get(1, 1, n, in[u], in[y]);
                y = spa[u][0];
            }

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 9 ms 852 KB Output is correct
4 Correct 9 ms 852 KB Output is correct
5 Correct 2 ms 800 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 7 ms 852 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 53820 KB Output is correct
2 Correct 376 ms 53520 KB Output is correct
3 Execution timed out 2058 ms 56160 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 53704 KB Output is correct
2 Correct 320 ms 53528 KB Output is correct
3 Execution timed out 2084 ms 55436 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 48044 KB Output is correct
2 Correct 228 ms 47932 KB Output is correct
3 Execution timed out 2064 ms 49680 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 9 ms 852 KB Output is correct
4 Correct 9 ms 852 KB Output is correct
5 Correct 2 ms 800 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 7 ms 852 KB Output is correct
9 Correct 204 ms 53820 KB Output is correct
10 Correct 376 ms 53520 KB Output is correct
11 Execution timed out 2058 ms 56160 KB Time limit exceeded
12 Halted 0 ms 0 KB -