oj.uz

Submission #724968

# Submission time Handle Problem Language Result Execution time Memory
724968 2023-04-16T11:54:36 Z berr Jail (JOI22_jail) C++17
0 / 100
 12 ms 8276 KB 
    #include <bits/stdc++.h>
    using namespace std; 
    const int N = 1e5 + 2e4 + 37;
    vector<int> adj[N], adj2[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
        return(d(s[x], e[x]) == (d(s[x], e[y])+ d(e[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 (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++){
        

         /*   cout<<i<<" : ";
            for(auto l: adj2[i]) cout<<l<<" ";
                cout<<"\n";
           
    */
            dfs2(i, 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 4 ms 8276 KB Output is correct
2 Correct 5 ms 8276 KB Output is correct
3 Correct 5 ms 8276 KB Output is correct
4 Incorrect 12 ms 8276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

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