oj.uz

Submission #724999

# Submission time Handle Problem Language Result Execution time Memory
724999 2023-04-16T12:28:41 Z berr Jail (JOI22_jail) C++17
0 / 100
 5000 ms 30224 KB 
#include <bits/stdc++.h>
using namespace std; 
const int N = 1e5 + 2e4 + 37;
vector<int> adj[N], adj2[N], adj3[N], s(N), e(N), ti(N), to(N), vis(N), de(N);
int par[N][18], cnt, flag;


bool ia(int x, int y){
    return ti[x] <= ti[y] && to[x] >= to[y];
}

int d(int x, int y){
    if(x == y) return 0;

    int sum = 0;

    if(ia(x, y)) swap(x, y);

    for (int i = 17; i >= 0; i--){
        if(!ia(par[x][i], y)){
            x = par[x][i];
            sum += 1<<i;
        }
    }

    sum++;
    x=par[x][0];



    swap(x, y);

    sum+=de[y]-de[x];
    return sum;
}

bool c(int x, int y){
    if( (d(s[x], e[x]) == (d(s[x], e[y])+ d(e[y], e[x])))) return 1;
    swap(x, y);
    return (d(s[x], e[x]) == (d(s[x], s[y])+ d(s[y], e[x])));
}
bool c2(int x, int y){
    if(d(s[x], e[x]) == d(s[x], s[y])+ d(s[y], e[y]) + d(e[y], e[x])) return 1;
    if(d(s[x], e[x]) == d(s[x], e[y])+ d(e[y], s[y]) + d(s[y], e[x])) return 1;
    return 0;
}

void dfs(int v, int p){
    par[v][0] = p;
    de[v]=de[p]+1;
    ti[v] = cnt++;
    
    for (auto i: adj[v]){
        if (i == p) continue;
        dfs(i, v);
    }

    to[v] = cnt++;
}

void dfs2(int v, int z){
    vis[v] = z;

    for (auto i: adj2[v]){
        if (vis[i]==z) flag = 0;
        else if(vis[i]<z) dfs2(i, z);
    }

    vis[v]=z+1;
}

void solve(){
    int n; cin >> n;
    cnt = 0;

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    de[0]=-1;
    dfs(0, 0);

    for (int i = 1; i < 18; i++){
        for(int l = 0; l < n; l++){
            par[l][i] = par[par[l][i-1]][i-1];
        }
    }

    flag = 1;

    int m; cin >> m;

    for (int i = 0; i < m; i++){
        cin >> s[i] >> e[i];
        s[i]--; e[i]--;
    }

    for (int i = 0; i < m; i++){
        for (int l = i+1; l < m; l++){
            if (c(i, l)) adj2[i].push_back(l);

            if (c(l, i)) adj2[l].push_back(i);

            if(c2(i, l)) flag = 0;
            if(c2(l, i)) flag = 0;
            

        }
    }

    for(int i = 0; i < n; i++){
        if(vis[i]==0) dfs2(i, n*i+1);
    }


    if(flag) cout << "Yes\n";
    else cout << "No\n";

    for (int i = 0; i < n; i++){
        adj[i].clear();
        adj2[i].clear();
        vis[i] = 0;
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
        
    int t; cin>>t;

    while(t--){
        solve();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct
4 Correct 15 ms 11644 KB Output is correct
5 Correct 32 ms 11604 KB Output is correct
6 Correct 7 ms 11604 KB Output is correct
7 Correct 7 ms 11664 KB Output is correct
8 Correct 175 ms 11660 KB Output is correct
9 Correct 4933 ms 13780 KB Output is correct
10 Correct 257 ms 30224 KB Output is correct
11 Correct 44 ms 11628 KB Output is correct
12 Correct 1507 ms 11708 KB Output is correct
13 Execution timed out 5057 ms 29340 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11604 KB Output is correct
2 Correct 7 ms 11604 KB Output is correct
3 Correct 7 ms 11604 KB Output is correct
4 Incorrect 8 ms 11660 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11604 KB Output is correct
2 Correct 7 ms 11604 KB Output is correct
3 Correct 7 ms 11604 KB Output is correct
4 Incorrect 8 ms 11660 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11604 KB Output is correct
2 Correct 7 ms 11604 KB Output is correct
3 Correct 7 ms 11604 KB Output is correct
4 Incorrect 8 ms 11660 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11604 KB Output is correct
2 Correct 7 ms 11604 KB Output is correct
3 Correct 7 ms 11604 KB Output is correct
4 Incorrect 8 ms 11660 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Incorrect 7 ms 11604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct
4 Correct 15 ms 11644 KB Output is correct
5 Correct 32 ms 11604 KB Output is correct
6 Correct 7 ms 11604 KB Output is correct
7 Correct 7 ms 11664 KB Output is correct
8 Correct 175 ms 11660 KB Output is correct
9 Correct 4933 ms 13780 KB Output is correct
10 Correct 257 ms 30224 KB Output is correct
11 Correct 44 ms 11628 KB Output is correct
12 Correct 1507 ms 11708 KB Output is correct
13 Execution timed out 5057 ms 29340 KB Time limit exceeded
14 Halted 0 ms 0 KB -