oj.uz

Submission #632630

# Submission time Handle Problem Language Result Execution time Memory
632630 2022-08-20T13:18:26 Z Mahdi Jail (JOI22_jail) C++17
72 / 100
 5000 ms 736192 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef pair<int, int> pii;
typedef long long ll;
const int N=5e5+5;
int n, m, nm, sq, s[N], t[N], dis[N], pr[N][18];
vector<int>g[N], h[3*N], nd;
bool mk[3*N];
pii st[N];
     
void dfs(const int &v, const int &p=-1){
    for(int u: g[v]){
        if(u!=p){
            pr[u][0]=v;
            for(int i=1;i<17;++i)
                pr[u][i]=pr[pr[u][i-1]][i-1];
            dis[u]=dis[v]+1;
            dfs(u, v);
        }   
    }
}
     
inline int par(int v, int p){
    for(int i=0;p>0;++i){
        if(p&1)
            v=pr[v][i];
        p>>=1;
    }
    return v;
}
     
inline int lca(int u, int v){
    u=par(u, dis[u]-dis[v]);
    v=par(v, dis[v]-dis[u]);
    if(u==v)
        return v;
    for(int i=16;i>=0;--i){
        if(pr[u][i]!=pr[v][i]){
            v=pr[v][i];
            u=pr[u][i];
        }
    }
    return pr[v][0];
}
     
void pre(){
    nm=2*n+m;
    for(int i=0;i<nm;++i)
        h[i].clear();
    for(int v=0;v<n;++v){
        int u=v, w=par(v, sq);
        while(u!=w){
            if(s[u]!=-1)
                h[s[u]+2*n].push_back(v);
            if(t[u]!=-1)
                h[v+n].push_back(t[u]+2*n);
            u=pr[u][0];
        }
    }
}
     
inline void opr(int i, int v, int u){
    int w=lca(u, v);
    int x=pr[v][0];
    int y=par(x, sq);
    while(dis[y]>=dis[w]){
        h[x].push_back(i);
        x=y;
        y=par(x, sq);
        if(x==w)
            break;
    }
    for(;dis[x]>=dis[w];x=pr[x][0]){
        if(s[x]!=-1)
            h[s[x]+2*n].push_back(i);
        if(x==w)
            break;
    }
    x=v;
    y=par(v, sq);
    while(dis[y]>=dis[w]){
        h[i].push_back(x+n);
        x=y;
        y=par(x, sq);
        if(x==w)
            break;
    }
    for(;dis[x]>=dis[w];x=pr[x][0]){
        if(t[x]!=-1)
            h[i].push_back(t[x]+2*n);
        if(x==w)
            break;
    }
    x=pr[u][0];
    y=par(x, sq);
    while(dis[y]>=dis[w]){
        h[i].push_back(x+n);
        x=y;
        y=par(x, sq);
        if(x==w)
            break;
    }
    for(;dis[x]>dis[w];x=pr[x][0]){
        if(t[x]!=-1)
            h[i].push_back(t[x]+2*n);
    }
    x=u;
    y=par(x, sq);
    while(dis[y]>=dis[w]){
        h[x].push_back(i);
        x=y;
        y=par(x, sq);
        if(x==w)
        break;
    }
    for(;dis[x]>dis[w];x=pr[x][0]){
        if(s[x]!=-1)
            h[s[x]+2*n].push_back(i);
    }
}
     
void sfd(const int &v){
    mk[v]=1;
    for(int u: h[v]){
        if(!mk[u])
            sfd(u);
    }
    nd.push_back(v);
}
     
void sol(){
    cin>>n;
    sq=sqrt(n);
    for(int i=0;i<n;++i)
        g[i].clear();
    for(int i=1;i<n;++i){
        int u, v;
        cin>>u>>v;
        g[--v].push_back(--u);
        g[u].push_back(v);
    }
    cin>>m;
    memset(s, -1, 4*n);
    memset(t, -1, 4*n);
    for(int i=0;i<m;++i){
        int u, v;
        cin>>u>>v;
        s[--u]=i;
        t[--v]=i;
        st[i]={u, v};
    }
    dfs(0);
    pre();    
    for(int i=0;i<m;++i)
        opr(2*n+i, st[i].F, st[i].S);
    nd.clear();
    memset(mk, 0, 4*nm);
    for(int i=0;i<nm;++i){
        if(!mk[i])
            sfd(i);
    }
    memset(mk, 0, 4*nm);
    for(int i=0;i<nm;++i){
        mk[nd[i]]=1;
        for(int u: h[nd[i]]){
            if(!mk[u]){
                cout<<"No\n";
                return;
            }
        }
    }
    cout<<"Yes\n";
}
     
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T;
    cin>>T;
    while(T--)
        sol();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47316 KB Output is correct
