Submission #1043504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043504		vladilius	Jail (JOI22_jail)	C++17	100 / 100	482 ms	89428 KiB

jail

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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

struct STG{
    vector<vector<int>> g;
    vector<int> a, b;
    int n, m, k;
    STG(int& ns, int& ms, vector<int>& as, vector<int>& bs){
        n = ns;
        m = ms;
        a = as;
        b = bs;
        g.resize(m + 8 * n + 1);
        build1(1, 1, n);
        k = m + 4 * n;
        build2(1, 1, 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);
    }
    vector<bool> used, seen;
    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 = (int) g.size() - 1;
        used.resize(nn + 1);
        seen.resize(nn + 1);
        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--){
        int n; cin>>n;
        vector<int> g[n + 1];
        for (int i = 1; i < n; i++){
            int x, y; cin>>x>>y;
            g[x].pb(y);
            g[y].pb(x);
        }
        int m; cin>>m;
        vector<int> s(m + 1), t(m + 1);
        for (int i = 1; i <= m; i++){
            cin>>s[i]>>t[i];
        }
        
        vector<int> sz(n + 1), h(n + 1), d(n + 1), p(n + 1);
        function<void(int, int)> fill = [&](int v, int pr){
            p[v] = pr;
            sz[v] = 1;
            for (int i: g[v]){
                if (sz[i]) 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);
        
        vector<int> head(n + 1), pos(n + 1);
        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);
        
        vector<int> a(n + 1), b(n + 1);
        for (int i = 1; i <= m; i++){
            a[pos[s[i]]] = i;
            b[pos[t[i]]] = i;
        }
        
        STG T(n, m, a, b);

        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);
                }
                T.add1(i, pos[head[y]] + (head[y] == s[i]), pos[y] - (y == s[i]));
                T.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);
            T.add1(i, pos[x] + (x == s[i]), pos[y] - (y == s[i]));
            T.add2(i, pos[x] + (x == t[i]), pos[y] - (y == t[i]));
        }
        
        cout<<((T.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