제출 #908546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
908546		GrindMachine	특수한 그래프 (IZhO13_specialg)	C++17	100 / 100	51 ms	19268 KiB

specialg

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

reverse the order of queries, deal with addition of edges instead of removal of edges
what we have is a functional graph
when we root a cc of the graph at a cycle, we have a directed tree going into the cycle
do the same for all ccs
we have multiple forests, with root node = the cycle

for the ease of implementation, assume the tree is rooted away from the cycle (direction of edges are reversed)

for (u,v) to be connected in the directed graph, they also have to be connected in the undirected graph
use a dsu to maintain the ccs
if (u,v) dont belong to the same cc in the dsu, then there is no path

assume there is a path between (u,v)
from a given edge u, we can only go to its ancestor in the tree
if v does not belong to a cycle (i.e is not a root node), then just check if v is an ances of u (using in and out times)
if yes, then ans = depth[u]-depth[v]

what if v belongs to a cycle?
by going up from u, we should be able to reach the same cycle as v (ans = -1 otherwise)
find the first node that we would reach on the cycle
for each cycle, maintain a fenwick, where fenw[i] = 1 if the outgoing edge of the ith node in the cycle is activated
checking if there is a directed path from u --> v is now possible (with some casework)

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct fenwick {
    int siz;
    vector<T> tree;

    fenwick() {

    }

    fenwick(int n) {
        siz = n;
        tree = vector<T>(n + 1);
    }

    int lsb(int x) {
        return x & -x;
    }

    void build(vector<T> &a, int n) {
        for (int i = 1; i <= n; ++i) {
            int par = i + lsb(i);
            tree[i] += a[i];

            if (par <= siz) {
                tree[par] += tree[i];
            }
        }
    }

    void pupd(int i, T v) {
        while (i <= siz) {
            tree[i] += v;
            i += lsb(i);
        }
    }

    T sum(int i) {
        T res = 0;

        while (i) {
            res += tree[i];
            i -= lsb(i);
        }

        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }
};

struct DSU {
    vector<int> par, rankk, siz;

    DSU() {

    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        par = vector<int>(n + 1);
        rankk = vector<int>(n + 1);
        siz = vector<int>(n + 1);
        rep(i, n + 1) create(i);
    }

    void create(int u) {
        par[u] = u;
        rankk[u] = 0;
        siz[u] = 1;
    }

    int find(int u) {
        if (u == par[u]) return u;
        else return par[u] = find(par[u]);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (rankk[u] == rankk[v]) rankk[u]++;
        if (rankk[u] < rankk[v]) swap(u, v);

        par[v] = u;
        siz[u] += siz[v];
    }
};

vector<ll> adj[N];
vector<bool> vis(N);
vector<ll> tin(N), tout(N);
vector<ll> depth(N);
vector<ll> root(N);
ll timer = 1;

void dfs1(ll u, ll r){
    vis[u] = 1;
    tin[u] = timer++;
    root[u] = r;
    trav(v,adj[u]){
        if(vis[v]) conts;
        depth[v] = depth[u]+1;
        dfs1(v,r);
    }
    tout[u] = timer-1;
}

void solve(int test_case)
{
    ll n; cin >> n;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];

    rep1(i,n){
        if(!a[i]){
            a[i] = i;
        }
    }

    queue<ll> q;
    vector<bool> bad(n+5);
    vector<ll> indeg(n+5);

    rep1(i,n){
        adj[a[i]].pb(i);
        indeg[a[i]]++;
    }

    rep1(i,n){
        if(indeg[i] == 0){
            q.push(i);
        }
    }

    while(!q.empty()){
        ll u = q.front();
        q.pop();

        bad[u] = 1;
        indeg[a[u]]--;

        if(indeg[a[u]] == 0){
            q.push(a[u]);
        }
    }

    vector<ll> cyc_id(n+5), cyc_pos(n+5), cyc_siz(n+5);
    ll ptr = 0;

    rep1(i,n){
        if(bad[i] or vis[i]) conts;

        ll j = i;
        vector<ll> roots;
        ptr++;

        ll curr_pos = 1;

        while(!vis[j]){
            vis[j] = 1;
            roots.pb(j);
            cyc_id[j] = ptr;
            cyc_pos[j] = curr_pos++;
            j = a[j];
        }

        cyc_siz[ptr] = sz(roots);

        trav(r,roots){
            dfs1(r,r);
        }
    }

    fenwick<ll> fenw[ptr+5];
    rep1(i,ptr){
        fenw[i] = fenwick<ll>(cyc_siz[i]);
    }

    ll m; cin >> m;
    vector<array<ll,3>> queries(m+5);
    vector<bool> rem(n+5);

    rep1(i,m){
        ll t; cin >> t;
        if(t == 1){
            ll u; cin >> u;
            queries[i] = {t,u,-1};
            rem[u] = 1;
        }
        else{
            ll u,v; cin >> u >> v;
            queries[i] = {t,u,v};
        }
    }

    DSU dsu(n+5);

    auto activate = [&](ll u){
        dsu.merge(u,a[u]);
        if(!bad[u]){
            ll id = cyc_id[u];
            ll pos = cyc_pos[u];
            fenw[id].pupd(pos,1);
        }
    };

    rep1(i,n){
        if(!rem[i]){
            activate(i);
        }
    }

    vector<ll> ans(m+5);

    rev(i,m,1){
        auto [t,u,v] = queries[i];
        if(t == 1){
            activate(u);
        }
        else{
            if(!dsu.same(u,v)){
                ans[i] = -1;
                conts;
            }

            if(bad[v]){
                 if(!(tin[v] <= tin[u] and tout[v] >= tout[u])){
                    ans[i] = -1;
                    conts;
                }

                ans[i] = depth[u]-depth[v];
                conts;
            }

            ll rootu = root[u];
            if(cyc_id[rootu] != cyc_id[v]){
                ans[i] = -1;
                conts;
            }

            ans[i] = depth[u];

            ll id = cyc_id[rootu];
            ll l = cyc_pos[rootu], r = cyc_pos[v];

            if(l <= r){
                if(fenw[id].query(l,r-1) == r-l){
                    ans[i] += r-l;
                }
                else{
                    ans[i] = -1;
                }
            }
            else{
                ll siz = cyc_siz[id];
                ll sum = fenw[id].query(l,siz)+fenw[id].query(1,r-1);
                ll len = siz-l+r;
                if(sum == len){
                    ans[i] += len;
                }
                else{
                    ans[i] = -1;
                }
            }
        }
    }

    rep1(i,m){
        if(queries[i][0] == 2){
            cout << ans[i] << endl;
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

• Subtask 1: 100 / 100