Submission #1046650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046650		_8_8_	Jail (JOI22_jail)	C++17	10 / 100	1455 ms	398400 KiB

jail

#include <bits/stdc++.h>

 
using namespace std;
    
typedef long long ll;
const int  N = 24e4 + 2, MOD = (int)1e9+7;

int n,x[N],y[N],m,it = 1,it1 = 1,s[N],f[N];
vector<int> g[N],G[N * 20];
int up[N][20],t[N][20],t1[N][20],tin[N],tout[N],timer = 0;
const int b = 18;
void dfs(int v,int pr) {
    tin[v] = ++timer;
    up[v][0] = pr;
    if(!x[v]) {
        t[v][0] = ++it;
    } else {
        t[v][0] = x[v];
    }
    if(!y[v]) {
        t1[v][0] = ++it;
    } else {
        t1[v][0] = y[v];
    }
    for(int i = 1;i <= b;i++) {
        up[v][i] = up[up[v][i-1]][i-1];
        t[v][i] = ++it;
        t1[v][i] = ++it;
        // cout << t[v][i] << ' ' << t[v][i - 1] << "\n" ;
        // cout << t[v][i] << ' ' << t[up[v][i-1]][i - 1] << '\n';
        G[t[v][i]].push_back(t[v][i-1]);G[t[v][i]].push_back(t[up[v][i-1]][i-1]);
        G[t1[v][i-1]].push_back(t1[v][i]);G[t1[up[v][i-1]][i-1]].push_back(t1[v][i]);
    }
    for(int to:g[v]) {
        if(to == pr) continue;
        dfs(to,v);  
    }
    tout[v] = ++timer;
}
int vis[N * 20];
bool ans = 1;
void go(int v) {
    vis[v] = 1;
    for(int to:G[v]) {
        if(!vis[to]) {
            // cout << v << ' ' << to << '\n';
            go(to);
        } else {
            if(vis[to] == 1) {
                ans = 0;
            }
        }
    }
    vis[v] = 2;
}
bool is(int v,int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int lca(int v,int u) {
    if(is(v,u)) return v;
    if(is(u,v)) return u;
    for(int i = b;i >= 0;i--) {
        if(!is(up[v][i],u)) {
            v = up[v][i];
        }
    }
    return up[v][0];
}
void add(int v,int l,int id,bool ok) {
    if(!is(l,v) || (l == v && ok)) return;
    for(int i = b;i >= 0;i--) {
        if(!is(up[v][i],l)) {
            G[id].push_back(t[v][i]);
            v = up[v][i];
        }
    }
    if(ok)G[id].push_back(t[v][1]);
    else{
        G[id].push_back(t[v][0]);
    }
}
void add_(int v,int l,int id,bool ok) {
    // if(!is(l,v) || (l == v && ok)) return;
    // cout << v << ' ' << l << ' ' << id << ' ' << ok << '\n';
    // cout << v << ' ' << l << "x\n";
    for(int i = b;i >= 0;i--) {
        if(!is(up[v][i],l)) {
            // cout << t1[v][i] << ' ' << id << '\n';
            G[t1[v][i]].push_back(id);
            v = up[v][i];
        }
    }
    // cout << t1[v][1] << ' ' << id << '\n';
    // cout << "x\n";
    if(ok)G[t1[v][1]].push_back(id);
    else{
        G[t1[v][0]].push_back(id);
        // cout << t1[v][0] << ' ' << id << '\n';
    } 
}
void test() {
    ans = 1;
    timer = 0;
    cin >> n;
    for(int i = 1;i <= n;i++) {
        g[i].clear();
        x[i] = y[i] =0 ;
    }
    for(int i = 1;i <= n - 1;i++) {
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cin >> m;
    it = it1 = m;
    for(int i = 1;i <= m;i++) {
        cin >> s[i] >> f[i];
        y[f[i]] = x[s[i]] = i;
    }
    dfs(1,1);
    for(int i = 1;i <= m;i++) {
        int l = lca(s[i],f[i]);
        if(s[i] == l) {
            add(f[i],l,i,0);
        } else {
            add(up[s[i]][0],l,i,1);
            if(f[i] != l) add(f[i],l,i,1);
        }
        if(f[i] == l) {
            add_(s[i],l,i,0);
        } else {
            add_(up[f[i]][0],l,i,1);
            if(s[i] != l) add_(s[i],l,i,1);
        }
    }
    for(int i = 1;i <= it;i++) {
        if(!vis[i]) {
            go(i);
        }
    }
    cout << (ans ? "Yes\n":"No\n");
    for(int i = 1;i <= it;i++) {
        G[i].clear();
        vis[i] =0;
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    cin >> t;
    while(t--) {
        test();
    }
}

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