Submission #1143619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143619		garam1732	Jail (JOI22_jail)	C++20	100 / 100	982 ms	369308 KiB

jail

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*4;
const ll MOD = 1e9+7;
const ll INF = 2e9;

vector<int> adj[MAXN], graph[MAXN*15];
int sp[20][MAXN], dep[MAXN];
int tmp[20][MAXN][2]; // type0: i->si->j, type1: i->tj->j
int cnt, deg[MAXN*15];
queue<int> q;

void dfs(int here, int par) {
    sp[0][here] = par;
    for(int there:adj[here]) {
        if(there^par) {
            dep[there] = dep[here]+1;
            dfs(there, here);
        }
    }
}

int lca(int a, int b) {
    if(dep[a]>dep[b]) swap(a,b);

    for(int j=19; j>=0; j--) {
        if(dep[a]<=dep[sp[j][b]]) b=sp[j][b];
    }

    if(a==b) return a;

    for(int j=19; j>=0; j--) {
        if(sp[j][a]!=sp[j][b]) a=sp[j][a], b=sp[j][b];
    }

    return sp[0][a];
}

void f(int v, int u, int s, int t) {
    int x = lca(s, t);
    if(x != s) s = sp[0][s];
    else {
        s = t;
        for(int j=19;j>=0;j--) {
            if(dep[sp[j][s]] > dep[x]) s=sp[j][s];
        }
    }
    //cout<<s<<bl<<t<<endl;

    x = lca(s, t);

    for(int j=19; j>=0; j--) {
        if(dep[sp[j][s]] >= dep[x]) {
            //if(v==0&&u==1)cout<<'!'<<j<<bl<<s<<endl;
            if(u) graph[v].push_back(tmp[j][s][u]);
            else graph[tmp[j][s][u]].push_back(v);
            s = sp[j][s];
        }
    }
    for(int j=19; j>=0; j--) {
        if(dep[sp[j][t]] >= dep[x]) {
            if(u) graph[v].push_back(tmp[j][t][u]);
            else graph[tmp[j][t][u]].push_back(v);
            t = sp[j][t];
        }
    }

    if(u) graph[v].push_back(tmp[0][x][u]);
    else graph[tmp[0][x][u]].push_back(v);
}

// bool fnd(int x, int y) {
//     for(int t:graph[x]) {
//         if(t==y) return true;
//     }
//     return 0;
// }

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

    int T; cin>>T;
    while(T--) {
        int n; cin>>n;

        for(int i=1; i<=n; i++) {
            adj[i].clear();
        }

        for(int i=1; i<n; i++) {
            int a,b; cin>>a>>b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        adj[0].push_back(1);
        dfs(0, 0);

        int m; cin>>m; cnt = m;
        for(int j=0; j<20; j++) {
            for(int i=0; i<=n; i++) {
                tmp[j][i][0] = cnt++; tmp[j][i][1] = cnt++;
            }
        }

        for(int i=0; i<cnt; i++) {
            graph[i].clear(); deg[i]=0;
        }

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

                //if(dep[i]+1 < (1<<j)) continue;
                graph[tmp[j-1][i][0]].push_back(tmp[j][i][0]);
                graph[tmp[j-1][sp[j-1][i]][0]].push_back(tmp[j][i][0]);
                graph[tmp[j][i][1]].push_back(tmp[j-1][i][1]);
                graph[tmp[j][i][1]].push_back(tmp[j-1][sp[j-1][i]][1]);
            }
        }

        for(int i=0; i<m; i++) {
            int s,t; cin>>s>>t;
            int x = lca(s,t);

            graph[i].push_back(tmp[0][s][0]);
            graph[tmp[0][t][1]].push_back(i);

            f(i, 0, s, t); f(i, 1, t, s);

            // for(int j=19; j>=0; j--) {
            //     if(dep[sp[j][s]]>=dep[x]) {
            //         graph[tmp[j][s][0]].push_back(i);
            //         graph[i].push_back(tmp[j][s][1]);
            //         s = sp[j][s];
            //     }
            // }
            // for(int j=19; j>=0; j--) {
            //     if(dep[sp[j][t]]>=dep[x]) {
            //         graph[tmp[j][t][0]].push_back(i);
            //         graph[i].push_back(tmp[j][t][1]);
            //         t = sp[j][t];
            //     }
            // }
        }//cout<<fnd(0,tmp[1][3][1])<<endl;

        for(int i=0; i<cnt; i++) {
            for(int j:graph[i]) deg[j]++;
        }

        for(int i=0; i<cnt; i++) {
            if(deg[i]==0) q.push(i);
        }

        while(q.size()) {
            int here=q.front(); q.pop(); cnt--;
            for(int x:graph[here]) {
                deg[x]--;
                if(deg[x]==0) q.push(x);
            }
        }
        
        cout<<(cnt?"No":"Yes")<<endl;
    }
}

• 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