oj.uz

Submission #546961

# Submission time Handle Problem Language Result Execution time Memory
546961 2022-04-09T05:01:06 Z ngrace Jail (JOI22_jail) C++14
72 / 100
 5000 ms 966224 KB 
#include <vector>
#include <iostream>
#include <utility>
#include <set>
#include <algorithm>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second
 
int N,M;
int anc=20;
v<v<int>> adj;
v<int> depth;
v<v<int>> par;
v<int> ps;
v<int> pe;
v<v<int>> num;
void dfs(int cur, int from){
    if(depth[cur]!=-1) return;
    depth[cur]=depth[from]+1;
    par[cur][0]=from;
    if(ps[cur]!=-1) num[cur][0]++;
    if(pe[cur]!=-1) num[cur][0]++;
    for(int it:adj[cur]) dfs(it, cur);
}
bool is_anc(int cur, int other){
    for(int i=anc-1; i>=0; i--){
        if(depth[par[cur][i]]>=depth[other]) cur=par[cur][i];
    }
    if(cur==other) return true;
    return false;
}
 
int lca(int a, int b){
    if(depth[a]<depth[b]) swap(a,b);
    for(int i=anc-1; i>=0; i--){
        if(depth[par[a][i]]>=depth[b]) a=par[a][i];
    }
    if(a==b) return a;
    for(int i=anc-1; i>=0; i--){
        if(par[a][i]!=par[b][i]){
            a=par[a][i];
            b=par[b][i];
        }
    }
    return par[a][0];
}

v<set<int>> diadj;
v<bool> prevrec;
v<bool> vis;
bool find_cycle(int cur){
    if(!vis[cur]){
        vis[cur]=true;
        prevrec[cur]=true;
        for(int it:diadj[cur]){
            if(!vis[it] && find_cycle(it)){
                return true;
            }
            else if(prevrec[it]){
                return true;
            }
        }
    }
    prevrec[cur]=false;
    return false;
}
 
