oj.uz

Submission #632634

# Submission time Handle Problem Language Result Execution time Memory
632634 2022-08-20T13:35:53 Z Mahdi Jail (JOI22_jail) C++17
72 / 100
 5000 ms 688660 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=12e4+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, nm);
    for(int i=0;i<nm;++i){
        if(!mk[i])
            sfd(i);
    }
    memset(mk, 0, 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 6 ms 11648 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct
4 Correct 20 ms 11724 KB Output is correct
5 Correct 29 ms 11772 KB Output is correct
6 Correct 8 ms 11700 KB Output is correct
7 Correct 7 ms 11604 KB Output is correct
8 Correct 9 ms 11760 KB Output is correct
9 Correct 98 ms 14764 KB Output is correct
10 Correct 223 ms 44668 KB Output is correct
11 Correct 13 ms 11740 KB Output is correct
12 Correct 49 ms 11896 KB Output is correct
13 Correct 726 ms 308344 KB Output is correct
14 Correct 731 ms 322072 KB Output is correct
15 Correct 4503 ms 412316 KB Output is correct
16 Execution timed out 5123 ms 688660 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11544 KB Output is correct
2 Correct 6 ms 11612 KB Output is correct
3 Correct 7 ms 11620 KB Output is correct
4 Correct 8 ms 11628 KB Output is correct
5 Correct 8 ms 11604 KB Output is correct
6 Correct 9 ms 11628 KB Output is correct
7 Correct 8 ms 11704 KB Output is correct
8 Correct 7 ms 11604 KB Output is correct
9 Correct 8 ms 11604 KB Output is correct
10 Correct 8 ms 11604 KB Output is correct
11 Correct 10 ms 11584 KB Output is correct
12 Correct 7 ms 11604 KB Output is correct
13 Correct 8 ms 11860 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11544 KB Output is correct
2 Correct 6 ms 11612 KB Output is correct
3 Correct 7 ms 11620 KB Output is correct
4 Correct 8 ms 11628 KB Output is correct
5 Correct 8 ms 11604 KB Output is correct
6 Correct 9 ms 11628 KB Output is correct
7 Correct 8 ms 11704 KB Output is correct
8 Correct 7 ms 11604 KB Output is correct
9 Correct 8 ms 11604 KB Output is correct
10 Correct 8 ms 11604 KB Output is correct
11 Correct 10 ms 11584 KB Output is correct
12 Correct 7 ms 11604 KB Output is correct
13 Correct 8 ms 11860 KB Output is correct
14 Correct 6 ms 11612 KB Output is correct
15 Correct 7 ms 11612 KB Output is correct
16 Correct 8 ms 11720 KB Output is correct
17 Correct 7 ms 11604 KB Output is correct
18 Correct 8 ms 11604 KB Output is correct
19 Correct 7 ms 11544 KB Output is correct
20 Correct 8 ms 11604 KB Output is correct
21 Correct 8 ms 11604 KB Output is correct
22 Correct 9 ms 11628 KB Output is correct
23 Correct 7 ms 11608 KB Output is correct
24 Correct 7 ms 11632 KB Output is correct
25 Correct 8 ms 11604 KB Output is correct
26 Correct 9 ms 11604 KB Output is correct
27 Correct 8 ms 11604 KB Output is correct
28 Correct 7 ms 11604 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11544 KB Output is correct
2 Correct 6 ms 11612 KB Output is correct
3 Correct 7 ms 11620 KB Output is correct
4 Correct 8 ms 11628 KB Output is correct
5 Correct 8 ms 11604 KB Output is correct
6 Correct 9 ms 11628 KB Output is correct
7 Correct 8 ms 11704 KB Output is correct
8 Correct 7 ms 11604 KB Output is correct
9 Correct 8 ms 11604 KB Output is correct
10 Correct 8 ms 11604 KB Output is correct
11 Correct 10 ms 11584 KB Output is correct
12 Correct 7 ms 11604 KB Output is correct
13 Correct 8 ms 11860 KB Output is correct
14 Correct 6 ms 11612 KB Output is correct
15 Correct 7 ms 11612 KB Output is correct
16 Correct 8 ms 11720 KB Output is correct
17 Correct 7 ms 11604 KB Output is correct
18 Correct 8 ms 11604 KB Output is correct
19 Correct 7 ms 11544 KB Output is correct
20 Correct 8 ms 11604 KB Output is correct
21 Correct 8 ms 11604 KB Output is correct
22 Correct 9 ms 11628 KB Output is correct
23 Correct 7 ms 11608 KB Output is correct
24 Correct 7 ms 11632 KB Output is correct
25 Correct 8 ms 11604 KB Output is correct
26 Correct 9 ms 11604 KB Output is correct
27 Correct 8 ms 11604 KB Output is correct
28 Correct 7 ms 11604 KB Output is correct
29 Correct 12 ms 11748 KB Output is correct
30 Correct 8 ms 11728 KB Output is correct
31 Correct 8 ms 11752 KB Output is correct
32 Correct 8 ms 11720 KB Output is correct
33 Correct 8 ms 11640 KB Output is correct
34 Correct 11 ms 11712 KB Output is correct
35 Correct 10 ms 11724 KB Output is correct
36 Correct 8 ms 11736 KB Output is correct
37 Correct 9 ms 11620 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11544 KB Output is correct
2 Correct 6 ms 11612 KB Output is correct
3 Correct 7 ms 11620 KB Output is correct
4 Correct 8 ms 11628 KB Output is correct
5 Correct 8 ms 11604 KB Output is correct
6 Correct 9 ms 11628 KB Output is correct
7 Correct 8 ms 11704 KB Output is correct
8 Correct 7 ms 11604 KB Output is correct
9 Correct 8 ms 11604 KB Output is correct
10 Correct 8 ms 11604 KB Output is correct
11 Correct 10 ms 11584 KB Output is correct
12 Correct 7 ms 11604 KB Output is correct
13 Correct 8 ms 11860 KB Output is correct
14 Correct 6 ms 11612 KB Output is correct
15 Correct 7 ms 11612 KB Output is correct
16 Correct 8 ms 11720 KB Output is correct
17 Correct 7 ms 11604 KB Output is correct
18 Correct 8 ms 11604 KB Output is correct
19 Correct 7 ms 11544 KB Output is correct
20 Correct 8 ms 11604 KB Output is correct
21 Correct 8 ms 11604 KB Output is correct
22 Correct 9 ms 11628 KB Output is correct
23 Correct 7 ms 11608 KB Output is correct
24 Correct 7 ms 11632 KB Output is correct
25 Correct 8 ms 11604 KB Output is correct
26 Correct 9 ms 11604 KB Output is correct
27 Correct 8 ms 11604 KB Output is correct
28 Correct 7 ms 11604 KB Output is correct
29 Correct 12 ms 11748 KB Output is correct
30 Correct 8 ms 11728 KB Output is correct
31 Correct 8 ms 11752 KB Output is correct
32 Correct 8 ms 11720 KB Output is correct
33 Correct 8 ms 11640 KB Output is correct
34 Correct 11 ms 11712 KB Output is correct
35 Correct 10 ms 11724 KB Output is correct
36 Correct 8 ms 11736 KB Output is correct
37 Correct 9 ms 11620 KB Output is correct
38 Correct 93 ms 14884 KB Output is correct
39 Correct 233 ms 44660 KB Output is correct
40 Correct 73 ms 14112 KB Output is correct
41 Correct 45 ms 13220 KB Output is correct
42 Correct 48 ms 14060 KB Output is correct
43 Correct 65 ms 13136 KB Output is correct
44 Correct 15 ms 12132 KB Output is correct
45 Correct 211 ms 28120 KB Output is correct
46 Correct 234 ms 27904 KB Output is correct
47 Correct 274 ms 33468 KB Output is correct
48 Correct 275 ms 33436 KB Output is correct
49 Correct 392 ms 28104 KB Output is correct
50 Correct 391 ms 27588 KB Output is correct
51 Correct 316 ms 30948 KB Output is correct
52 Correct 328 ms 31304 KB Output is correct
53 Correct 19 ms 13408 KB Output is correct
54 Correct 120 ms 27040 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11600 KB Output is correct
2 Correct 6 ms 11556 KB Output is correct
3 Correct 8 ms 11608 KB Output is correct
4 Correct 7 ms 11616 KB Output is correct
5 Correct 14 ms 11752 KB Output is correct
6 Correct 9 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Correct 6 ms 11612 KB Output is correct
9 Correct 8 ms 11604 KB Output is correct
10 Correct 6 ms 11604 KB Output is correct
11 Correct 7 ms 11604 KB Output is correct
12 Correct 8 ms 11732 KB Output is correct
13 Correct 29 ms 11896 KB Output is correct
14 Correct 40 ms 11968 KB Output is correct
15 Correct 36 ms 11988 KB Output is correct
16 Correct 124 ms 30212 KB Output is correct
17 Correct 224 ms 41320 KB Output is correct
18 Correct 438 ms 59664 KB Output is correct
19 Correct 94 ms 28916 KB Output is correct
20 Correct 103 ms 29704 KB Output is correct
21 Correct 104 ms 29640 KB Output is correct
22 Correct 182 ms 39940 KB Output is correct
23 Correct 189 ms 39608 KB Output is correct
24 Correct 190 ms 39588 KB Output is correct
25 Correct 162 ms 39772 KB Output is correct
26 Correct 169 ms 39880 KB Output is correct
27 Correct 186 ms 37724 KB Output is correct
28 Correct 208 ms 40356 KB Output is correct
29 Correct 190 ms 38720 KB Output is correct
30 Correct 131 ms 35340 KB Output is correct
31 Correct 137 ms 36152 KB Output is correct
32 Correct 191 ms 33512 KB Output is correct
33 Correct 139 ms 34280 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11648 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct
4 Correct 20 ms 11724 KB Output is correct
5 Correct 29 ms 11772 KB Output is correct
6 Correct 8 ms 11700 KB Output is correct
7 Correct 7 ms 11604 KB Output is correct
8 Correct 9 ms 11760 KB Output is correct
9 Correct 98 ms 14764 KB Output is correct
10 Correct 223 ms 44668 KB Output is correct
11 Correct 13 ms 11740 KB Output is correct
12 Correct 49 ms 11896 KB Output is correct
13 Correct 726 ms 308344 KB Output is correct
14 Correct 731 ms 322072 KB Output is correct
15 Correct 4503 ms 412316 KB Output is correct
16 Execution timed out 5123 ms 688660 KB Time limit exceeded
17 Halted 0 ms 0 KB -