oj.uz

Submission #709484

# Submission time Handle Problem Language Result Execution time Memory
709484 2023-03-13T17:00:28 Z urosk Jail (JOI22_jail) C++14
49 / 100
 461 ms 330912 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
//using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
#define maxn 3000005
#define lg 22
ll n,m;
vector<ll> g[maxn];
vector<ll> v[maxn];
ll tsz = 0;
ll id[maxn][lg][2];
ll st[maxn][lg];
ll in[maxn],out[maxn],ti = 0;
bool intree(ll x,ll y){return in[y]<=in[x]&&out[x]<=out[y];}
ll lca(ll x,ll y){
    if(intree(x,y)) return y;
    if(intree(y,x)) return x;
    for(ll j = lg-1;j>=0;j--){
        if(!intree(x,st[y][j])) y = st[y][j];
    }
    return st[y][0];
}
void dfs(ll u,ll p){
    in[u] = ++ti;
    st[u][0] = p;
    for(ll s : g[u]) if(s!=p) dfs(s,u);
    out[u] = ti-1;
}
ll get(ll x,ll y){
    for(ll j = lg-1;j>=0;j--){
        if(!intree(y,st[x][j])) x = st[x][j];
    }
    return x;
}
void add(ll x,ll y,bool smer,ll nod){
    for(ll j = lg-1;j>=0;j--){
        if(!intree(y,st[x][j])){
            if(smer) v[id[x][j][1]].pb(nod);
            else v[nod].pb(id[x][j][0]);
            x = st[x][j];
        }
    }
    if(smer) v[id[x][0][1]].pb(nod);
    else v[nod].pb(id[x][0][0]);
    if(smer) v[id[y][0][1]].pb(nod);
    else v[nod].pb(id[y][0][0]);
}
ll deg[maxn];
void tc(){
    ti = 0;
    cin >> n;
    for(ll i = 1;i<=n-1;i++){
        ll x,y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1,1);
    for(ll i = 1;i<=n;i++) id[i][0][0] = i,id[i][0][1] = i+n;
    tsz = 2*n;
    for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++){
        st[i][j] = st[st[i][j-1]][j-1];
        ++tsz;
        id[i][j][0] = tsz;
        v[tsz].pb(id[i][j-1][0]);
        v[tsz].pb(id[st[i][j-1]][j-1][0]);
        ++tsz;
        id[i][j][1] = tsz;
        v[id[i][j-1][1]].pb(tsz);
        v[id[st[i][j-1]][j-1][1]].pb(tsz);
    }
    cin >> m;
    for(ll i = 1;i<=m;i++){
        ll x,y; cin >> x >> y;
        ++tsz;
        v[x].pb(tsz);
        v[tsz].pb(n+y);
        ll z = lca(x,y);
        if(z!=x){
            add(x,get(x,z),1,tsz);
            add(st[x][0],z,0,tsz);
        }
        if(z!=y){
            add(y,get(y,z),0,tsz);
            add(st[y][0],z,1,tsz);
        }
    }
    queue<ll> q;
    for(ll i = 1;i<=tsz;i++) deg[i] = 0;
    for(ll i = 1;i<=tsz;i++){
        for(ll j : v[i]) deg[j]++;
    }
    for(ll i = 1;i<=tsz;i++){
        if(!deg[i]) q.push(i);
    }
    ll cnt = 0;
    while(q.size()){
        ll x = q.front();
        q.pop();
        cnt++;
        for(ll y : v[x]){
            deg[y]--;
            if(!deg[y]) q.push(y);
        }
    }
    if(cnt!=tsz) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    for(ll i = 1;i<=n;i++) g[i].clear();
    for(ll i = 1;i<=tsz;i++) v[i].clear();
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    cin >> t;
    while(t--){
        tc();
    }
	return 0;
}
/**
1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2
3 4
4 8

2
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
4
1 2
1 3
1 4
3
2 3
3 4
4 2

3
3
1 2
2 3
2
2 1
3 2
7
1 2
2 3
3 4
4 5
5 6
6 7
3
1 3
4 2
2 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 5
2 6
3 7
4 8
**/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 141192 KB Output is correct
2 Correct 68 ms 141240 KB Output is correct
3 Correct 72 ms 141144 KB Output is correct
4 Correct 165 ms 141644 KB Output is correct
5 Correct 273 ms 141656 KB Output is correct
6 Correct 88 ms 141772 KB Output is correct
7 Correct 83 ms 141864 KB Output is correct
8 Correct 78 ms 141904 KB Output is correct
9 Correct 423 ms 156976 KB Output is correct
10 Runtime error 428 ms 326168 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 141228 KB Output is correct
2 Correct 69 ms 141124 KB Output is correct
3 Correct 84 ms 141760 KB Output is correct
4 Correct 82 ms 141772 KB Output is correct
5 Correct 88 ms 141880 KB Output is correct
6 Correct 75 ms 141856 KB Output is correct
7 Correct 79 ms 141772 KB Output is correct
8 Correct 90 ms 141876 KB Output is correct
9 Correct 93 ms 141848 KB Output is correct
10 Correct 78 ms 141912 KB Output is correct
11 Correct 78 ms 141812 KB Output is correct
12 Correct 72 ms 141808 KB Output is correct
13 Correct 80 ms 141764 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 141228 KB Output is correct
2 Correct 69 ms 141124 KB Output is correct
3 Correct 84 ms 141760 KB Output is correct
4 Correct 82 ms 141772 KB Output is correct
5 Correct 88 ms 141880 KB Output is correct
6 Correct 75 ms 141856 KB Output is correct
7 Correct 79 ms 141772 KB Output is correct
8 Correct 90 ms 141876 KB Output is correct
9 Correct 93 ms 141848 KB Output is correct
10 Correct 78 ms 141912 KB Output is correct
11 Correct 78 ms 141812 KB Output is correct
12 Correct 72 ms 141808 KB Output is correct
13 Correct 80 ms 141764 KB Output is correct
14 Correct 86 ms 141148 KB Output is correct
15 Correct 73 ms 141152 KB Output is correct
16 Correct 76 ms 141744 KB Output is correct
17 Correct 77 ms 141848 KB Output is correct
18 Correct 78 ms 141904 KB Output is correct
19 Correct 85 ms 141240 KB Output is correct
20 Correct 87 ms 141900 KB Output is correct
21 Correct 77 ms 141900 KB Output is correct
22 Correct 76 ms 141816 KB Output is correct
23 Correct 77 ms 141264 KB Output is correct
24 Correct 75 ms 141520 KB Output is correct
25 Correct 81 ms 141852 KB Output is correct
26 Correct 69 ms 141772 KB Output is correct
27 Correct 95 ms 141888 KB Output is correct
28 Correct 91 ms 141240 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 141228 KB Output is correct
2 Correct 69 ms 141124 KB Output is correct
3 Correct 84 ms 141760 KB Output is correct
4 Correct 82 ms 141772 KB Output is correct
5 Correct 88 ms 141880 KB Output is correct
6 Correct 75 ms 141856 KB Output is correct
7 Correct 79 ms 141772 KB Output is correct
8 Correct 90 ms 141876 KB Output is correct
9 Correct 93 ms 141848 KB Output is correct
10 Correct 78 ms 141912 KB Output is correct
11 Correct 78 ms 141812 KB Output is correct
12 Correct 72 ms 141808 KB Output is correct
13 Correct 80 ms 141764 KB Output is correct
14 Correct 86 ms 141148 KB Output is correct
15 Correct 73 ms 141152 KB Output is correct
16 Correct 76 ms 141744 KB Output is correct
17 Correct 77 ms 141848 KB Output is correct
18 Correct 78 ms 141904 KB Output is correct
19 Correct 85 ms 141240 KB Output is correct
20 Correct 87 ms 141900 KB Output is correct
21 Correct 77 ms 141900 KB Output is correct
22 Correct 76 ms 141816 KB Output is correct
23 Correct 77 ms 141264 KB Output is correct
24 Correct 75 ms 141520 KB Output is correct
25 Correct 81 ms 141852 KB Output is correct
26 Correct 69 ms 141772 KB Output is correct
27 Correct 95 ms 141888 KB Output is correct
28 Correct 91 ms 141240 KB Output is correct
29 Correct 94 ms 141900 KB Output is correct
30 Correct 84 ms 141792 KB Output is correct
31 Correct 86 ms 141972 KB Output is correct
32 Correct 84 ms 141912 KB Output is correct
33 Correct 94 ms 141840 KB Output is correct
34 Correct 84 ms 141688 KB Output is correct
35 Correct 82 ms 141808 KB Output is correct
36 Correct 81 ms 141900 KB Output is correct
37 Correct 91 ms 141772 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 141228 KB Output is correct
2 Correct 69 ms 141124 KB Output is correct
3 Correct 84 ms 141760 KB Output is correct
4 Correct 82 ms 141772 KB Output is correct
5 Correct 88 ms 141880 KB Output is correct
6 Correct 75 ms 141856 KB Output is correct
7 Correct 79 ms 141772 KB Output is correct
8 Correct 90 ms 141876 KB Output is correct
9 Correct 93 ms 141848 KB Output is correct
10 Correct 78 ms 141912 KB Output is correct
11 Correct 78 ms 141812 KB Output is correct
12 Correct 72 ms 141808 KB Output is correct
13 Correct 80 ms 141764 KB Output is correct
14 Correct 86 ms 141148 KB Output is correct
15 Correct 73 ms 141152 KB Output is correct
16 Correct 76 ms 141744 KB Output is correct
17 Correct 77 ms 141848 KB Output is correct
18 Correct 78 ms 141904 KB Output is correct
19 Correct 85 ms 141240 KB Output is correct
20 Correct 87 ms 141900 KB Output is correct
21 Correct 77 ms 141900 KB Output is correct
22 Correct 76 ms 141816 KB Output is correct
23 Correct 77 ms 141264 KB Output is correct
24 Correct 75 ms 141520 KB Output is correct
25 Correct 81 ms 141852 KB Output is correct
26 Correct 69 ms 141772 KB Output is correct
27 Correct 95 ms 141888 KB Output is correct
28 Correct 91 ms 141240 KB Output is correct
29 Correct 94 ms 141900 KB Output is correct
30 Correct 84 ms 141792 KB Output is correct
31 Correct 86 ms 141972 KB Output is correct
32 Correct 84 ms 141912 KB Output is correct
33 Correct 94 ms 141840 KB Output is correct
34 Correct 84 ms 141688 KB Output is correct
35 Correct 82 ms 141808 KB Output is correct
36 Correct 81 ms 141900 KB Output is correct
37 Correct 91 ms 141772 KB Output is correct
38 Correct 461 ms 156864 KB Output is correct
39 Runtime error 382 ms 326088 KB Execution killed with signal 6
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 141272 KB Output is correct
2 Correct 73 ms 141208 KB Output is correct
3 Correct 77 ms 141260 KB Output is correct
4 Correct 82 ms 141252 KB Output is correct
5 Correct 114 ms 141304 KB Output is correct
6 Correct 77 ms 141856 KB Output is correct
7 Correct 82 ms 141872 KB Output is correct
8 Correct 81 ms 141280 KB Output is correct
9 Correct 75 ms 141220 KB Output is correct
10 Correct 86 ms 141688 KB Output is correct
11 Correct 73 ms 141228 KB Output is correct
12 Correct 88 ms 141840 KB Output is correct
13 Correct 188 ms 141692 KB Output is correct
14 Correct 320 ms 141592 KB Output is correct
15 Correct 253 ms 141868 KB Output is correct
16 Runtime error 432 ms 330912 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 141192 KB Output is correct
2 Correct 68 ms 141240 KB Output is correct
3 Correct 72 ms 141144 KB Output is correct
4 Correct 165 ms 141644 KB Output is correct
5 Correct 273 ms 141656 KB Output is correct
6 Correct 88 ms 141772 KB Output is correct
7 Correct 83 ms 141864 KB Output is correct
8 Correct 78 ms 141904 KB Output is correct
9 Correct 423 ms 156976 KB Output is correct
10 Runtime error 428 ms 326168 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -