oj.uz

Submission #1043513

# Submission time Handle Problem Language Result Execution time Memory
1043513 2024-08-04T10:27:17 Z vladilius Jail (JOI22_jail) C++17
5 / 100
 5000 ms 1048576 KB 
#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
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];
        }
        
        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 <= n; i++) a[i] = b[i] = 0;
        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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33116 KB Output is correct
2 Correct 6 ms 33112 KB Output is correct
3 Correct 6 ms 33116 KB Output is correct
4 Correct 10 ms 33116 KB Output is correct
5 Correct 17 ms 33112 KB Output is correct
6 Correct 5 ms 33124 KB Output is correct
7 Correct 5 ms 33192 KB Output is correct
8 Correct 6 ms 33124 KB Output is correct
9 Correct 24 ms 35144 KB Output is correct
10 Correct 66 ms 65632 KB Output is correct
11 Correct 8 ms 33128 KB Output is correct
12 Correct 29 ms 33308 KB Output is correct
13 Correct 107 ms 71760 KB Output is correct
14 Correct 78 ms 71904 KB Output is correct
15 Correct 106 ms 76884 KB Output is correct
16 Correct 211 ms 92240 KB Output is correct
17 Correct 115 ms 79996 KB Output is correct
18 Correct 87 ms 72984 KB Output is correct
19 Correct 107 ms 78176 KB Output is correct
20 Correct 101 ms 78168 KB Output is correct
21 Correct 96 ms 79184 KB Output is correct
22 Correct 63 ms 69204 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 5 ms 33184 KB Output is correct
4 Runtime error 454 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 5 ms 33184 KB Output is correct
4 Runtime error 454 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 5 ms 33184 KB Output is correct
4 Runtime error 454 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 5 ms 33184 KB Output is correct
4 Runtime error 454 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33116 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 4 ms 33116 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 8 ms 33268 KB Output is correct
6 Correct 5 ms 33160 KB Output is correct
7 Execution timed out 5068 ms 33116 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33116 KB Output is correct
2 Correct 6 ms 33112 KB Output is correct
3 Correct 6 ms 33116 KB Output is correct
4 Correct 10 ms 33116 KB Output is correct
5 Correct 17 ms 33112 KB Output is correct
6 Correct 5 ms 33124 KB Output is correct
7 Correct 5 ms 33192 KB Output is correct
8 Correct 6 ms 33124 KB Output is correct
9 Correct 24 ms 35144 KB Output is correct
10 Correct 66 ms 65632 KB Output is correct
11 Correct 8 ms 33128 KB Output is correct
12 Correct 29 ms 33308 KB Output is correct
13 Correct 107 ms 71760 KB Output is correct
14 Correct 78 ms 71904 KB Output is correct
15 Correct 106 ms 76884 KB Output is correct
16 Correct 211 ms 92240 KB Output is correct
17 Correct 115 ms 79996 KB Output is correct
18 Correct 87 ms 72984 KB Output is correct
19 Correct 107 ms 78176 KB Output is correct
20 Correct 101 ms 78168 KB Output is correct
21 Correct 96 ms 79184 KB Output is correct
22 Correct 63 ms 69204 KB Output is correct
23 Correct 5 ms 33112 KB Output is correct
24 Correct 5 ms 33116 KB Output is correct
25 Correct 5 ms 33184 KB Output is correct
26 Runtime error 454 ms 1048576 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -