oj.uz

Submission #632664

# Submission time Handle Problem Language Result Execution time Memory
632664 2022-08-20T14:20:18 Z Mahdi Jail (JOI22_jail) C++17
72 / 100
 4175 ms 1048576 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=4*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 8 ms 11604 KB Output is correct
2 Correct 6 ms 11616 KB Output is correct
3 Correct 9 ms 11608 KB Output is correct
4 Correct 24 ms 11988 KB Output is correct
5 Correct 46 ms 12284 KB Output is correct
6 Correct 10 ms 11620 KB Output is correct
7 Correct 10 ms 11624 KB Output is correct
8 Correct 11 ms 11736 KB Output is correct
9 Correct 237 ms 18376 KB Output is correct
10 Correct 608 ms 45116 KB Output is correct
11 Correct 15 ms 11732 KB Output is correct
12 Correct 79 ms 12672 KB Output is correct
13 Correct 2440 ms 919808 KB Output is correct
14 Correct 2222 ms 919892 KB Output is correct
15 Runtime error 4175 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 7 ms 11616 KB Output is correct
3 Correct 9 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 7 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Correct 8 ms 11620 KB Output is correct
9 Correct 9 ms 11708 KB Output is correct
10 Correct 8 ms 11604 KB Output is correct
11 Correct 8 ms 11608 KB Output is correct
12 Correct 7 ms 11604 KB Output is correct
13 Correct 7 ms 11604 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 7 ms 11616 KB Output is correct
3 Correct 9 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 7 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Correct 8 ms 11620 KB Output is correct
9 Correct 9 ms 11708 KB Output is correct
10 Correct 8 ms 11604 KB Output is correct
11 Correct 8 ms 11608 KB Output is correct
12 Correct 7 ms 11604 KB Output is correct
13 Correct 7 ms 11604 KB Output is correct
14 Correct 7 ms 11604 KB Output is correct
15 Correct 7 ms 11604 KB Output is correct
16 Correct 8 ms 11604 KB Output is correct
17 Correct 9 ms 11604 KB Output is correct
18 Correct 10 ms 11624 KB Output is correct
19 Correct 6 ms 11604 KB Output is correct
20 Correct 8 ms 11704 KB Output is correct
21 Correct 8 ms 11724 KB Output is correct
22 Correct 7 ms 11604 KB Output is correct
23 Correct 6 ms 11604 KB Output is correct
24 Correct 6 ms 11608 KB Output is correct
25 Correct 9 ms 11716 KB Output is correct
26 Correct 7 ms 11608 KB Output is correct
27 Correct 8 ms 11604 KB Output is correct
28 Correct 8 ms 11608 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 7 ms 11616 KB Output is correct
3 Correct 9 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 7 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Correct 8 ms 11620 KB Output is correct
9 Correct 9 ms 11708 KB Output is correct
10 Correct 8 ms 11604 KB Output is correct
11 Correct 8 ms 11608 KB Output is correct
12 Correct 7 ms 11604 KB Output is correct
13 Correct 7 ms 11604 KB Output is correct
14 Correct 7 ms 11604 KB Output is correct
15 Correct 7 ms 11604 KB Output is correct
16 Correct 8 ms 11604 KB Output is correct
17 Correct 9 ms 11604 KB Output is correct
18 Correct 10 ms 11624 KB Output is correct
19 Correct 6 ms 11604 KB Output is correct
20 Correct 8 ms 11704 KB Output is correct
21 Correct 8 ms 11724 KB Output is correct
22 Correct 7 ms 11604 KB Output is correct
23 Correct 6 ms 11604 KB Output is correct
24 Correct 6 ms 11608 KB Output is correct
25 Correct 9 ms 11716 KB Output is correct
26 Correct 7 ms 11608 KB Output is correct
27 Correct 8 ms 11604 KB Output is correct
28 Correct 8 ms 11608 KB Output is correct
29 Correct 12 ms 11828 KB Output is correct
30 Correct 8 ms 11752 KB Output is correct
31 Correct 10 ms 11812 KB Output is correct
32 Correct 9 ms 11608 KB Output is correct
33 Correct 9 ms 11736 KB Output is correct
34 Correct 8 ms 11716 KB Output is correct
35 Correct 9 ms 11756 KB Output is correct
36 Correct 9 ms 11732 KB Output is correct
37 Correct 8 ms 11736 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 7 ms 11616 KB Output is correct
3 Correct 9 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 7 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Correct 8 ms 11620 KB Output is correct
9 Correct 9 ms 11708 KB Output is correct
10 Correct 8 ms 11604 KB Output is correct
11 Correct 8 ms 11608 KB Output is correct
12 Correct 7 ms 11604 KB Output is correct
13 Correct 7 ms 11604 KB Output is correct
14 Correct 7 ms 11604 KB Output is correct
15 Correct 7 ms 11604 KB Output is correct
16 Correct 8 ms 11604 KB Output is correct
17 Correct 9 ms 11604 KB Output is correct
18 Correct 10 ms 11624 KB Output is correct
19 Correct 6 ms 11604 KB Output is correct
20 Correct 8 ms 11704 KB Output is correct
21 Correct 8 ms 11724 KB Output is correct
22 Correct 7 ms 11604 KB Output is correct
23 Correct 6 ms 11604 KB Output is correct
24 Correct 6 ms 11608 KB Output is correct
25 Correct 9 ms 11716 KB Output is correct
26 Correct 7 ms 11608 KB Output is correct
27 Correct 8 ms 11604 KB Output is correct
28 Correct 8 ms 11608 KB Output is correct
29 Correct 12 ms 11828 KB Output is correct
30 Correct 8 ms 11752 KB Output is correct
31 Correct 10 ms 11812 KB Output is correct
32 Correct 9 ms 11608 KB Output is correct
33 Correct 9 ms 11736 KB Output is correct
34 Correct 8 ms 11716 KB Output is correct
35 Correct 9 ms 11756 KB Output is correct
36 Correct 9 ms 11732 KB Output is correct
37 Correct 8 ms 11736 KB Output is correct
38 Correct 239 ms 18176 KB Output is correct
39 Correct 597 ms 44756 KB Output is correct
40 Correct 174 ms 16988 KB Output is correct
41 Correct 47 ms 13712 KB Output is correct
42 Correct 73 ms 15728 KB Output is correct
43 Correct 226 ms 13872 KB Output is correct
44 Correct 16 ms 12116 KB Output is correct
45 Correct 220 ms 28576 KB Output is correct
46 Correct 233 ms 28416 KB Output is correct
47 Correct 822 ms 33492 KB Output is correct
48 Correct 833 ms 33536 KB Output is correct
49 Correct 1575 ms 28996 KB Output is correct
50 Correct 1543 ms 28420 KB Output is correct
51 Correct 1200 ms 34040 KB Output is correct
52 Correct 1178 ms 34772 KB Output is correct
53 Correct 19 ms 13516 KB Output is correct
54 Correct 126 ms 27648 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11608 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 6 ms 11612 KB Output is correct
4 Correct 6 ms 11592 KB Output is correct
5 Correct 16 ms 11712 KB Output is correct
6 Correct 10 ms 11604 KB Output is correct
7 Correct 7 ms 11608 KB Output is correct
8 Correct 6 ms 11608 KB Output is correct
9 Correct 6 ms 11508 KB Output is correct
10 Correct 8 ms 11612 KB Output is correct
11 Correct 7 ms 11608 KB Output is correct
12 Correct 8 ms 11732 KB Output is correct
13 Correct 29 ms 12236 KB Output is correct
14 Correct 49 ms 12516 KB Output is correct
15 Correct 40 ms 12372 KB Output is correct
16 Correct 96 ms 30712 KB Output is correct
17 Correct 232 ms 41760 KB Output is correct
18 Correct 456 ms 60064 KB Output is correct
19 Correct 118 ms 29272 KB Output is correct
20 Correct 102 ms 30188 KB Output is correct
21 Correct 101 ms 30108 KB Output is correct
22 Correct 177 ms 40444 KB Output is correct
23 Correct 196 ms 40136 KB Output is correct
24 Correct 165 ms 40128 KB Output is correct
25 Correct 156 ms 40368 KB Output is correct
26 Correct 167 ms 40308 KB Output is correct
27 Correct 233 ms 38264 KB Output is correct
28 Correct 180 ms 40800 KB Output is correct
29 Correct 179 ms 39132 KB Output is correct
30 Correct 151 ms 35920 KB Output is correct
31 Correct 162 ms 36664 KB Output is correct
32 Correct 151 ms 33984 KB Output is correct
33 Correct 135 ms 34812 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11604 KB Output is correct
2 Correct 6 ms 11616 KB Output is correct
3 Correct 9 ms 11608 KB Output is correct
4 Correct 24 ms 11988 KB Output is correct
5 Correct 46 ms 12284 KB Output is correct
6 Correct 10 ms 11620 KB Output is correct
7 Correct 10 ms 11624 KB Output is correct
8 Correct 11 ms 11736 KB Output is correct
9 Correct 237 ms 18376 KB Output is correct
10 Correct 608 ms 45116 KB Output is correct
11 Correct 15 ms 11732 KB Output is correct
12 Correct 79 ms 12672 KB Output is correct
13 Correct 2440 ms 919808 KB Output is correct
14 Correct 2222 ms 919892 KB Output is correct
15 Runtime error 4175 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -