제출 #567855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
567855		joshjms	Jail (JOI22_jail)	C++17	100 / 100	2318 ms	507148 KiB

jail

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

#pragma GCC optimize("Ofast")

#define int long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";

const long long mod = 1e9 + 7;

int n, a[120005], b[120005], m, s[120005], t[120005];
vector <int> g[120005];

int par[120005][20], in[120005], out[120005], tmr;
int node[120005][20][2], nodes;

vector <int> dirGraph[4800005];
pair <int,int> range[4800005];

int vis[4800005], flag;

void init() {
    cin >> n;
    for(int i = 1; i < n; i++)
        cin >> a[i] >> b[i];

    cin >> m;
    for(int i = 1; i <= m; i++)
        cin >> s[i] >> t[i];

    for(int i = 1; i <= n; i++) {
        g[i].clear();
        in[i] = out[i] = 0;
        for(int j = 0; j < 20; j++) par[i][j] = 0;
    }

    for(int i = 1; i < n; i++) {
        g[a[i]].pb(b[i]);
        g[b[i]].pb(a[i]);
    }

    in[0] = -1;
    out[0] = 1e18;

    tmr = 0;

    for(int i = 1; i <= 40 * n; i++) {
        dirGraph[i].clear();
        vis[i] = 0;
    }

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

void dfs(int v, int p) {
    par[v][0] = v;
    par[v][1] = p;

    for(int i = 2; i < 18; i++) 
        par[v][i] = par[par[par[v][i - 1]][1]][i - 1];

    in[v] = ++tmr;

    for(auto c : g[v]) if(c != p) 
        dfs(c, v);

    out[v] = ++tmr;
}

void findCycle(int v) {
    vis[v] = 1;

    // cout << "[" << v << "][" << range[v].fi << " " << range[v].se << "]" << (v % 2 ? "[S]" : "[T]") << "\n";
    for(auto c : dirGraph[v]) {
        if(vis[c] == 1) {flag = 1; return;}
        if(vis[c] == 0) findCycle(c);
    }
    vis[v] = 2;
}

void solve () {

    dfs(1, 0);

    // for(int i = 1; i <= n; i++) {
    //     for(int j = 0; j < 18; j++) {
    //         cout << par[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    nodes = 0;

    for(int i = 1; i <= n; i++) {
        node[i][0][0] = ++nodes;
        node[i][0][1] = ++nodes;

        range[node[i][0][0]] = range[node[i][0][1]] = {i, i};
    }

    for(int i = 1; i <= m; i++) {
        dirGraph[node[s[i]][0][0]].pb(node[t[i]][0][1]);
    }

    auto showNode = [&](int i, int j) {
        cout << "[" << i << " " << par[i][j] << "]\n";
        return;
    };

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < 18; j++) {
            node[i][j][0] = ++nodes;
            node[i][j][1] = ++nodes;
        }
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < 18; j++) {
            range[node[i][j][0]] = range[node[i][j][1]] = {i, par[i][j]};

            // showNode(i, j);
            // cout << "child: \n";
            // showNode(i, j - 1);
            // showNode(par[par[i][j - 1]][1], j - 1);
            // cout << "\n";

            // cout << "[" << i << " " << j << "] => " << node[i][j][0] << ", " << node[i][j][1] << "\n";

            dirGraph[node[i][j][0]].pb(node[i][j - 1][0]);
            if(dirGraph[node[i][j][0]].back() == 0) dirGraph[node[i][j][0]].pop_back();
            dirGraph[node[i][j][0]].pb(node[par[par[i][j - 1]][1]][j - 1][0]);
            if(dirGraph[node[i][j][0]].back() == 0) dirGraph[node[i][j][0]].pop_back();

            dirGraph[node[i][j - 1][1]].pb(node[i][j][1]);
            if(dirGraph[node[i][j - 1][1]].back() == 0) dirGraph[node[i][j - 1][1]].pop_back();
            dirGraph[node[par[par[i][j - 1]][1]][j - 1][1]].pb(node[i][j][1]);
            if(dirGraph[node[i][j - 1][1]].back() == 0) dirGraph[node[i][j - 1][1]].pop_back();
        }
    }

    auto lca = [&](int u, int v) {
        if(in[u] <= in[v] && out[u] >= out[v]) return u;
        if(in[v] <= in[u] && out[v] >= out[u]) return v;
        for(int i = 17; i >= 1; i--) {
            while(!(in[par[u][i]] <= in[v] && out[par[u][i]] >= out[v])) {
                u = par[u][i];
            }
        }
        return par[u][1];
    };

    for(int i = 1; i <= m; i++) {
        int LCA = lca(s[i], t[i]);

        // debug(s[i]);
        // debug(t[i]);

        // debug(LCA);

        if(LCA == s[i]) {
            int u, v;

            u = t[i], v = s[i];
            for(int j = 17; j >= 0; j--) {
                while(true) {
                    if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) break;
                    // cout << "[" << u << " -> " << par[u][j] << "]\n";
                    dirGraph[node[s[i]][0][0]].pb(node[u][j][0]);
                    u = par[par[u][j]][1];
                }
            }

            u = par[t[i]][1], v = par[s[i]][1];
            for(int j = 17; j >= 0; j--) {
                while(true) {
                    if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) break;
                    // cout << "[" << u << " -> " << par[u][j] << "]\n";
                    dirGraph[node[u][j][1]].pb(node[s[i]][0][0]);
                    u = par[par[u][j]][1];
                }
            }
        }
        else if(LCA == t[i]) {
            int u, v;

            u = par[s[i]][1], v = par[t[i]][1];
            for(int j = 17; j >= 0; j--) {
                 while(true) {
                    if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) break;
                    // cout << "[" << u << " -> " << par[u][j] << "]\n";
                    dirGraph[node[s[i]][0][0]].pb(node[u][j][0]);
                    u = par[par[u][j]][1];
                }
            }

            u = s[i], v = t[i];
            for(int j = 17; j >= 0; j--) {
                while(true) {
                    if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) break;
                    // cout << "[" << u << " -> " << par[u][j] << "]\n";
                    dirGraph[node[u][j][1]].pb(node[s[i]][0][0]);
                    u = par[par[u][j]][1];
                }
            }
        }
        else {
            int u, v;

            u = par[s[i]][1], v = par[LCA][1];
            for(int j = 17; j >= 0; j--) {
                 while(true) {
                    if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) break;
                    dirGraph[node[s[i]][0][0]].pb(node[u][j][0]);
                    u = par[par[u][j]][1];
                }
            }

            u = t[i], v = par[LCA][1];
            for(int j = 17; j >= 0; j--) {
                 while(true) {
                    if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) break;
                    dirGraph[node[s[i]][0][0]].pb(node[u][j][0]);
                    u = par[par[u][j]][1];
                }
            }

            u = par[t[i]][1], v = par[LCA][1];
            for(int j = 17; j >= 0; j--) {
                while(true) {
                    if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) break;
                    dirGraph[node[u][j][1]].pb(node[s[i]][0][0]);
                    u = par[par[u][j]][1];
                }
            }

            u = s[i], v = par[LCA][1];
            for(int j = 17; j >= 0; j--) {
                while(true) {
                    if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) break;
                    dirGraph[node[u][j][1]].pb(node[s[i]][0][0]);
                    u = par[par[u][j]][1];
                }
            }
        }
    }

    // int u = 2;
    // while(u != 1) {cout << u << " "; u = par[u][1];}

    // cout << "\n";

    // u = 12;
    // while(u != 1) {cout << u << " "; u = par[u][1];}

    // cout << "\n";

    flag = 0;

    // for(auto c : dirGraph[node[1][0][0]])
    //     cout << c << " ";
    // cout << "\n";

    for(int j = 17; j >= 0; j--) {
        for(int i = 1; i <= n; i++) {
            if(vis[node[i][0][0]] == 0) {
                findCycle(node[i][j][0]);
                if(flag) break;
            }
        }
    }
    

    if(flag) cout << "No\n";
    else cout << "Yes\n";
}

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

    int tc; cin >> tc;
    while(tc--) {
        init ();
        solve ();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

jail.cpp: In function 'void solve()':
jail.cpp:114:10: warning: variable 'showNode' set but not used [-Wunused-but-set-variable]
  114 |     auto showNode = [&](int i, int j) {
      |          ^~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23