Submission #1043523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043523		vladilius	Jail (JOI22_jail)	C++17	100 / 100	631 ms	92264 KiB

jail

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const int N = 1.2e5;

vector<int> g[N + 1], G[9 * N];
int s[N + 1], t[N + 1], sz[N + 1], h[N + 1], p[N + 1], d[N + 1], head[N + 1], pos[N + 1], a[N + 1], b[N + 1], k, m, n;

void build1(int v, int tl, int tr){
    if (tl == tr){
        if (a[tl]) G[v + m].pb(a[tl]);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    build1(vv, tl, tm);
    build1(vv + 1, tm + 1, tr);
    G[v + m].pb(vv + m);
    G[v + m].pb(vv + m + 1);
}

void build2(int v, int tl, int tr){
    if (tl == tr){
        if (b[tl]) G[b[tl]].pb(v + k);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    build2(vv, tl, tm);
    build2(vv + 1, tm + 1, tr);
    G[vv + k].pb(v + k);
    G[vv + k + 1].pb(v + k);
}

void add1(int v, int tl, int tr, int& l, int& r, int& u){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        G[u].pb(v + m);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    add1(vv, tl, tm, l, r, u);
    add1(vv + 1, tm + 1, tr, l, r, u);
}
void add1(int u, int l, int r){
    if (l > r) return;
    add1(1, 1, n, l, r, u);
}

void add2(int v, int tl, int tr, int& l, int& r, int& u){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        G[v + k].pb(u);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    add2(vv, tl, tm, l, r, u);
    add2(vv + 1, tm + 1, tr, l, r, u);
}
void add2(int u, int l, int r){
    if (l > r) return;
    add2(1, 1, n, l, r, u);
}

bool used[9 * N], seen[9 * N];

bool dfs(int v){
    used[v] = seen[v] = 1;
    for (int i: G[v]){
        if (used[i]){
            if (seen[i]){
                return 0;
            }
            continue;
        }
        if (!dfs(i)) return 0;
    }
    seen[v] = 0;
    return 1;
}

bool check(){
    int nn = 9 * n;
    for (int i = 1; i < nn; i++) used[i] = seen[i] = 0;
    for (int i = 1; i <= nn; i++){
        if (!used[i]){
            if (!dfs(i)){
                return 0;
            }
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int tt; cin>>tt;
    while (tt--){
        cin>>n;
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1; i < n; i++){
            int x, y; cin>>x>>y;
            g[x].pb(y);
            g[y].pb(x);
        }
        cin>>m;
        for (int i = 1; i <= m; i++){
            cin>>s[i]>>t[i];
        }
        
        for (int i = 1; i <= n; i++) pos[i] = h[i] = a[i] = b[i] = 0;
        
        function<void(int, int)> fill = [&](int v, int pr){
            p[v] = pr;
            sz[v] = 1;
            for (int i: g[v]){
                if (i == pr) continue;
                d[i] = d[v] + 1;
                fill(i, v);
                if (sz[i] > sz[h[v]]){
                    h[v] = i;
                }
                sz[v] += sz[i];
            }
        };
        fill(1, 0);
        
        
        int timer = 0;
        function<void(int, int)> fill_hld = [&](int v, int k){
            head[v] = k;
            pos[v] = ++timer;
            if (!h[v]) return;
            fill_hld(h[v], k);
            for (int i: g[v]){
                if (pos[i]) continue;
                fill_hld(i, i);
            }
        };
        fill_hld(1, 1);
        
        for (int i = 1; i <= m; i++){
            a[pos[s[i]]] = i;
            b[pos[t[i]]] = i;
        }
        
        for (int i = 1; i < 9 * n; i++) G[i].clear();
        k = m + 4 * n;
        build1(1, 1, n);
        build2(1, 1, n);

        for (int i = 1; i <= m; i++){
            int x = s[i], y = t[i];
            while (head[x] != head[y]){
                if (d[head[x]] > d[head[y]]){
                    swap(x, y);
                }
                add1(i, pos[head[y]] + (head[y] == s[i]), pos[y] - (y == s[i]));
                add2(i, pos[head[y]] + (head[y] == t[i]), pos[y] - (y == t[i]));
                y = p[head[y]];
            }
            if (d[x] > d[y]) swap(x, y);
            add1(i, pos[x] + (x == s[i]), pos[y] - (y == s[i]));
            add2(i, pos[x] + (x == t[i]), pos[y] - (y == t[i]));
        }
        
        cout<<((check()) ? "Yes" : "No")<<"\n";
    }
}

• 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