oj.uz

답안 #545015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545015 2022-04-03T10:13:53 Z leaked Jail (JOI22_jail) C++14
49 / 100
 706 ms 727816 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=17;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 194764 KB Output is correct
2 Correct 95 ms 194812 KB Output is correct
3 Correct 104 ms 194752 KB Output is correct
4 Correct 146 ms 195012 KB Output is correct
5 Correct 216 ms 194920 KB Output is correct
6 Correct 98 ms 195228 KB Output is correct
7 Correct 95 ms 195228 KB Output is correct
8 Correct 107 ms 195172 KB Output is correct
9 Incorrect 502 ms 207872 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 194760 KB Output is correct
2 Correct 93 ms 194764 KB Output is correct
3 Correct 100 ms 195204 KB Output is correct
4 Correct 103 ms 195208 KB Output is correct
5 Correct 99 ms 195196 KB Output is correct
6 Correct 100 ms 195208 KB Output is correct
7 Correct 105 ms 195236 KB Output is correct
8 Correct 104 ms 195132 KB Output is correct
9 Correct 98 ms 195224 KB Output is correct
10 Correct 96 ms 195148 KB Output is correct
11 Correct 105 ms 195232 KB Output is correct
12 Correct 100 ms 195216 KB Output is correct
13 Correct 95 ms 195224 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 194760 KB Output is correct
2 Correct 93 ms 194764 KB Output is correct
3 Correct 100 ms 195204 KB Output is correct
4 Correct 103 ms 195208 KB Output is correct
5 Correct 99 ms 195196 KB Output is correct
6 Correct 100 ms 195208 KB Output is correct
7 Correct 105 ms 195236 KB Output is correct
8 Correct 104 ms 195132 KB Output is correct
9 Correct 98 ms 195224 KB Output is correct
10 Correct 96 ms 195148 KB Output is correct
11 Correct 105 ms 195232 KB Output is correct
12 Correct 100 ms 195216 KB Output is correct
13 Correct 95 ms 195224 KB Output is correct
14 Correct 92 ms 194876 KB Output is correct
15 Correct 95 ms 194760 KB Output is correct
16 Correct 110 ms 195180 KB Output is correct
17 Correct 116 ms 195232 KB Output is correct
18 Correct 108 ms 195144 KB Output is correct
19 Correct 92 ms 194708 KB Output is correct
20 Correct 96 ms 195252 KB Output is correct
21 Correct 97 ms 195148 KB Output is correct
22 Correct 97 ms 195276 KB Output is correct
23 Correct 90 ms 194720 KB Output is correct
24 Correct 92 ms 194896 KB Output is correct
25 Correct 98 ms 195148 KB Output is correct
26 Correct 94 ms 195072 KB Output is correct
27 Correct 97 ms 195152 KB Output is correct
28 Correct 94 ms 194756 KB Output is correct

