Submission #1186679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186679		brinton	Jail (JOI22_jail)	C++20	60 / 100	5095 ms	50044 KiB

jail

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

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //start here
    int tt;cin >> tt;
    while(tt--){
        int N;cin >> N;
        vector<vector<int>> edges(N+1);
        for(int i = 0;i < N-1;i++){
            int u,v;cin >> u >> v;
            edges[u].push_back(v);
            edges[v].push_back(u);
        }
        vector<int> p(N+1,-1);
        vector<int> dep(N+1,-1);
        function<void(int,int,int)> dfs = [&](int cur,int par,int cdep){
            dep[cur] = cdep;
            for(auto nxt:edges[cur]){
                if(nxt == par)continue;
                p[nxt] = cur;
                dfs(nxt,cur,cdep+1);
            }
        };
        dfs(1,-1,1);
        
        vector<vector<int>> bj(__lg(N)+1,vector<int>(N+1));
        bj[0] = p;
        for(int i = 1;i <= __lg(N);i++){
            for(int s = 1;s <= N;s++){
                bj[i][s] = (bj[i-1][s]==-1?-1:bj[i-1][bj[i-1][s]]);
            }
        }
        auto jmp = [&](int a,int x){
            int lvl = 0;
            while(x){
                if(x&1) a = bj[lvl][a];
                x >>= 1;
                lvl++;
            }
            return a;
        };
        auto lca = [&](int a,int b){
            if(dep[a] < dep[b]) swap(a,b);
            // dep a > dep b
            a = jmp(a,dep[a]-dep[b]);
            if(a == b) return a;
            for(int i = __lg(N);i >= 0;i--){
                if(bj[i][a] != bj[i][b]){
                    a = bj[i][a];
                    b = bj[i][b];
                }
            }
            return p[a];
        };

        int Q;cin >> Q;
        vector<int> S(Q);
        vector<int> T(Q);
        for(int i = 0;i < Q;i++){
            cin >> S[i] >> T[i];
        }
        
        vector<int> nStart(N+1,-1);
        vector<int> nEnd(N+1,-1);
        for(int i = 0;i < Q;i++) nStart[S[i]] = i;
        for(int i = 0;i < Q;i++) nEnd[T[i]] = i;

        vector<int> block(Q,0);// end block
        vector<int> stuck(Q,0);// middle stuck

        vector<vector<int>> unblock(Q);
        vector<vector<int>> unstuck(Q);
        for(int i = 0;i < Q;i++){
            int top = lca(S[i],T[i]);
            // cout << S[i] << " to " << T[i] << endl;
            set<int> cvis;
            auto upd = [&](int cs){
                while(cs != -1 && dep[cs] >= dep[top]){
                    if(cvis.count(cs)) {
                        cs = p[cs];
                        continue;
                    }
                    // cout << "check " << cs << endl;
                    cvis.insert(cs);
                    if(nStart[cs] != -1 && cs != S[i]) {
                        stuck[i]++;
                        unstuck[nStart[cs]].push_back(i);
                    }
                    if(nEnd[cs] != -1 && cs != T[i]){
                        block[nEnd[cs]]++;
                        unblock[i].push_back(nEnd[cs]);
                    }
                    cs = p[cs];
                }
            };
            upd(S[i]);
            upd(T[i]);
        }

        queue<int> q;
        int cnt = 0;
        for(int i = 0;i < Q;i++) {
            if(block[i] == 0 && stuck[i] == 0) q.push(i);
        }
        // cout << "start" << endl;
        while(!q.empty()){
            int cur = q.front();
            // cout << cur << ": " << flush;
            q.pop();
            cnt++;
            for(auto i:unblock[cur]){
                // cout << i << " " << flush;
                block[i]--;
                if(block[i] == 0 && stuck[i] == 0) q.push(i);
            }
            for(auto i:unstuck[cur]){
                stuck[i]--;
                // cout << i << " " << flush;
                if(block[i] == 0 && stuck[i] == 0) q.push(i);
            }
        }
        cout << (cnt == Q?"Yes\n":"No\n");
    }

}

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