oj.uz

Submission #1046647

# Submission time Handle Problem Language Result Execution time Memory
1046647 2024-08-06T19:41:44 Z _8_8_ Jail (JOI22_jail) C++17
10 / 100
 1449 ms 401216 KB 
#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 = 1) {
    for(int i = b;i >= 0;i--) {
        if(!is(up[v][i],l)) {
            G[id].push_back(t[v][i]);
            v = up[v][i];
        }
    }
    // cout << id << ' ' << t[v][1] << '\n';
    // cout << v << ' ' << l << '\n';
    if(ok)G[id].push_back(t[v][1]);
    else{
        G[id].push_back(t[v][0]);
        // cout << id << ' ' << t[v][0] << '\n';
    }
}
void add_(int v,int l,int id,bool ok = 1) {
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 127580 KB Output is correct
2 Correct 16 ms 127692 KB Output is correct
3 Correct 16 ms 127580 KB Output is correct
4 Correct 44 ms 128128 KB Output is correct
5 Correct 71 ms 128616 KB Output is correct
6 Correct 20 ms 128092 KB Output is correct
7 Correct 23 ms 128136 KB Output is correct
8 Correct 20 ms 128164 KB Output is correct
9 Correct 139 ms 140256 KB Output is correct
10 Correct 1041 ms 327748 KB Output is correct
11 Correct 27 ms 127836 KB Output is correct
12 Correct 82 ms 128852 KB Output is correct
13 Correct 896 ms 330236 KB Output is correct
14 Correct 912 ms 330592 KB Output is correct
15 Correct 1153 ms 351744 KB Output is correct
16 Correct 1449 ms 401216 KB Output is correct
17 Correct 1138 ms 364820 KB Output is correct
18 Correct 968 ms 328572 KB Output is correct
19 Correct 1089 ms 333872 KB Output is correct
20 Correct 1070 ms 348020 KB Output is correct
21 Correct 1135 ms 356196 KB Output is correct
22 Correct 765 ms 328104 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 127580 KB Output is correct
2 Correct 16 ms 127604 KB Output is correct
3 Correct 20 ms 128092 KB Output is correct
4 Correct 19 ms 127956 KB Output is correct
5 Correct 19 ms 128128 KB Output is correct
6 Correct 20 ms 128092 KB Output is correct
7 Correct 20 ms 128092 KB Output is correct
8 Correct 19 ms 128092 KB Output is correct
9 Correct 19 ms 127988 KB Output is correct
10 Correct 19 ms 128048 KB Output is correct
11 Correct 19 ms 128092 KB Output is correct
12 Correct 17 ms 128104 KB Output is correct
13 Correct 18 ms 128092 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 127580 KB Output is correct
2 Correct 16 ms 127604 KB Output is correct
3 Correct 20 ms 128092 KB Output is correct
4 Correct 19 ms 127956 KB Output is correct
5 Correct 19 ms 128128 KB Output is correct
6 Correct 20 ms 128092 KB Output is correct
7 Correct 20 ms 128092 KB Output is correct
8 Correct 19 ms 128092 KB Output is correct
9 Correct 19 ms 127988 KB Output is correct
10 Correct 19 ms 128048 KB Output is correct
11 Correct 19 ms 128092 KB Output is correct
12 Correct 17 ms 128104 KB Output is correct
13 Correct 18 ms 128092 KB Output is correct
14 Correct 17 ms 127580 KB Output is correct
15 Correct 17 ms 127580 KB Output is correct
16 Correct 20 ms 128088 KB Output is correct
17 Correct 19 ms 128092 KB Output is correct
18 Correct 20 ms 128144 KB Output is correct
19 Correct 16 ms 127704 KB Output is correct
20 Correct 20 ms 128092 KB Output is correct
21 Correct 20 ms 128088 KB Output is correct
22 Correct 19 ms 128092 KB Output is correct
23 Correct 16 ms 127708 KB Output is correct
24 Incorrect 19 ms 127836 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 127580 KB Output is correct
2 Correct 16 ms 127604 KB Output is correct
3 Correct 20 ms 128092 KB Output is correct
4 Correct 19 ms 127956 KB Output is correct
5 Correct 19 ms 128128 KB Output is correct
6 Correct 20 ms 128092 KB Output is correct
7 Correct 20 ms 128092 KB Output is correct
8 Correct 19 ms 128092 KB Output is correct
9 Correct 19 ms 127988 KB Output is correct
10 Correct 19 ms 128048 KB Output is correct
11 Correct 19 ms 128092 KB Output is correct
12 Correct 17 ms 128104 KB Output is correct
13 Correct 18 ms 128092 KB Output is correct
14 Correct 17 ms 127580 KB Output is correct
15 Correct 17 ms 127580 KB Output is correct
16 Correct 20 ms 128088 KB Output is correct
17 Correct 19 ms 128092 KB Output is correct
18 Correct 20 ms 128144 KB Output is correct
19 Correct 16 ms 127704 KB Output is correct
20 Correct 20 ms 128092 KB Output is correct
21 Correct 20 ms 128088 KB Output is correct
22 Correct 19 ms 128092 KB Output is correct
23 Correct 16 ms 127708 KB Output is correct
24 Incorrect 19 ms 127836 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 127580 KB Output is correct
2 Correct 16 ms 127604 KB Output is correct
3 Correct 20 ms 128092 KB Output is correct
4 Correct 19 ms 127956 KB Output is correct
5 Correct 19 ms 128128 KB Output is correct
6 Correct 20 ms 128092 KB Output is correct
7 Correct 20 ms 128092 KB Output is correct
8 Correct 19 ms 128092 KB Output is correct
9 Correct 19 ms 127988 KB Output is correct
10 Correct 19 ms 128048 KB Output is correct
11 Correct 19 ms 128092 KB Output is correct
12 Correct 17 ms 128104 KB Output is correct
13 Correct 18 ms 128092 KB Output is correct
14 Correct 17 ms 127580 KB Output is correct
15 Correct 17 ms 127580 KB Output is correct
16 Correct 20 ms 128088 KB Output is correct
17 Correct 19 ms 128092 KB Output is correct
18 Correct 20 ms 128144 KB Output is correct
19 Correct 16 ms 127704 KB Output is correct
20 Correct 20 ms 128092 KB Output is correct
21 Correct 20 ms 128088 KB Output is correct
22 Correct 19 ms 128092 KB Output is correct
23 Correct 16 ms 127708 KB Output is correct
24 Incorrect 19 ms 127836 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 127576 KB Output is correct
2 Correct 17 ms 127580 KB Output is correct
3 Correct 16 ms 127600 KB Output is correct
4 Correct 17 ms 127580 KB Output is correct
5 Correct 27 ms 127668 KB Output is correct
6 Correct 18 ms 128092 KB Output is correct
7 Correct 19 ms 128092 KB Output is correct
8 Correct 17 ms 127580 KB Output is correct
9 Correct 17 ms 127580 KB Output is correct
10 Incorrect 17 ms 127836 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 127580 KB Output is correct
2 Correct 16 ms 127692 KB Output is correct
3 Correct 16 ms 127580 KB Output is correct
4 Correct 44 ms 128128 KB Output is correct
5 Correct 71 ms 128616 KB Output is correct
6 Correct 20 ms 128092 KB Output is correct
7 Correct 23 ms 128136 KB Output is correct
8 Correct 20 ms 128164 KB Output is correct
9 Correct 139 ms 140256 KB Output is correct
10 Correct 1041 ms 327748 KB Output is correct
11 Correct 27 ms 127836 KB Output is correct
12 Correct 82 ms 128852 KB Output is correct
13 Correct 896 ms 330236 KB Output is correct
14 Correct 912 ms 330592 KB Output is correct
15 Correct 1153 ms 351744 KB Output is correct
16 Correct 1449 ms 401216 KB Output is correct
17 Correct 1138 ms 364820 KB Output is correct
18 Correct 968 ms 328572 KB Output is correct
19 Correct 1089 ms 333872 KB Output is correct
20 Correct 1070 ms 348020 KB Output is correct
21 Correct 1135 ms 356196 KB Output is correct
22 Correct 765 ms 328104 KB Output is correct
23 Correct 19 ms 127580 KB Output is correct
24 Correct 16 ms 127604 KB Output is correct
25 Correct 20 ms 128092 KB Output is correct
26 Correct 19 ms 127956 KB Output is correct
27 Correct 19 ms 128128 KB Output is correct
28 Correct 20 ms 128092 KB Output is correct
29 Correct 20 ms 128092 KB Output is correct
30 Correct 19 ms 128092 KB Output is correct
31 Correct 19 ms 127988 KB Output is correct
32 Correct 19 ms 128048 KB Output is correct
33 Correct 19 ms 128092 KB Output is correct
34 Correct 17 ms 128104 KB Output is correct
35 Correct 18 ms 128092 KB Output is correct
36 Correct 17 ms 127580 KB Output is correct
37 Correct 17 ms 127580 KB Output is correct
38 Correct 20 ms 128088 KB Output is correct
39 Correct 19 ms 128092 KB Output is correct
40 Correct 20 ms 128144 KB Output is correct
41 Correct 16 ms 127704 KB Output is correct
42 Correct 20 ms 128092 KB Output is correct
43 Correct 20 ms 128088 KB Output is correct
44 Correct 19 ms 128092 KB Output is correct
45 Correct 16 ms 127708 KB Output is correct
46 Incorrect 19 ms 127836 KB Output isn't correct
47 Halted 0 ms 0 KB -