Subtask #4
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 194760 KB Output is correct
2 Correct 93 ms 194764 KB Output is correct
3 Correct 100 ms 195204 KB Output is correct
4 Correct 103 ms 195208 KB Output is correct
5 Correct 99 ms 195196 KB Output is correct
6 Correct 100 ms 195208 KB Output is correct
7 Correct 105 ms 195236 KB Output is correct
8 Correct 104 ms 195132 KB Output is correct
9 Correct 98 ms 195224 KB Output is correct
10 Correct 96 ms 195148 KB Output is correct
11 Correct 105 ms 195232 KB Output is correct
12 Correct 100 ms 195216 KB Output is correct
13 Correct 95 ms 195224 KB Output is correct
14 Correct 92 ms 194876 KB Output is correct
15 Correct 95 ms 194760 KB Output is correct
16 Correct 110 ms 195180 KB Output is correct
17 Correct 116 ms 195232 KB Output is correct
18 Correct 108 ms 195144 KB Output is correct
19 Correct 92 ms 194708 KB Output is correct
20 Correct 96 ms 195252 KB Output is correct
21 Correct 97 ms 195148 KB Output is correct
22 Correct 97 ms 195276 KB Output is correct
23 Correct 90 ms 194720 KB Output is correct
24 Correct 92 ms 194896 KB Output is correct
25 Correct 98 ms 195148 KB Output is correct
26 Correct 94 ms 195072 KB Output is correct
27 Correct 97 ms 195152 KB Output is correct
28 Correct 94 ms 194756 KB Output is correct
29 Correct 110 ms 195216 KB Output is correct
30 Correct 97 ms 195272 KB Output is correct
31 Correct 99 ms 195276 KB Output is correct
32 Correct 98 ms 195148 KB Output is correct
33 Correct 98 ms 195172 KB Output is correct
34 Correct 100 ms 195112 KB Output is correct
35 Correct 108 ms 195120 KB Output is correct
36 Correct 96 ms 195188 KB Output is correct
37 Correct 93 ms 195156 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 194760 KB Output is correct
2 Correct 93 ms 194764 KB Output is correct
3 Correct 100 ms 195204 KB Output is correct
4 Correct 103 ms 195208 KB Output is correct
5 Correct 99 ms 195196 KB Output is correct
6 Correct 100 ms 195208 KB Output is correct
7 Correct 105 ms 195236 KB Output is correct
8 Correct 104 ms 195132 KB Output is correct
9 Correct 98 ms 195224 KB Output is correct
10 Correct 96 ms 195148 KB Output is correct
11 Correct 105 ms 195232 KB Output is correct
12 Correct 100 ms 195216 KB Output is correct
13 Correct 95 ms 195224 KB Output is correct
14 Correct 92 ms 194876 KB Output is correct
15 Correct 95 ms 194760 KB Output is correct
16 Correct 110 ms 195180 KB Output is correct
17 Correct 116 ms 195232 KB Output is correct
18 Correct 108 ms 195144 KB Output is correct
19 Correct 92 ms 194708 KB Output is correct
20 Correct 96 ms 195252 KB Output is correct
21 Correct 97 ms 195148 KB Output is correct
22 Correct 97 ms 195276 KB Output is correct
23 Correct 90 ms 194720 KB Output is correct
24 Correct 92 ms 194896 KB Output is correct
25 Correct 98 ms 195148 KB Output is correct
26 Correct 94 ms 195072 KB Output is correct
27 Correct 97 ms 195152 KB Output is correct
28 Correct 94 ms 194756 KB Output is correct
29 Correct 110 ms 195216 KB Output is correct
30 Correct 97 ms 195272 KB Output is correct
31 Correct 99 ms 195276 KB Output is correct
32 Correct 98 ms 195148 KB Output is correct
33 Correct 98 ms 195172 KB Output is correct
34 Correct 100 ms 195112 KB Output is correct
35 Correct 108 ms 195120 KB Output is correct
36 Correct 96 ms 195188 KB Output is correct
37 Correct 93 ms 195156 KB Output is correct
38 Incorrect 511 ms 207924 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 194704 KB Output is correct
2 Correct 95 ms 194692 KB Output is correct
3 Correct 93 ms 194816 KB Output is correct
4 Correct 91 ms 194788 KB Output is correct
5 Correct 111 ms 194828 KB Output is correct
6 Correct 96 ms 195104 KB Output is correct
7 Correct 94 ms 195148 KB Output is correct
8 Correct 95 ms 194756 KB Output is correct
9 Correct 93 ms 194896 KB Output is correct
10 Correct 98 ms 194996 KB Output is correct
11 Correct 96 ms 194740 KB Output is correct
12 Correct 94 ms 195188 KB Output is correct
13 Correct 167 ms 195272 KB Output is correct
14 Correct 215 ms 195132 KB Output is correct
15 Correct 188 ms 195032 KB Output is correct
16 Runtime error 706 ms 727816 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 194764 KB Output is correct
2 Correct 95 ms 194812 KB Output is correct
3 Correct 104 ms 194752 KB Output is correct
4 Correct 146 ms 195012 KB Output is correct
5 Correct 216 ms 194920 KB Output is correct
6 Correct 98 ms 195228 KB Output is correct
7 Correct 95 ms 195228 KB Output is correct
8 Correct 107 ms 195172 KB Output is correct
9 Incorrect 502 ms 207872 KB Output isn't correct
10 Halted 0 ms 0 KB -