oj.uz

Submission #709486

# Submission time Handle Problem Language Result Execution time Memory
709486 2023-03-13T17:03:13 Z urosk Jail (JOI22_jail) C++14
49 / 100
 432 ms 303868 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 int
#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 64 ms 141256 KB Output is correct
2 Correct 73 ms 141212 KB Output is correct
3 Correct 73 ms 141144 KB Output is correct
4 Correct 171 ms 141472 KB Output is correct
5 Correct 259 ms 141568 KB Output is correct
6 Correct 79 ms 141820 KB Output is correct
7 Correct 91 ms 141724 KB Output is correct
8 Correct 85 ms 141656 KB Output is correct
9 Correct 432 ms 152808 KB Output is correct
10 Runtime error 362 ms 303868 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 70 ms 141232 KB Output is correct
2 Correct 69 ms 141132 KB Output is correct
3 Correct 86 ms 141712 KB Output is correct
4 Correct 77 ms 141624 KB Output is correct
5 Correct 75 ms 141720 KB Output is correct
6 Correct 76 ms 141764 KB Output is correct
7 Correct 78 ms 141672 KB Output is correct
8 Correct 77 ms 141620 KB Output is correct
9 Correct 90 ms 141712 KB Output is correct
10 Correct 85 ms 141808 KB Output is correct
11 Correct 78 ms 141644 KB Output is correct
12 Correct 68 ms 141672 KB Output is correct
13 Correct 80 ms 141720 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 141232 KB Output is correct
2 Correct 69 ms 141132 KB Output is correct
3 Correct 86 ms 141712 KB Output is correct
4 Correct 77 ms 141624 KB Output is correct
5 Correct 75 ms 141720 KB Output is correct
6 Correct 76 ms 141764 KB Output is correct
7 Correct 78 ms 141672 KB Output is correct
8 Correct 77 ms 141620 KB Output is correct
9 Correct 90 ms 141712 KB Output is correct
10 Correct 85 ms 141808 KB Output is correct
11 Correct 78 ms 141644 KB Output is correct
12 Correct 68 ms 141672 KB Output is correct
13 Correct 80 ms 141720 KB Output is correct
14 Correct 72 ms 141164 KB Output is correct
15 Correct 66 ms 141192 KB Output is correct
16 Correct 76 ms 141652 KB Output is correct
17 Correct 75 ms 141712 KB Output is correct
18 Correct 87 ms 141620 KB Output is correct
19 Correct 86 ms 141200 KB Output is correct
20 Correct 79 ms 141716 KB Output is correct
21 Correct 76 ms 141660 KB Output is correct
22 Correct 74 ms 141644 KB Output is correct
23 Correct 70 ms 141220 KB Output is correct
24 Correct 74 ms 141396 KB Output is correct
25 Correct 90 ms 141732 KB Output is correct
26 Correct 74 ms 141664 KB Output is correct
27 Correct 76 ms 141656 KB Output is correct
28 Correct 67 ms 141292 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 141232 KB Output is correct
2 Correct 69 ms 141132 KB Output is correct
3 Correct 86 ms 141712 KB Output is correct
4 Correct 77 ms 141624 KB Output is correct
5 Correct 75 ms 141720 KB Output is correct
6 Correct 76 ms 141764 KB Output is correct
7 Correct 78 ms 141672 KB Output is correct
8 Correct 77 ms 141620 KB Output is correct
9 Correct 90 ms 141712 KB Output is correct
10 Correct 85 ms 141808 KB Output is correct
11 Correct 78 ms 141644 KB Output is correct
12 Correct 68 ms 141672 KB Output is correct
13 Correct 80 ms 141720 KB Output is correct
14 Correct 72 ms 141164 KB Output is correct
15 Correct 66 ms 141192 KB Output is correct
16 Correct 76 ms 141652 KB Output is correct
17 Correct 75 ms 141712 KB Output is correct
18 Correct 87 ms 141620 KB Output is correct
19 Correct 86 ms 141200 KB Output is correct
20 Correct 79 ms 141716 KB Output is correct
21 Correct 76 ms 141660 KB Output is correct
22 Correct 74 ms 141644 KB Output is correct
23 Correct 70 ms 141220 KB Output is correct
24 Correct 74 ms 141396 KB Output is correct
25 Correct 90 ms 141732 KB Output is correct
26 Correct 74 ms 141664 KB Output is correct
27 Correct 76 ms 141656 KB Output is correct
28 Correct 67 ms 141292 KB Output is correct
29 Correct 75 ms 141712 KB Output is correct
30 Correct 85 ms 141740 KB Output is correct
31 Correct 90 ms 141668 KB Output is correct
32 Correct 77 ms 141692 KB Output is correct
33 Correct 74 ms 141700 KB Output is correct
34 Correct 76 ms 141644 KB Output is correct
35 Correct 84 ms 141768 KB Output is correct
36 Correct 81 ms 141712 KB Output is correct
37 Correct 71 ms 141644 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 141232 KB Output is correct
2 Correct 69 ms 141132 KB Output is correct
3 Correct 86 ms 141712 KB Output is correct
4 Correct 77 ms 141624 KB Output is correct
5 Correct 75 ms 141720 KB Output is correct
6 Correct 76 ms 141764 KB Output is correct
7 Correct 78 ms 141672 KB Output is correct
8 Correct 77 ms 141620 KB Output is correct
9 Correct 90 ms 141712 KB Output is correct
10 Correct 85 ms 141808 KB Output is correct
11 Correct 78 ms 141644 KB Output is correct
12 Correct 68 ms 141672 KB Output is correct
13 Correct 80 ms 141720 KB Output is correct
14 Correct 72 ms 141164 KB Output is correct
15 Correct 66 ms 141192 KB Output is correct
16 Correct 76 ms 141652 KB Output is correct
17 Correct 75 ms 141712 KB Output is correct
18 Correct 87 ms 141620 KB Output is correct
19 Correct 86 ms 141200 KB Output is correct
20 Correct 79 ms 141716 KB Output is correct
21 Correct 76 ms 141660 KB Output is correct
22 Correct 74 ms 141644 KB Output is correct
23 Correct 70 ms 141220 KB Output is correct
24 Correct 74 ms 141396 KB Output is correct
25 Correct 90 ms 141732 KB Output is correct
26 Correct 74 ms 141664 KB Output is correct
27 Correct 76 ms 141656 KB Output is correct
28 Correct 67 ms 141292 KB Output is correct
29 Correct 75 ms 141712 KB Output is correct
30 Correct 85 ms 141740 KB Output is correct
31 Correct 90 ms 141668 KB Output is correct
32 Correct 77 ms 141692 KB Output is correct
33 Correct 74 ms 141700 KB Output is correct
34 Correct 76 ms 141644 KB Output is correct
35 Correct 84 ms 141768 KB Output is correct
36 Correct 81 ms 141712 KB Output is correct
37 Correct 71 ms 141644 KB Output is correct
38 Correct 430 ms 152684 KB Output is correct
39 Runtime error 357 ms 303820 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 73 ms 141252 KB Output is correct
2 Correct 75 ms 141252 KB Output is correct
3 Correct 81 ms 141140 KB Output is correct
4 Correct 69 ms 141240 KB Output is correct
5 Correct 106 ms 141276 KB Output is correct
6 Correct 71 ms 141716 KB Output is correct
7 Correct 71 ms 141644 KB Output is correct
8 Correct 69 ms 141176 KB Output is correct
9 Correct 79 ms 141132 KB Output is correct
10 Correct 70 ms 141380 KB Output is correct
11 Correct 66 ms 141180 KB Output is correct
12 Correct 76 ms 141604 KB Output is correct
13 Correct 203 ms 141540 KB Output is correct
14 Correct 310 ms 141604 KB Output is correct
15 Correct 254 ms 141516 KB Output is correct
16 Runtime error 408 ms 301900 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 64 ms 141256 KB Output is correct
2 Correct 73 ms 141212 KB Output is correct
3 Correct 73 ms 141144 KB Output is correct
4 Correct 171 ms 141472 KB Output is correct
5 Correct 259 ms 141568 KB Output is correct
6 Correct 79 ms 141820 KB Output is correct
7 Correct 91 ms 141724 KB Output is correct
8 Correct 85 ms 141656 KB Output is correct
9 Correct 432 ms 152808 KB Output is correct
10 Runtime error 362 ms 303868 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -