oj.uz

Submission #545007

# Submission time Handle Problem Language Result Execution time Memory
545007 2022-04-03T10:10:58 Z leaked Jail (JOI22_jail) C++14
49 / 100
 766 ms 807536 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++;

//        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]);
    }
    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 100 ms 217296 KB Output is correct
2 Correct 105 ms 217268 KB Output is correct
3 Correct 107 ms 217300 KB Output is correct
4 Correct 175 ms 217472 KB Output is correct
5 Correct 238 ms 217544 KB Output is correct
6 Correct 123 ms 217816 KB Output is correct
7 Correct 112 ms 217808 KB Output is correct
8 Correct 111 ms 217736 KB Output is correct
9 Incorrect 597 ms 231504 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 116 ms 217272 KB Output is correct
2 Correct 106 ms 217252 KB Output is correct
3 Correct 120 ms 217724 KB Output is correct
4 Correct 115 ms 217748 KB Output is correct
5 Correct 113 ms 217824 KB Output is correct
6 Correct 119 ms 217856 KB Output is correct
7 Correct 121 ms 217804 KB Output is correct
8 Correct 113 ms 217776 KB Output is correct
9 Correct 120 ms 217808 KB Output is correct
10 Correct 131 ms 217824 KB Output is correct
11 Correct 110 ms 217804 KB Output is correct
12 Correct 126 ms 217864 KB Output is correct
13 Correct 128 ms 217776 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 217272 KB Output is correct
2 Correct 106 ms 217252 KB Output is correct
3 Correct 120 ms 217724 KB Output is correct
4 Correct 115 ms 217748 KB Output is correct
5 Correct 113 ms 217824 KB Output is correct
6 Correct 119 ms 217856 KB Output is correct
7 Correct 121 ms 217804 KB Output is correct
8 Correct 113 ms 217776 KB Output is correct
9 Correct 120 ms 217808 KB Output is correct
10 Correct 131 ms 217824 KB Output is correct
11 Correct 110 ms 217804 KB Output is correct
12 Correct 126 ms 217864 KB Output is correct
13 Correct 128 ms 217776 KB Output is correct
14 Correct 103 ms 217228 KB Output is correct
15 Correct 117 ms 217308 KB Output is correct
16 Correct 129 ms 217792 KB Output is correct
17 Correct 127 ms 217860 KB Output is correct
18 Correct 119 ms 217836 KB Output is correct
19 Correct 111 ms 217348 KB Output is correct
20 Correct 107 ms 217764 KB Output is correct
21 Correct 105 ms 217676 KB Output is correct
22 Correct 116 ms 217804 KB Output is correct
23 Correct 104 ms 217268 KB Output is correct
24 Correct 113 ms 217520 KB Output is correct
25 Correct 119 ms 217728 KB Output is correct
26 Correct 116 ms 217780 KB Output is correct
27 Correct 111 ms 217848 KB Output is correct
28 Correct 113 ms 217380 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 217272 KB Output is correct
2 Correct 106 ms 217252 KB Output is correct
3 Correct 120 ms 217724 KB Output is correct
4 Correct 115 ms 217748 KB Output is correct
5 Correct 113 ms 217824 KB Output is correct
6 Correct 119 ms 217856 KB Output is correct
7 Correct 121 ms 217804 KB Output is correct
8 Correct 113 ms 217776 KB Output is correct
9 Correct 120 ms 217808 KB Output is correct
10 Correct 131 ms 217824 KB Output is correct
11 Correct 110 ms 217804 KB Output is correct
12 Correct 126 ms 217864 KB Output is correct
13 Correct 128 ms 217776 KB Output is correct
14 Correct 103 ms 217228 KB Output is correct
15 Correct 117 ms 217308 KB Output is correct
16 Correct 129 ms 217792 KB Output is correct
17 Correct 127 ms 217860 KB Output is correct
18 Correct 119 ms 217836 KB Output is correct
19 Correct 111 ms 217348 KB Output is correct
20 Correct 107 ms 217764 KB Output is correct
21 Correct 105 ms 217676 KB Output is correct
22 Correct 116 ms 217804 KB Output is correct
23 Correct 104 ms 217268 KB Output is correct
24 Correct 113 ms 217520 KB Output is correct
25 Correct 119 ms 217728 KB Output is correct
26 Correct 116 ms 217780 KB Output is correct
27 Correct 111 ms 217848 KB Output is correct
28 Correct 113 ms 217380 KB Output is correct
29 Correct 118 ms 217796 KB Output is correct
30 Correct 112 ms 217932 KB Output is correct
31 Correct 113 ms 217920 KB Output is correct
32 Correct 112 ms 217804 KB Output is correct
33 Correct 111 ms 217832 KB Output is correct
34 Correct 111 ms 217676 KB Output is correct
35 Correct 118 ms 217640 KB Output is correct
36 Correct 122 ms 217792 KB Output is correct
37 Correct 113 ms 217736 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 217272 KB Output is correct
2 Correct 106 ms 217252 KB Output is correct
3 Correct 120 ms 217724 KB Output is correct
4 Correct 115 ms 217748 KB Output is correct
5 Correct 113 ms 217824 KB Output is correct
6 Correct 119 ms 217856 KB Output is correct
7 Correct 121 ms 217804 KB Output is correct
8 Correct 113 ms 217776 KB Output is correct
9 Correct 120 ms 217808 KB Output is correct
10 Correct 131 ms 217824 KB Output is correct
11 Correct 110 ms 217804 KB Output is correct
12 Correct 126 ms 217864 KB Output is correct
13 Correct 128 ms 217776 KB Output is correct
14 Correct 103 ms 217228 KB Output is correct
15 Correct 117 ms 217308 KB Output is correct
16 Correct 129 ms 217792 KB Output is correct
17 Correct 127 ms 217860 KB Output is correct
18 Correct 119 ms 217836 KB Output is correct
19 Correct 111 ms 217348 KB Output is correct
20 Correct 107 ms 217764 KB Output is correct
21 Correct 105 ms 217676 KB Output is correct
22 Correct 116 ms 217804 KB Output is correct
23 Correct 104 ms 217268 KB Output is correct
24 Correct 113 ms 217520 KB Output is correct
25 Correct 119 ms 217728 KB Output is correct
26 Correct 116 ms 217780 KB Output is correct
27 Correct 111 ms 217848 KB Output is correct
28 Correct 113 ms 217380 KB Output is correct
29 Correct 118 ms 217796 KB Output is correct
30 Correct 112 ms 217932 KB Output is correct
31 Correct 113 ms 217920 KB Output is correct
32 Correct 112 ms 217804 KB Output is correct
33 Correct 111 ms 217832 KB Output is correct
34 Correct 111 ms 217676 KB Output is correct
35 Correct 118 ms 217640 KB Output is correct
36 Correct 122 ms 217792 KB Output is correct
37 Correct 113 ms 217736 KB Output is correct
38 Incorrect 614 ms 231520 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 217412 KB Output is correct
2 Correct 113 ms 217360 KB Output is correct
3 Correct 124 ms 217328 KB Output is correct
4 Correct 102 ms 217292 KB Output is correct
5 Correct 136 ms 217384 KB Output is correct
6 Correct 108 ms 217816 KB Output is correct
7 Correct 107 ms 217808 KB Output is correct
8 Correct 104 ms 217276 KB Output is correct
9 Correct 104 ms 217300 KB Output is correct
10 Correct 103 ms 217544 KB Output is correct
11 Correct 105 ms 217288 KB Output is correct
12 Correct 107 ms 217772 KB Output is correct
13 Correct 188 ms 217736 KB Output is correct
14 Correct 238 ms 217644 KB Output is correct
15 Correct 205 ms 217584 KB Output is correct
16 Runtime error 766 ms 807536 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 100 ms 217296 KB Output is correct
2 Correct 105 ms 217268 KB Output is correct
3 Correct 107 ms 217300 KB Output is correct
4 Correct 175 ms 217472 KB Output is correct
5 Correct 238 ms 217544 KB Output is correct
6 Correct 123 ms 217816 KB Output is correct
7 Correct 112 ms 217808 KB Output is correct
8 Correct 111 ms 217736 KB Output is correct
9 Incorrect 597 ms 231504 KB Output isn't correct
10 Halted 0 ms 0 KB -