oj.uz

Submission #1046650

# Submission time Handle Problem Language Result Execution time Memory
1046650 2024-08-06T19:44:00 Z _8_8_ Jail (JOI22_jail) C++17
10 / 100
 1455 ms 398400 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) {
    if(!is(l,v) || (l == v && ok)) return;
    for(int i = b;i >= 0;i--) {
        if(!is(up[v][i],l)) {
            G[id].push_back(t[v][i]);
            v = up[v][i];
        }
    }
    if(ok)G[id].push_back(t[v][1]);
    else{
        G[id].push_back(t[v][0]);
    }
}
void add_(int v,int l,int id,bool ok) {
    // 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 127580 KB Output is correct
3 Correct 16 ms 127696 KB Output is correct
4 Correct 44 ms 127880 KB Output is correct
5 Correct 71 ms 127864 KB Output is correct
6 Correct 19 ms 128092 KB Output is correct
7 Correct 19 ms 128092 KB Output is correct
8 Correct 20 ms 127968 KB Output is correct
9 Correct 144 ms 139036 KB Output is correct
10 Correct 1000 ms 326468 KB Output is correct
11 Correct 27 ms 127580 KB Output is correct
12 Correct 83 ms 127900 KB Output is correct
13 Correct 899 ms 328284 KB Output is correct
14 Correct 854 ms 328512 KB Output is correct
15 Correct 1184 ms 350016 KB Output is correct
16 Correct 1455 ms 398400 KB Output is correct
17 Correct 1127 ms 362820 KB Output is correct
18 Correct 962 ms 325852 KB Output is correct
19 Correct 1096 ms 331584 KB Output is correct
20 Correct 1106 ms 345824 KB Output is correct
21 Correct 1088 ms 354068 KB Output is correct
22 Correct 865 ms 325952 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 127540 KB Output is correct
2 Correct 17 ms 127580 KB Output is correct
3 Correct 20 ms 128088 KB Output is correct
4 Correct 20 ms 128084 KB Output is correct
5 Correct 19 ms 127848 KB Output is correct
6 Correct 19 ms 128096 KB Output is correct
7 Correct 19 ms 128092 KB Output is correct
8 Correct 20 ms 128052 KB Output is correct
9 Correct 21 ms 127836 KB Output is correct
10 Correct 23 ms 128088 KB Output is correct
11 Correct 22 ms 128088 KB Output is correct
12 Correct 18 ms 127836 KB Output is correct
13 Correct 20 ms 127984 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 127540 KB Output is correct
2 Correct 17 ms 127580 KB Output is correct
3 Correct 20 ms 128088 KB Output is correct
4 Correct 20 ms 128084 KB Output is correct
5 Correct 19 ms 127848 KB Output is correct
6 Correct 19 ms 128096 KB Output is correct
7 Correct 19 ms 128092 KB Output is correct
8 Correct 20 ms 128052 KB Output is correct
9 Correct 21 ms 127836 KB Output is correct
10 Correct 23 ms 128088 KB Output is correct
11 Correct 22 ms 128088 KB Output is correct
12 Correct 18 ms 127836 KB Output is correct
13 Correct 20 ms 127984 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 128092 KB Output is correct
17 Correct 20 ms 128096 KB Output is correct
18 Correct 19 ms 127876 KB Output is correct
19 Incorrect 18 ms 127576 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 127540 KB Output is correct
2 Correct 17 ms 127580 KB Output is correct
3 Correct 20 ms 128088 KB Output is correct
4 Correct 20 ms 128084 KB Output is correct
5 Correct 19 ms 127848 KB Output is correct
6 Correct 19 ms 128096 KB Output is correct
7 Correct 19 ms 128092 KB Output is correct
8 Correct 20 ms 128052 KB Output is correct
9 Correct 21 ms 127836 KB Output is correct
10 Correct 23 ms 128088 KB Output is correct
11 Correct 22 ms 128088 KB Output is correct
12 Correct 18 ms 127836 KB Output is correct
13 Correct 20 ms 127984 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 128092 KB Output is correct
17 Correct 20 ms 128096 KB Output is correct
18 Correct 19 ms 127876 KB Output is correct
19 Incorrect 18 ms 127576 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 127540 KB Output is correct
2 Correct 17 ms 127580 KB Output is correct
3 Correct 20 ms 128088 KB Output is correct
4 Correct 20 ms 128084 KB Output is correct
5 Correct 19 ms 127848 KB Output is correct
6 Correct 19 ms 128096 KB Output is correct
7 Correct 19 ms 128092 KB Output is correct
8 Correct 20 ms 128052 KB Output is correct
9 Correct 21 ms 127836 KB Output is correct
10 Correct 23 ms 128088 KB Output is correct
11 Correct 22 ms 128088 KB Output is correct
12 Correct 18 ms 127836 KB Output is correct
13 Correct 20 ms 127984 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 128092 KB Output is correct
17 Correct 20 ms 128096 KB Output is correct
18 Correct 19 ms 127876 KB Output is correct
19 Incorrect 18 ms 127576 KB Output isn't correct
20 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 18 ms 127580 KB Output is correct
3 Correct 21 ms 127676 KB Output is correct
4 Correct 22 ms 127580 KB Output is correct
5 Correct 31 ms 127644 KB Output is correct
6 Correct 18 ms 127872 KB Output is correct
7 Correct 27 ms 127836 KB Output is correct
8 Incorrect 23 ms 127580 KB Output isn't correct
9 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 127580 KB Output is correct
3 Correct 16 ms 127696 KB Output is correct
4 Correct 44 ms 127880 KB Output is correct
5 Correct 71 ms 127864 KB Output is correct
6 Correct 19 ms 128092 KB Output is correct
7 Correct 19 ms 128092 KB Output is correct
8 Correct 20 ms 127968 KB Output is correct
9 Correct 144 ms 139036 KB Output is correct
10 Correct 1000 ms 326468 KB Output is correct
11 Correct 27 ms 127580 KB Output is correct
12 Correct 83 ms 127900 KB Output is correct
13 Correct 899 ms 328284 KB Output is correct
14 Correct 854 ms 328512 KB Output is correct
15 Correct 1184 ms 350016 KB Output is correct
16 Correct 1455 ms 398400 KB Output is correct
17 Correct 1127 ms 362820 KB Output is correct
18 Correct 962 ms 325852 KB Output is correct
19 Correct 1096 ms 331584 KB Output is correct
20 Correct 1106 ms 345824 KB Output is correct
21 Correct 1088 ms 354068 KB Output is correct
22 Correct 865 ms 325952 KB Output is correct
23 Correct 16 ms 127540 KB Output is correct
24 Correct 17 ms 127580 KB Output is correct
25 Correct 20 ms 128088 KB Output is correct
26 Correct 20 ms 128084 KB Output is correct
27 Correct 19 ms 127848 KB Output is correct
28 Correct 19 ms 128096 KB Output is correct
29 Correct 19 ms 128092 KB Output is correct
30 Correct 20 ms 128052 KB Output is correct
31 Correct 21 ms 127836 KB Output is correct
32 Correct 23 ms 128088 KB Output is correct
33 Correct 22 ms 128088 KB Output is correct
34 Correct 18 ms 127836 KB Output is correct
35 Correct 20 ms 127984 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 128092 KB Output is correct
39 Correct 20 ms 128096 KB Output is correct
40 Correct 19 ms 127876 KB Output is correct
41 Incorrect 18 ms 127576 KB Output isn't correct
42 Halted 0 ms 0 KB -