Submission #48319

#	Time	Username	Problem	Language	Result	Execution time	Memory
48319		dalgerok	Special graph (IZhO13_specialg)	C++14	0 / 100	8 ms	5112 KiB

specialg

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


const int N = 2e5 + 5, M = 18;



int n, nxt[N], dp[M + 1][N], p[N], d[N], cnt[N], cl[N], num[N], lg[N];
int m, cur, sz, x[N], y[N], type[N], ans[N];
bool circle[N], used[N];
vector < int > g[N];

void dfs1(int v){
    for(int to : g[v]){
        if(to != dp[0][v]){
            d[to] = d[v] + 1;
            dfs1(to);
        }
    }
}

void dfs2(int v){
    num[v] = ++lg[sz];
    cl[v] = sz;
    if(!cl[nxt[v]]){
        dfs2(nxt[v]);
    }
}

int dsu_get(int v){
    return p[v] == v ? v : p[v] = dsu_get(p[v]);
}

/// X podveshivaem k Y
inline void dsu_unite(int x, int y){
    x = dsu_get(x);
    y = dsu_get(y);
    if(x == y){
        circle[x] = true;
        return;
    }
    p[x] = y;
}

inline int lca(int x, int y){
    for(int i = M; i >= 0; i--){
        if(d[dp[i][x]] >= d[y]){
            x = dp[i][x];
        }
    }
    return x;
}

int main(){
    freopen("specialg.in", "r", stdin);
    freopen("specialg.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> nxt[i];
        if(nxt[i]){
            cnt[nxt[i]]++;
        }
        p[i] = i;
    }
    queue < int > q;
    for(int i = 1; i <= n; i++){
        if(!cnt[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int v = q.front();
        q.pop();
        if(nxt[v]){
            cnt[nxt[v]]--;
            if(!cnt[nxt[v]]){
                q.push(nxt[v]);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(nxt[i] && !cnt[i]){
            g[nxt[i]].push_back(i);
            dp[0][i] = nxt[i];
        }
    }
    for(int i = 1; i <= n; i++){
        if(!dp[0][i]){
            dp[0][i] = i;
            dfs1(i);
        }
    }
    for(int j = 1; j <= M; j++){
        for(int i = 1; i <= n; i++){
            dp[j][i] = dp[j - 1][dp[j - 1][i]];
        }
    }
    for(int i = 1; i <= n; i++){
        if(!cl[i] && cnt[i]){
            sz++;
            dfs2(i);
        }
    }
    /*for(int i = 1; i <= n; i++){
        for(int j = 0; j <= M; j++){
            cout << dp[j][i] << " ";
        }
        cout << "\n";
    }
    return 0;*/
    cin >> m;
    for(int i = 1; i <= m; i++){
        cin >> type[i] >> x[i];
        if(type[i] == 1){
            used[x[i]] = true;
        }
        else{
            cin >> y[i];
        }
    }
    //return 0;
    for(int i = 1; i <= n; i++){
        if(!used[i] && nxt[i]){
            dsu_unite(i, nxt[i]);
        }
    }
    /*for(int i = 1; i <= n; i++){
        cout << dsu_get(i) << " ";
    }
    return 0;*/
    //cout << "\n";
    for(int i = m; i >= 1; i--){
        if(type[i] == 1){
            dsu_unite(x[i], nxt[x[i]]);
        }
        else{
            int px = dsu_get(x[i]),
                py = dsu_get(y[i]);
            if(px == py){
                if(lca(x[i], y[i]) == y[i]){
                    ans[i] = d[x[i]] - d[y[i]];
                }
                else{
                    //cout << "SOSI " << lca(x[i], y[i]) << " " << px << " " << py << " " << x[i] << " " << y[i] << "\n";
                    int z = dp[M][x[i]];
                    if(!cl[px] || !cl[z] || cl[z] != cl[y[i]]){
                        ans[i] = -1;
                    }
                    else{
                        ans[i] = d[x[i]] + (num[y[i]] - num[z]);
                        //cout << "CIRCLE = " << circle[px] << " " << num[y[i]] << " " << z << " " << num[z] << "\n";
                        if(!circle[px]){
                            if(num[z] < num[y[i]]){
                                if(num[px] < num[y[i]] && num[z] <= num[y[i]]){
                                    ans[i] = -1;
                                }
                            }
                            else{
                                if(num[px] < num[y[i]] || num[z] <= num[y[i]]){
                                    ans[i] = -1;
                                }
                                else{
                                    ans[i] += lg[cl[y[i]]];
                                }
                            }
                        }
                        else{
                            if(num[z] > num[y[i]]){
                                ans[i] += lg[cl[y[i]]];
                            }
                        }
                    }
                }
            }
            else{
                ans[i] = -1;
            }
        }
    }
    for(int i = 1; i <= m; i++){
        if(type[i] == 2){
            cout << ans[i] << "\n";
        }
    }
}
/**
6
3 3 4 5 6 4
6
2 1 6
2 1 4
2 1 2
1 3
2 1 6
2 1 4
2 1 3
*/

Compilation message (stderr)

specialg.cpp: In function 'int main()':
specialg.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("specialg.in", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
specialg.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("specialg.out", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100