oj.uz

Submission #724993

# Submission time Handle Problem Language Result Execution time Memory
724993 2023-04-16T12:21:59 Z berr Jail (JOI22_jail) C++17
0 / 100
 5000 ms 29768 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);
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){
    return(abs(x-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];


    if(x==y) return sum;

    swap(x, y);

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

    sum++;
    return sum;
}

bool c(int x, int y){//  s1 e2    s2 e2
    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;
    
    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 dfs3(int v, int z){
    vis[v] = z;

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


}

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);
    }

    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 5 ms 11092 KB Output is correct
2 Correct 6 ms 11092 KB Output is correct
3 Correct 6 ms 11092 KB Output is correct
4 Correct 13 ms 11092 KB Output is correct
5 Correct 29 ms 11160 KB Output is correct
6 Correct 9 ms 11092 KB Output is correct
7 Correct 7 ms 11096 KB Output is correct
8 Correct 13 ms 11196 KB Output is correct
9 Correct 120 ms 13296 KB Output is correct
10 Correct 68 ms 29564 KB Output is correct
11 Correct 10 ms 11092 KB Output is correct
12 Correct 61 ms 11172 KB Output is correct
13 Execution timed out 5009 ms 29768 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11092 KB Output is correct
2 Correct 6 ms 11092 KB Output is correct
3 Correct 7 ms 11160 KB Output is correct
4 Incorrect 9 ms 11092 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 11092 KB Output is correct
2 Correct 7 ms 11092 KB Output is correct
3 Correct 6 ms 11092 KB Output is correct
4 Correct 7 ms 11092 KB Output is correct
5 Correct 11 ms 11092 KB Output is correct
6 Incorrect 6 ms 11092 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11092 KB Output is correct
2 Correct 6 ms 11092 KB Output is correct
3 Correct 6 ms 11092 KB Output is correct
4 Correct 13 ms 11092 KB Output is correct
5 Correct 29 ms 11160 KB Output is correct
6 Correct 9 ms 11092 KB Output is correct
7 Correct 7 ms 11096 KB Output is correct
8 Correct 13 ms 11196 KB Output is correct
9 Correct 120 ms 13296 KB Output is correct
10 Correct 68 ms 29564 KB Output is correct
11 Correct 10 ms 11092 KB Output is correct
12 Correct 61 ms 11172 KB Output is correct
13 Execution timed out 5009 ms 29768 KB Time limit exceeded
14 Halted 0 ms 0 KB -