2 Correct 22 ms 47260 KB Output is correct
3 Correct 21 ms 47316 KB Output is correct
4 Correct 33 ms 47316 KB Output is correct
5 Correct 46 ms 47368 KB Output is correct
6 Correct 24 ms 47324 KB Output is correct
7 Correct 24 ms 47316 KB Output is correct
8 Correct 25 ms 47444 KB Output is correct
9 Correct 110 ms 50124 KB Output is correct
10 Correct 234 ms 80716 KB Output is correct
11 Correct 28 ms 47440 KB Output is correct
12 Correct 69 ms 48120 KB Output is correct
13 Correct 801 ms 345160 KB Output is correct
14 Correct 694 ms 358696 KB Output is correct
15 Correct 4503 ms 449120 KB Output is correct
16 Execution timed out 5077 ms 736192 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47316 KB Output is correct
2 Correct 27 ms 47232 KB Output is correct
3 Correct 31 ms 47308 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 29 ms 47312 KB Output is correct
6 Correct 31 ms 47316 KB Output is correct
7 Correct 32 ms 47312 KB Output is correct
8 Correct 32 ms 47368 KB Output is correct
9 Correct 29 ms 47312 KB Output is correct
10 Correct 27 ms 47316 KB Output is correct
11 Correct 29 ms 47392 KB Output is correct
12 Correct 29 ms 47368 KB Output is correct
13 Correct 29 ms 47416 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47316 KB Output is correct
2 Correct 27 ms 47232 KB Output is correct
3 Correct 31 ms 47308 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 29 ms 47312 KB Output is correct
6 Correct 31 ms 47316 KB Output is correct
7 Correct 32 ms 47312 KB Output is correct
8 Correct 32 ms 47368 KB Output is correct
9 Correct 29 ms 47312 KB Output is correct
10 Correct 27 ms 47316 KB Output is correct
11 Correct 29 ms 47392 KB Output is correct
12 Correct 29 ms 47368 KB Output is correct
13 Correct 29 ms 47416 KB Output is correct
14 Correct 31 ms 47204 KB Output is correct
15 Correct 27 ms 47316 KB Output is correct
16 Correct 28 ms 47372 KB Output is correct
17 Correct 28 ms 47380 KB Output is correct
18 Correct 32 ms 47392 KB Output is correct
19 Correct 26 ms 47264 KB Output is correct
20 Correct 30 ms 47404 KB Output is correct
21 Correct 30 ms 47292 KB Output is correct
22 Correct 27 ms 47308 KB Output is correct
23 Correct 26 ms 47252 KB Output is correct
24 Correct 27 ms 47244 KB Output is correct
25 Correct 25 ms 47316 KB Output is correct
26 Correct 24 ms 47372 KB Output is correct
27 Correct 27 ms 47412 KB Output is correct
28 Correct 24 ms 47300 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47316 KB Output is correct
2 Correct 27 ms 47232 KB Output is correct
3 Correct 31 ms 47308 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 29 ms 47312 KB Output is correct
6 Correct 31 ms 47316 KB Output is correct
7 Correct 32 ms 47312 KB Output is correct
8 Correct 32 ms 47368 KB Output is correct
9 Correct 29 ms 47312 KB Output is correct
10 Correct 27 ms 47316 KB Output is correct
11 Correct 29 ms 47392 KB Output is correct
12 Correct 29 ms 47368 KB Output is correct
13 Correct 29 ms 47416 KB Output is correct
14 Correct 31 ms 47204 KB Output is correct
15 Correct 27 ms 47316 KB Output is correct
16 Correct 28 ms 47372 KB Output is correct
17 Correct 28 ms 47380 KB Output is correct
18 Correct 32 ms 47392 KB Output is correct
19 Correct 26 ms 47264 KB Output is correct
20 Correct 30 ms 47404 KB Output is correct
21 Correct 30 ms 47292 KB Output is correct
22 Correct 27 ms 47308 KB Output is correct
23 Correct 26 ms 47252 KB Output is correct
24 Correct 27 ms 47244 KB Output is correct
25 Correct 25 ms 47316 KB Output is correct
26 Correct 24 ms 47372 KB Output is correct
27 Correct 27 ms 47412 KB Output is correct
28 Correct 24 ms 47300 KB Output is correct
29 Correct 26 ms 47440 KB Output is correct
30 Correct 26 ms 47416 KB Output is correct
31 Correct 25 ms 47460 KB Output is correct
32 Correct 25 ms 47444 KB Output is correct
33 Correct 27 ms 47440 KB Output is correct
34 Correct 28 ms 47392 KB Output is correct
35 Correct 27 ms 47304 KB Output is correct
36 Correct 26 ms 47424 KB Output is correct
37 Correct 32 ms 47316 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47316 KB Output is correct
2 Correct 27 ms 47232 KB Output is correct
3 Correct 31 ms 47308 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 29 ms 47312 KB Output is correct
6 Correct 31 ms 47316 KB Output is correct
7 Correct 32 ms 47312 KB Output is correct
8 Correct 32 ms 47368 KB Output is correct
9 Correct 29 ms 47312 KB Output is correct
10 Correct 27 ms 47316 KB Output is correct
11 Correct 29 ms 47392 KB Output is correct
12 Correct 29 ms 47368 KB Output is correct
13 Correct 29 ms 47416 KB Output is correct
14 Correct 31 ms 47204 KB Output is correct
15 Correct 27 ms 47316 KB Output is correct
16 Correct 28 ms 47372 KB Output is correct
17 Correct 28 ms 47380 KB Output is correct
18 Correct 32 ms 47392 KB Output is correct
19 Correct 26 ms 47264 KB Output is correct
20 Correct 30 ms 47404 KB Output is correct
21 Correct 30 ms 47292 KB Output is correct
22 Correct 27 ms 47308 KB Output is correct
23 Correct 26 ms 47252 KB Output is correct
24 Correct 27 ms 47244 KB Output is correct
25 Correct 25 ms 47316 KB Output is correct
26 Correct 24 ms 47372 KB Output is correct
27 Correct 27 ms 47412 KB Output is correct
28 Correct 24 ms 47300 KB Output is correct
29 Correct 26 ms 47440 KB Output is correct
30 Correct 26 ms 47416 KB Output is correct
31 Correct 25 ms 47460 KB Output is correct
32 Correct 25 ms 47444 KB Output is correct
33 Correct 27 ms 47440 KB Output is correct
34 Correct 28 ms 47392 KB Output is correct
35 Correct 27 ms 47304 KB Output is correct
36 Correct 26 ms 47424 KB Output is correct
37 Correct 32 ms 47316 KB Output is correct
38 Correct 142 ms 50392 KB Output is correct
39 Correct 263 ms 80904 KB Output is correct
40 Correct 102 ms 49740 KB Output is correct
41 Correct 68 ms 48824 KB Output is correct
42 Correct 76 ms 49796 KB Output is correct
43 Correct 96 ms 48832 KB Output is correct
44 Correct 39 ms 47764 KB Output is correct
45 Correct 238 ms 64448 KB Output is correct
46 Correct 217 ms 64260 KB Output is correct
47 Correct 304 ms 69692 KB Output is correct
48 Correct 320 ms 69700 KB Output is correct
49 Correct 420 ms 64396 KB Output is correct
50 Correct 418 ms 63744 KB Output is correct
51 Correct 339 ms 67180 KB Output is correct
52 Correct 355 ms 67640 KB Output is correct
53 Correct 37 ms 48972 KB Output is correct
54 Correct 162 ms 63356 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47284 KB Output is correct
2 Correct 23 ms 47308 KB Output is correct
3 Correct 24 ms 47280 KB Output is correct
4 Correct 25 ms 47316 KB Output is correct
5 Correct 32 ms 47448 KB Output is correct
6 Correct 24 ms 47316 KB Output is correct
7 Correct 25 ms 47304 KB Output is correct
8 Correct 25 ms 47308 KB Output is correct
9 Correct 25 ms 47304 KB Output is correct
10 Correct 26 ms 47316 KB Output is correct
11 Correct 24 ms 47332 KB Output is correct
12 Correct 25 ms 47340 KB Output is correct
13 Correct 48 ms 47668 KB Output is correct
14 Correct 57 ms 47612 KB Output is correct
15 Correct 50 ms 47620 KB Output is correct
16 Correct 109 ms 66560 KB Output is correct
17 Correct 237 ms 77872 KB Output is correct
18 Correct 455 ms 96428 KB Output is correct
19 Correct 110 ms 65052 KB Output is correct
20 Correct 126 ms 66024 KB Output is correct
21 Correct 131 ms 65928 KB Output is correct
22 Correct 181 ms 76688 KB Output is correct
23 Correct 171 ms 76180 KB Output is correct
24 Correct 174 ms 76096 KB Output is correct
25 Correct 172 ms 76152 KB Output is correct
26 Correct 210 ms 76300 KB Output is correct
27 Correct 194 ms 74516 KB Output is correct
28 Correct 216 ms 77044 KB Output is correct
29 Correct 213 ms 75248 KB Output is correct
30 Correct 149 ms 71852 KB Output is correct
31 Correct 137 ms 72656 KB Output is correct
32 Correct 154 ms 69896 KB Output is correct
33 Correct 174 ms 70924 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47316 KB Output is correct
2 Correct 22 ms 47260 KB Output is correct
3 Correct 21 ms 47316 KB Output is correct
4 Correct 33 ms 47316 KB Output is correct
5 Correct 46 ms 47368 KB Output is correct
6 Correct 24 ms 47324 KB Output is correct
7 Correct 24 ms 47316 KB Output is correct
8 Correct 25 ms 47444 KB Output is correct
9 Correct 110 ms 50124 KB Output is correct
10 Correct 234 ms 80716 KB Output is correct
11 Correct 28 ms 47440 KB Output is correct
12 Correct 69 ms 48120 KB Output is correct
13 Correct 801 ms 345160 KB Output is correct
14 Correct 694 ms 358696 KB Output is correct
15 Correct 4503 ms 449120 KB Output is correct
16 Execution timed out 5077 ms 736192 KB Time limit exceeded
17 Halted 0 ms 0 KB -