oj.uz

답안 #567162

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567162 2022-05-23T08:37:53 Z zaneyu Jail (JOI22_jail) C++14
5 / 100
 1987 ms 413236 KB 
/*input
1
5
1 2
1 3
1 4
4 5
2
1 2
2 5
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-6;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mypow(ll a,ll b){
    a%=MOD;
    if(a==0) return 0;
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
bool wk=1;
vector<int> v[maxn];
int in[maxn],out[maxn];
vector<int> vv[maxn*40];
int vis[maxn*40];
int par[maxn][20];
int dep[maxn];
int cur;
int idx[maxn][20],idx2[maxn][20];

void dfs(int u,int p){
    par[u][0]=p;
    idx[u][0]=(cur++);
    idx2[u][0]=(cur++);
    if(in[u]) vv[in[u]].pb(idx[u][0]);
    if(out[u]) vv[idx2[u][0]].pb(out[u]);
    REP1(j,19){
        if(par[u][j-1]!=-1){
            par[u][j]=par[par[u][j-1]][j-1];
            idx[u][j]=(cur++);
            idx2[u][j]=(cur++);
            vv[idx2[u][j]].pb(idx2[u][j-1]);
            if(idx2[par[u][j-1]][j-1]) vv[idx2[u][j]].pb(idx2[par[u][j-1]][j-1]);
            vv[idx[u][j-1]].pb(idx[u][j]);
            if(idx[par[u][j-1]][j-1]) vv[idx[par[u][j-1]][j-1]].pb(idx[u][j]); 
        }
        else par[u][j]=-1;
    }
    for(int x:v[u]){
        if(x==p) continue;
        dep[x]=dep[u]+1;
        dfs(x,u);
    }
}

void dfs2(int u){
    vis[u]=1;
    for(int x:vv[u]){
        if(!vis[x]) dfs2(x);
        else if(vis[x]==1){
            wk=0;
            break;
        }
    }
    vis[u]=2;
}
int get(int a,int d){
    while(d){
        int z=__lg(lowb(d));
        a=par[a][z];
        d-=lowb(d);
    }
    return a;
}
void solve(){
    int n,m;
    cin>>n;
    REP(i,n-1){
        int a,b;
        cin>>a>>b;
        --a,--b;
        v[a].pb(b),v[b].pb(a);
    }
    cin>>m;
    vector<pii> asd;
    REP1(i,m){
        int a,b;
        cin>>a>>b;
        --a,--b;
        in[a]=i,out[b]=i;
        asd.pb({a,b});
    }
    cur=m+1;
    dfs(0,-1);
    REP1(i,m){
        int a=asd[i-1].f,b=asd[i-1].s;
        int cur=i;
        if(in[b]) vv[in[b]].pb(i);
        if(out[a]) vv[i].pb(out[a]);
        if(dep[a]<dep[b]) swap(a,b);
        int d=dep[a]-dep[b];
        if(get(a,d)==b){
            --d;
            a=par[a][0];
        }
        else{
            a=par[a][0],b=par[b][0];
            if(get(a,d)==b){
                if(in[b]) vv[in[b]].pb(i);
                if(out[b]) vv[i].pb(out[b]);
            }
        }
        while(d){
            int z=__lg(lowb(d));
            vv[idx[a][z]].pb(cur);
            vv[cur].pb(idx2[a][z]);
            a=par[a][z];
            d-=lowb(d);
        }
        if(a==b) continue;
        for(int j=19;j>=0;j--){
            if(par[a][j]!=par[b][j]){
                vv[cur].pb(idx2[a][j]);
                vv[cur].pb(idx2[b][j]);
                vv[idx[a][j]].pb(cur);
                vv[idx[b][j]].pb(cur);
                a=par[a][j],b=par[b][j];
            }
        }
        int j=0;
        vv[cur].pb(idx2[a][j]);
        vv[cur].pb(idx2[b][j]);
        vv[idx[a][j]].pb(cur);
        vv[idx[b][j]].pb(cur);
        a=par[a][j],b=par[b][j];
        if(in[a]) vv[in[a]].pb(i);
        if(out[a]) vv[i].pb(out[a]);
    }
    //REP1(i,cur-1) cout<<i<<' '<<vv[i]<<'\n';
    wk=1;
    REP1(i,cur-1){
        if(!vis[i]) dfs2(i);
    }
    if(wk){
        cout<<"Yes\n";
    }
    else cout<<"No\n";
    REP(i,n) v[i].clear(),in[i]=out[i]=0;
    REP1(i,cur) vv[i].clear(),vis[i]=0;
}
int main(){
    int t;
    cin>>t;
    while(t--) solve();
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 192932 KB Output is correct
2 Correct 98 ms 192804 KB Output is correct
3 Correct 87 ms 192872 KB Output is correct
4 Correct 127 ms 192972 KB Output is correct
5 Correct 211 ms 192996 KB Output is correct
6 Correct 105 ms 193100 KB Output is correct
7 Correct 91 ms 193064 KB Output is correct
8 Correct 103 ms 193084 KB Output is correct
9 Correct 438 ms 200428 KB Output is correct
10 Correct 1161 ms 372900 KB Output is correct
11 Correct 112 ms 192856 KB Output is correct
12 Correct 211 ms 193132 KB Output is correct
13 Correct 1277 ms 377556 KB Output is correct
14 Correct 1085 ms 377732 KB Output is correct
15 Correct 1572 ms 388148 KB Output is correct
16 Correct 1987 ms 413236 KB Output is correct
17 Correct 1383 ms 381916 KB Output is correct
18 Correct 1226 ms 381704 KB Output is correct
19 Correct 1297 ms 381916 KB Output is correct
20 Correct 1319 ms 381868 KB Output is correct
21 Correct 1358 ms 383100 KB Output is correct
22 Correct 1027 ms 377256 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 192888 KB Output is correct
2 Correct 95 ms 192888 KB Output is correct
3 Correct 98 ms 193048 KB Output is correct
4 Correct 95 ms 193072 KB Output is correct
5 Correct 108 ms 193036 KB Output is correct
6 Correct 101 ms 193072 KB Output is correct
7 Correct 110 ms 193076 KB Output is correct
8 Incorrect 93 ms 193052 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 192888 KB Output is correct
2 Correct 95 ms 192888 KB Output is correct
3 Correct 98 ms 193048 KB Output is correct
4 Correct 95 ms 193072 KB Output is correct
5 Correct 108 ms 193036 KB Output is correct
6 Correct 101 ms 193072 KB Output is correct
7 Correct 110 ms 193076 KB Output is correct
8 Incorrect 93 ms 193052 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 192888 KB Output is correct
2 Correct 95 ms 192888 KB Output is correct
3 Correct 98 ms 193048 KB Output is correct
4 Correct 95 ms 193072 KB Output is correct
5 Correct 108 ms 193036 KB Output is correct
6 Correct 101 ms 193072 KB Output is correct
7 Correct 110 ms 193076 KB Output is correct
8 Incorrect 93 ms 193052 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 192888 KB Output is correct
2 Correct 95 ms 192888 KB Output is correct
3 Correct 98 ms 193048 KB Output is correct
4 Correct 95 ms 193072 KB Output is correct
5 Correct 108 ms 193036 KB Output is correct
6 Correct 101 ms 193072 KB Output is correct
7 Correct 110 ms 193076 KB Output is correct
8 Incorrect 93 ms 193052 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 192888 KB Output is correct
2 Correct 93 ms 192932 KB Output is correct
3 Correct 89 ms 192876 KB Output is correct
4 Correct 93 ms 192812 KB Output is correct
5 Correct 109 ms 192844 KB Output is correct
6 Correct 109 ms 193112 KB Output is correct
7 Correct 95 ms 192984 KB Output is correct
8 Correct 102 ms 192860 KB Output is correct
9 Correct 90 ms 193000 KB Output is correct
10 Incorrect 108 ms 192932 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 192932 KB Output is correct
2 Correct 98 ms 192804 KB Output is correct
3 Correct 87 ms 192872 KB Output is correct
4 Correct 127 ms 192972 KB Output is correct
5 Correct 211 ms 192996 KB Output is correct
6 Correct 105 ms 193100 KB Output is correct
7 Correct 91 ms 193064 KB Output is correct
8 Correct 103 ms 193084 KB Output is correct
9 Correct 438 ms 200428 KB Output is correct
10 Correct 1161 ms 372900 KB Output is correct
11 Correct 112 ms 192856 KB Output is correct
12 Correct 211 ms 193132 KB Output is correct
13 Correct 1277 ms 377556 KB Output is correct
14 Correct 1085 ms 377732 KB Output is correct
15 Correct 1572 ms 388148 KB Output is correct
16 Correct 1987 ms 413236 KB Output is correct
17 Correct 1383 ms 381916 KB Output is correct
18 Correct 1226 ms 381704 KB Output is correct
19 Correct 1297 ms 381916 KB Output is correct
20 Correct 1319 ms 381868 KB Output is correct
21 Correct 1358 ms 383100 KB Output is correct
22 Correct 1027 ms 377256 KB Output is correct
23 Correct 107 ms 192888 KB Output is correct
24 Correct 95 ms 192888 KB Output is correct
25 Correct 98 ms 193048 KB Output is correct
26 Correct 95 ms 193072 KB Output is correct
27 Correct 108 ms 193036 KB Output is correct
28 Correct 101 ms 193072 KB Output is correct
29 Correct 110 ms 193076 KB Output is correct
30 Incorrect 93 ms 193052 KB Output isn't correct
31 Halted 0 ms 0 KB -