int main(){
    int Q;
    cin>>Q;
    for(int q=0;q<Q;q++){
        cin>>N;
        adj=v<v<int>>(N);
        for(int i=0; i<N-1; i++){
            int a,b;
            cin>>a>>b;
            a--;
            b--;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
 
        cin>>M;
        v<pii> rooms(M);
        ps = v<int>(N,-1);
        pe = v<int>(N,-1);
        for(int i=0; i<M; i++){
            cin>>rooms[i].fi>>rooms[i].se;
            rooms[i].fi--;
            rooms[i].se--;
            ps[rooms[i].fi]=i;
            pe[rooms[i].se]=i;
        }


        depth=v<int>(N,-1);
        par=v<v<int>>(N,v<int>(anc,-1));
        num=v<v<int>>(N,v<int>(anc,0));
        dfs(0,0);
        for(int i=1; i<anc; i++){
            for(int j=0; j<N; j++){
                par[j][i]=par[par[j][i-1]][i-1];
                num[j][i]=num[par[j][i-1]][i-1]+num[j][i-1];
            }
        }


        bool cycle=false;
        diadj = v<set<int>>(M);
        for(int i=0; i<M; i++){
            int a=rooms[i].fi;
            int b=rooms[i].se;
            int l=lca(a,b);

            //if have quick way of checking if any are on the path between x and an ancestor of x then can do the while loops below faster with binary lifting
            while(true){
                for(int j=anc-1; j>=0; j--){
                    if(depth[par[a][j]]<depth[l]) continue;
                    if(num[a][j]==0) a=par[a][j];
                }
                if(ps[a]!=-1 && ps[a]!=i){
                    diadj[ps[a]].insert(i);
                    if(diadj[i].find(ps[a])!=diadj[i].end()){
                        cycle=true;
                        break;
                    }
                }
                if(pe[a]!=-1 && pe[a]!=i){
                    diadj[i].insert(pe[a]);
                    if(diadj[pe[a]].find(i)!=diadj[pe[a]].end()){
                        cycle=true;
                        break;
                    }
                }
                if(a==l) break;
                a=par[a][0];
            }
            if(cycle) break;
            while(b!=l){
                for(int j=anc-1; j>=0; j--){
                    if(depth[par[b][j]]<=depth[l]) continue;
                    if(num[b][j]==0) b=par[b][j];
                }
                if(ps[b]!=-1 && ps[b]!=i){
                    diadj[ps[b]].insert(i);
                    if(diadj[i].find(ps[b])!=diadj[i].end()){
                        cycle=true;
                        break;
                    }
                }
                if(pe[b]!=-1 && pe[b]!=i){
                    diadj[i].insert(pe[b]);
                    if(diadj[pe[b]].find(i)!=diadj[pe[b]].end()){
                        cycle=true;
                        break;
                    }
                }
                b=par[b][0];
            }
            if(cycle) break;
        }

        vis = v<bool>(M,false);
        prevrec = v<bool>(M,false);
        for(int i=0; i<M; i++){
            if(cycle) break;
            if(!vis[i] && find_cycle(i)){
                cycle=true;
                break;
            }
        }
 
        if(cycle) cout<<"No\n";
        else cout<<"Yes\n";
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 38 ms 340 KB Output is correct
5 Correct 76 ms 340 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 7 ms 560 KB Output is correct
9 Correct 169 ms 8124 KB Output is correct
10 Correct 179 ms 46032 KB Output is correct
11 Correct 17 ms 212 KB Output is correct
12 Correct 103 ms 364 KB Output is correct
13 Correct 1226 ms 166604 KB Output is correct
14 Correct 168 ms 44236 KB Output is correct
15 Correct 166 ms 42960 KB Output is correct
16 Correct 225 ms 46868 KB Output is correct
17 Execution timed out 5075 ms 966224 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 4 ms 348 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 4 ms 340 KB Output is correct
21 Correct 4 ms 340 KB Output is correct
22 Correct 4 ms 340 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 5 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 1 ms 212 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 4 ms 348 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 4 ms 340 KB Output is correct
21 Correct 4 ms 340 KB Output is correct
22 Correct 4 ms 340 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 5 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 7 ms 596 KB Output is correct
30 Correct 4 ms 340 KB Output is correct
31 Correct 4 ms 340 KB Output is correct
32 Correct 5 ms 340 KB Output is correct
33 Correct 4 ms 340 KB Output is correct
34 Correct 6 ms 340 KB Output is correct
35 Correct 12 ms 468 KB Output is correct
36 Correct 4 ms 340 KB Output is correct
37 Correct 4 ms 340 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 4 ms 348 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 4 ms 340 KB Output is correct
21 Correct 4 ms 340 KB Output is correct
22 Correct 4 ms 340 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 5 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 7 ms 596 KB Output is correct
30 Correct 4 ms 340 KB Output is correct
31 Correct 4 ms 340 KB Output is correct
32 Correct 5 ms 340 KB Output is correct
33 Correct 4 ms 340 KB Output is correct
34 Correct 6 ms 340 KB Output is correct
35 Correct 12 ms 468 KB Output is correct
36 Correct 4 ms 340 KB Output is correct
37 Correct 4 ms 340 KB Output is correct
38 Correct 154 ms 8112 KB Output is correct
39 Correct 200 ms 46072 KB Output is correct
40 Correct 108 ms 2896 KB Output is correct
41 Correct 109 ms 2868 KB Output is correct
42 Correct 101 ms 2944 KB Output is correct
43 Correct 102 ms 2884 KB Output is correct
44 Correct 34 ms 1044 KB Output is correct
45 Correct 164 ms 36516 KB Output is correct
46 Correct 159 ms 36580 KB Output is correct
47 Correct 142 ms 38356 KB Output is correct
48 Correct 150 ms 38420 KB Output is correct
49 Correct 145 ms 36592 KB Output is correct
50 Correct 151 ms 36592 KB Output is correct
51 Correct 147 ms 37036 KB Output is correct
52 Correct 140 ms 37144 KB Output is correct
53 Correct 28 ms 3204 KB Output is correct
54 Correct 190 ms 36588 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 18 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 4 ms 404 KB Output is correct
13 Correct 57 ms 316 KB Output is correct
14 Correct 103 ms 284 KB Output is correct
15 Correct 87 ms 340 KB Output is correct
16 Correct 202 ms 38104 KB Output is correct
17 Correct 226 ms 40864 KB Output is correct
18 Correct 261 ms 46284 KB Output is correct
19 Correct 237 ms 38036 KB Output is correct
20 Correct 181 ms 37720 KB Output is correct
21 Correct 218 ms 38120 KB Output is correct
22 Correct 223 ms 42376 KB Output is correct
23 Correct 196 ms 39928 KB Output is correct
24 Correct 584 ms 83444 KB Output is correct
25 Correct 343 ms 59720 KB Output is correct
26 Correct 596 ms 84144 KB Output is correct
27 Correct 391 ms 51556 KB Output is correct
28 Correct 404 ms 58520 KB Output is correct
29 Correct 382 ms 53700 KB Output is correct
30 Correct 313 ms 46568 KB Output is correct
31 Correct 320 ms 47440 KB Output is correct
32 Correct 314 ms 45156 KB Output is correct
33 Correct 309 ms 47536 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 38 ms 340 KB Output is correct
5 Correct 76 ms 340 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 7 ms 560 KB Output is correct
9 Correct 169 ms 8124 KB Output is correct
10 Correct 179 ms 46032 KB Output is correct
11 Correct 17 ms 212 KB Output is correct
12 Correct 103 ms 364 KB Output is correct
13 Correct 1226 ms 166604 KB Output is correct
14 Correct 168 ms 44236 KB Output is correct
15 Correct 166 ms 42960 KB Output is correct
16 Correct 225 ms 46868 KB Output is correct
17 Execution timed out 5075 ms 966224 KB Time limit exceeded
18 Halted 0 ms 0 KB -