oj.uz

Submission #1043518

# Submission time Handle Problem Language Result Execution time Memory
1043518 2024-08-04T10:32:24 Z vladilius Jail (JOI22_jail) C++17
5 / 100
 5000 ms 92164 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);
        
        for (int i = 1; i <= n; i++) pos[i] = 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 6 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 5 ms 33252 KB Output is correct
4 Correct 11 ms 33272 KB Output is correct
5 Correct 21 ms 33288 KB Output is correct
6 Correct 7 ms 33180 KB Output is correct
7 Correct 6 ms 33116 KB Output is correct
8 Correct 7 ms 33208 KB Output is correct
9 Correct 26 ms 35000 KB Output is correct
10 Correct 57 ms 65872 KB Output is correct
11 Correct 9 ms 33116 KB Output is correct
12 Correct 24 ms 33300 KB Output is correct
13 Correct 94 ms 71764 KB Output is correct
14 Correct 83 ms 72040 KB Output is correct
15 Correct 119 ms 76880 KB Output is correct
16 Correct 203 ms 92164 KB Output is correct
17 Correct 119 ms 79964 KB Output is correct
18 Correct 89 ms 72972 KB Output is correct
19 Correct 108 ms 78196 KB Output is correct
20 Correct 105 ms 78160 KB Output is correct
21 Correct 108 ms 79184 KB Output is correct
22 Correct 67 ms 69204 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Correct 5 ms 33160 KB Output is correct
3 Correct 5 ms 33116 KB Output is correct
4 Correct 5 ms 33116 KB Output is correct
5 Correct 9 ms 33264 KB Output is correct
6 Correct 8 ms 33116 KB Output is correct
7 Incorrect 5 ms 33116 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 5 ms 33252 KB Output is correct
4 Correct 11 ms 33272 KB Output is correct
5 Correct 21 ms 33288 KB Output is correct
6 Correct 7 ms 33180 KB Output is correct
7 Correct 6 ms 33116 KB Output is correct
8 Correct 7 ms 33208 KB Output is correct
9 Correct 26 ms 35000 KB Output is correct
10 Correct 57 ms 65872 KB Output is correct
11 Correct 9 ms 33116 KB Output is correct
12 Correct 24 ms 33300 KB Output is correct
13 Correct 94 ms 71764 KB Output is correct
14 Correct 83 ms 72040 KB Output is correct
15 Correct 119 ms 76880 KB Output is correct
16 Correct 203 ms 92164 KB Output is correct
17 Correct 119 ms 79964 KB Output is correct
18 Correct 89 ms 72972 KB Output is correct
19 Correct 108 ms 78196 KB Output is correct
20 Correct 105 ms 78160 KB Output is correct
21 Correct 108 ms 79184 KB Output is correct
22 Correct 67 ms 69204 KB Output is correct
23 Correct 6 ms 33116 KB Output is correct
24 Correct 5 ms 33116 KB Output is correct
25 Correct 6 ms 33236 KB Output is correct
26 Execution timed out 5044 ms 33116 KB Time limit exceeded
27 Halted 0 ms 0 KB -