Submission #724968

#	Time	Username	Problem	Language	Result	Execution time	Memory
724968		berr	Jail (JOI22_jail)	C++17	0 / 100	12 ms	8276 KiB

jail

    #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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23