oj.uz

Submission #545011

# Submission time Handle Problem Language Result Execution time Memory
545011 2022-04-03T10:12:29 Z leaked Jail (JOI22_jail) C++14
49 / 100
 797 ms 811536 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int M=1e9+7;
const int N=120'000+1;
const int lg=19;
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
vec<int> gr[4*N*lg],g[N];
int used[N],ok;
int up[N][lg];

int fin[N][lg],sta[N][lg];
void dfs(int v){
    used[v]=1;
    for(auto &z : gr[v]){
        if(used[z]){
            ok&=(used[z]==2);
            continue;
        }
        dfs(z);
    }
    used[v]=2;
}
int par[N],in[N],out[N],tt,ut[N],dt[N];
int id=0;
void dfs1(int v,int p){
    par[v]=p;
    in[v]=tt++;
    ut[v]=(ut[v]==-1?id++:ut[v]);
    dt[v]=(dt[v]==-1?id++:dt[v]);

    up[v][0]=p;

    sta[v][0]=id++;fin[v][0]=id++;

//    cout<<"ADD "<<fin[v][0]<<' '<<dt[p]<<endl;
    gr[fin[v][0]].pb(dt[p]);

    gr[ut[p]].pb(sta[v][0]);
//    cout<<"ADD "<<ut[p]<<' ' <<sta[v][0]<<endl;
//    cout<<"DFS "<<v<<endl;
    for(int j=1;j<lg;j++){
        up[v][j]=up[up[v][j-1]][j-1];
        sta[v][j]=id++;fin[v][j]=id++;
        assert(id<4*N*lg);

//        cout<<"ADDT1 "<<fin[v][j]<<' '<<fin[v][j-1]<<' '<<fin[up[v][j-1]][j-1]<<endl;
        gr[fin[v][j]].pb(fin[v][j-1]);gr[fin[v][j]].pb(fin[up[v][j-1]][j-1]);
//        cout<<"ADDT2 "<<sta[v][j-1]<<' '<<sta[up[v][j-1]][j-1]<<' '<<sta[v][j]<<endl;
        gr[sta[v][j-1]].pb(sta[v][j]);gr[sta[up[v][j-1]][j-1]].pb(sta[v][j]);
    }
//    assert(id<4*N*lg);
    for(auto &z : g[v]){
        if(z==p) continue;
        dfs1(z,v);
    }
    out[v]=tt-1;
}
bool is(int a,int b){
    return in[a]<=in[b]&&out[a]>=out[b];
}
int lca(int a,int b){
    if(is(a,b)) return a;
    for(int i=lg-1;i>=0;i--){
        if(!is(up[a][i],b))
            a=up[a][i];
    }
    return up[a][0];
}
void addway(int a,int b,int j){
    if(is(a,b)) return;
    for(int i=lg-1;i>=0;i--){
        if(!is(up[a][i],b)){
//            cout<<"ADD "<<sta[a][i]<<' '<<j<<endl;
//            cout<<"ADD "<<j<<' '<<fin[a][i]<<endl;
            gr[sta[a][i]].pb(j);
            gr[j].pb(fin[a][i]);
            a=up[a][i];
        }
    }
//    int i=0;
//    gr[j].pb(gu[a][i]);
//    gr[gd[a][i]].pb(j);
}
void solve(){
    int n,m;
    cin>>n;
    for(int i=0;i<n;i++) ut[i]=dt[i]=-1,g[i].clear();
    ok=1;
    for(int i=1;i<n;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb(u);g[u].pb(v);
    }
    cin>>m;
    vec<int> st(m),f(m);
    for(int i=0;i<m;i++) used[i]=0,gr[i].clear();
//    vec<int>ids(m);
    id=m;
    for(int i=0;i<m;i++){
        cin>>st[i]>>f[i];--st[i];--f[i];
        ut[st[i]]=i;dt[f[i]]=i;
    }
    dfs1(0,0);
    ///ut - start , dt - finish
    for(int i=0;i<m;i++){
//        gr[ut[f[i]]].pb(ids[i]);
//        gr[ids[i]].pb(dt[st[i]]);

        int v=st[i],u=f[i];
        int lc=lca(v,u);
        addway(v,lc,i);addway(u,lc,i);

        gr[i].pb(dt[st[i]]);
        gr[ut[f[i]]].pb(i);
//
        if(lc!=v && lc!=u){
            gr[i].pb(dt[lc]);
            gr[ut[lc]].pb(i);
        }
    }
    for(int i=0;i<id;i++){
        if(!used[i])
            dfs(i);
    }
    for(int i=0;i<id;i++) gr[i].clear(),used[i]=0;
    id=0;
    cout<<(ok?"Yes":"No")<<'\n';
}
signed main(){
    fast_resp;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
/*
1
4
1 2
2 3
3 4
4 5
3 6
6 7
1
4 1
5 7
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 217264 KB Output is correct
2 Correct 114 ms 217304 KB Output is correct
3 Correct 114 ms 217340 KB Output is correct
4 Correct 187 ms 217528 KB Output is correct
5 Correct 251 ms 217576 KB Output is correct
6 Correct 126 ms 217712 KB Output is correct
7 Correct 153 ms 217736 KB Output is correct
8 Correct 110 ms 217744 KB Output is correct
9 Incorrect 681 ms 231472 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 217356 KB Output is correct
2 Correct 106 ms 217344 KB Output is correct
3 Correct 129 ms 217820 KB Output is correct
4 Correct 110 ms 217804 KB Output is correct
5 Correct 110 ms 217756 KB Output is correct
6 Correct 111 ms 217824 KB Output is correct
7 Correct 124 ms 217828 KB Output is correct
8 Correct 109 ms 217756 KB Output is correct
9 Correct 108 ms 217752 KB Output is correct
10 Correct 110 ms 217800 KB Output is correct
11 Correct 113 ms 217744 KB Output is correct
12 Correct 118 ms 217736 KB Output is correct
13 Correct 108 ms 217748 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 217356 KB Output is correct
2 Correct 106 ms 217344 KB Output is correct
3 Correct 129 ms 217820 KB Output is correct
4 Correct 110 ms 217804 KB Output is correct
5 Correct 110 ms 217756 KB Output is correct
6 Correct 111 ms 217824 KB Output is correct
7 Correct 124 ms 217828 KB Output is correct
8 Correct 109 ms 217756 KB Output is correct
9 Correct 108 ms 217752 KB Output is correct
10 Correct 110 ms 217800 KB Output is correct
11 Correct 113 ms 217744 KB Output is correct
12 Correct 118 ms 217736 KB Output is correct
13 Correct 108 ms 217748 KB Output is correct
14 Correct 104 ms 217452 KB Output is correct
15 Correct 102 ms 217344 KB Output is correct
16 Correct 120 ms 217768 KB Output is correct
17 Correct 107 ms 217844 KB Output is correct
18 Correct 111 ms 217804 KB Output is correct
19 Correct 118 ms 217292 KB Output is correct
20 Correct 108 ms 217816 KB Output is correct
21 Correct 109 ms 217688 KB Output is correct
22 Correct 115 ms 217816 KB Output is correct
23 Correct 108 ms 217268 KB Output is correct
24 Correct 102 ms 217504 KB Output is correct
25 Correct 113 ms 217764 KB Output is correct
26 Correct 101 ms 217780 KB Output is correct
27 Correct 110 ms 217744 KB Output is correct
28 Correct 102 ms 217376 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 217356 KB Output is correct
2 Correct 106 ms 217344 KB Output is correct
3 Correct 129 ms 217820 KB Output is correct
4 Correct 110 ms 217804 KB Output is correct
5 Correct 110 ms 217756 KB Output is correct
6 Correct 111 ms 217824 KB Output is correct
7 Correct 124 ms 217828 KB Output is correct
8 Correct 109 ms 217756 KB Output is correct
9 Correct 108 ms 217752 KB Output is correct
10 Correct 110 ms 217800 KB Output is correct
11 Correct 113 ms 217744 KB Output is correct
12 Correct 118 ms 217736 KB Output is correct
13 Correct 108 ms 217748 KB Output is correct
14 Correct 104 ms 217452 KB Output is correct
15 Correct 102 ms 217344 KB Output is correct
16 Correct 120 ms 217768 KB Output is correct
17 Correct 107 ms 217844 KB Output is correct
18 Correct 111 ms 217804 KB Output is correct
19 Correct 118 ms 217292 KB Output is correct
20 Correct 108 ms 217816 KB Output is correct
21 Correct 109 ms 217688 KB Output is correct
22 Correct 115 ms 217816 KB Output is correct
23 Correct 108 ms 217268 KB Output is correct
24 Correct 102 ms 217504 KB Output is correct
25 Correct 113 ms 217764 KB Output is correct
26 Correct 101 ms 217780 KB Output is correct
27 Correct 110 ms 217744 KB Output is correct
28 Correct 102 ms 217376 KB Output is correct
29 Correct 114 ms 217764 KB Output is correct
30 Correct 110 ms 217888 KB Output is correct
31 Correct 114 ms 218036 KB Output is correct
32 Correct 109 ms 217852 KB Output is correct
33 Correct 111 ms 217752 KB Output is correct
34 Correct 111 ms 217640 KB Output is correct
35 Correct 108 ms 217744 KB Output is correct
36 Correct 108 ms 217772 KB Output is correct
37 Correct 108 ms 217844 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 217356 KB Output is correct
2 Correct 106 ms 217344 KB Output is correct
3 Correct 129 ms 217820 KB Output is correct
4 Correct 110 ms 217804 KB Output is correct
5 Correct 110 ms 217756 KB Output is correct
6 Correct 111 ms 217824 KB Output is correct
7 Correct 124 ms 217828 KB Output is correct
8 Correct 109 ms 217756 KB Output is correct
9 Correct 108 ms 217752 KB Output is correct
10 Correct 110 ms 217800 KB Output is correct
11 Correct 113 ms 217744 KB Output is correct
12 Correct 118 ms 217736 KB Output is correct
13 Correct 108 ms 217748 KB Output is correct
14 Correct 104 ms 217452 KB Output is correct
15 Correct 102 ms 217344 KB Output is correct
16 Correct 120 ms 217768 KB Output is correct
17 Correct 107 ms 217844 KB Output is correct
18 Correct 111 ms 217804 KB Output is correct
19 Correct 118 ms 217292 KB Output is correct
20 Correct 108 ms 217816 KB Output is correct
21 Correct 109 ms 217688 KB Output is correct
22 Correct 115 ms 217816 KB Output is correct
23 Correct 108 ms 217268 KB Output is correct
24 Correct 102 ms 217504 KB Output is correct
25 Correct 113 ms 217764 KB Output is correct
26 Correct 101 ms 217780 KB Output is correct
27 Correct 110 ms 217744 KB Output is correct
28 Correct 102 ms 217376 KB Output is correct
29 Correct 114 ms 217764 KB Output is correct
30 Correct 110 ms 217888 KB Output is correct
31 Correct 114 ms 218036 KB Output is correct
32 Correct 109 ms 217852 KB Output is correct
33 Correct 111 ms 217752 KB Output is correct
34 Correct 111 ms 217640 KB Output is correct
35 Correct 108 ms 217744 KB Output is correct
36 Correct 108 ms 217772 KB Output is correct
37 Correct 108 ms 217844 KB Output is correct
38 Incorrect 591 ms 231484 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 217292 KB Output is correct
2 Correct 101 ms 217232 KB Output is correct
3 Correct 103 ms 217324 KB Output is correct
4 Correct 107 ms 217340 KB Output is correct
5 Correct 128 ms 217384 KB Output is correct
6 Correct 101 ms 217772 KB Output is correct
7 Correct 107 ms 217804 KB Output is correct
8 Correct 113 ms 217428 KB Output is correct
9 Correct 102 ms 217276 KB Output is correct
10 Correct 109 ms 217456 KB Output is correct
11 Correct 103 ms 217296 KB Output is correct
12 Correct 106 ms 217796 KB Output is correct
13 Correct 192 ms 217692 KB Output is correct
14 Correct 239 ms 217756 KB Output is correct
15 Correct 211 ms 217688 KB Output is correct
16 Runtime error 797 ms 811536 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 217264 KB Output is correct
2 Correct 114 ms 217304 KB Output is correct
3 Correct 114 ms 217340 KB Output is correct
4 Correct 187 ms 217528 KB Output is correct
5 Correct 251 ms 217576 KB Output is correct
6 Correct 126 ms 217712 KB Output is correct
7 Correct 153 ms 217736 KB Output is correct
8 Correct 110 ms 217744 KB Output is correct
9 Incorrect 681 ms 231472 KB Output isn't correct
10 Halted 0 ms 0 KB -