oj.uz

Submission #709488

# Submission time Handle Problem Language Result Execution time Memory
709488 2023-03-13T17:05:12 Z urosk Jail (JOI22_jail) C++14
100 / 100
 1836 ms 526728 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 6000005
#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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 282060 KB Output is correct
2 Correct 135 ms 282216 KB Output is correct
3 Correct 132 ms 282044 KB Output is correct
4 Correct 208 ms 282372 KB Output is correct
5 Correct 321 ms 282600 KB Output is correct
6 Correct 137 ms 282608 KB Output is correct
7 Correct 140 ms 282572 KB Output is correct
8 Correct 136 ms 282628 KB Output is correct
9 Correct 502 ms 293688 KB Output is correct
10 Correct 839 ms 505336 KB Output is correct
11 Correct 171 ms 282264 KB Output is correct
12 Correct 361 ms 283316 KB Output is correct
13 Correct 1045 ms 511588 KB Output is correct
14 Correct 847 ms 511600 KB Output is correct
15 Correct 1134 ms 512988 KB Output is correct
16 Correct 1568 ms 522620 KB Output is correct
17 Correct 946 ms 514216 KB Output is correct
18 Correct 918 ms 515740 KB Output is correct
19 Correct 977 ms 514140 KB Output is correct
20 Correct 865 ms 514132 KB Output is correct
21 Correct 921 ms 514640 KB Output is correct
22 Correct 819 ms 511408 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 282052 KB Output is correct
2 Correct 128 ms 282248 KB Output is correct
3 Correct 149 ms 282572 KB Output is correct
4 Correct 137 ms 282564 KB Output is correct
5 Correct 139 ms 282628 KB Output is correct
6 Correct 149 ms 282712 KB Output is correct
7 Correct 135 ms 282540 KB Output is correct
8 Correct 141 ms 282608 KB Output is correct
9 Correct 142 ms 282516 KB Output is correct
10 Correct 144 ms 282572 KB Output is correct
11 Correct 144 ms 282604 KB Output is correct
12 Correct 143 ms 282540 KB Output is correct
13 Correct 137 ms 282588 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 282052 KB Output is correct
2 Correct 128 ms 282248 KB Output is correct
3 Correct 149 ms 282572 KB Output is correct
4 Correct 137 ms 282564 KB Output is correct
5 Correct 139 ms 282628 KB Output is correct
6 Correct 149 ms 282712 KB Output is correct
7 Correct 135 ms 282540 KB Output is correct
8 Correct 141 ms 282608 KB Output is correct
9 Correct 142 ms 282516 KB Output is correct
10 Correct 144 ms 282572 KB Output is correct
11 Correct 144 ms 282604 KB Output is correct
12 Correct 143 ms 282540 KB Output is correct
13 Correct 137 ms 282588 KB Output is correct
14 Correct 147 ms 282108 KB Output is correct
15 Correct 131 ms 282116 KB Output is correct
16 Correct 141 ms 282584 KB Output is correct
17 Correct 142 ms 282612 KB Output is correct
18 Correct 142 ms 282556 KB Output is correct
19 Correct 133 ms 282104 KB Output is correct
20 Correct 155 ms 282616 KB Output is correct
21 Correct 156 ms 282616 KB Output is correct
22 Correct 135 ms 282660 KB Output is correct
23 Correct 135 ms 282240 KB Output is correct
24 Correct 124 ms 282396 KB Output is correct
25 Correct 146 ms 282648 KB Output is correct
26 Correct 141 ms 282564 KB Output is correct
27 Correct 153 ms 282540 KB Output is correct
28 Correct 130 ms 282188 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 282052 KB Output is correct
2 Correct 128 ms 282248 KB Output is correct
3 Correct 149 ms 282572 KB Output is correct
4 Correct 137 ms 282564 KB Output is correct
5 Correct 139 ms 282628 KB Output is correct
6 Correct 149 ms 282712 KB Output is correct
7 Correct 135 ms 282540 KB Output is correct
8 Correct 141 ms 282608 KB Output is correct
9 Correct 142 ms 282516 KB Output is correct
10 Correct 144 ms 282572 KB Output is correct
11 Correct 144 ms 282604 KB Output is correct
12 Correct 143 ms 282540 KB Output is correct
13 Correct 137 ms 282588 KB Output is correct
14 Correct 147 ms 282108 KB Output is correct
15 Correct 131 ms 282116 KB Output is correct
16 Correct 141 ms 282584 KB Output is correct
17 Correct 142 ms 282612 KB Output is correct
18 Correct 142 ms 282556 KB Output is correct
19 Correct 133 ms 282104 KB Output is correct
20 Correct 155 ms 282616 KB Output is correct
21 Correct 156 ms 282616 KB Output is correct
22 Correct 135 ms 282660 KB Output is correct
23 Correct 135 ms 282240 KB Output is correct
24 Correct 124 ms 282396 KB Output is correct
25 Correct 146 ms 282648 KB Output is correct
26 Correct 141 ms 282564 KB Output is correct
27 Correct 153 ms 282540 KB Output is correct
28 Correct 130 ms 282188 KB Output is correct
29 Correct 167 ms 282528 KB Output is correct
30 Correct 144 ms 282640 KB Output is correct
31 Correct 143 ms 282780 KB Output is correct
32 Correct 138 ms 282660 KB Output is correct
33 Correct 142 ms 282632 KB Output is correct
34 Correct 139 ms 282548 KB Output is correct
35 Correct 139 ms 282540 KB Output is correct
36 Correct 149 ms 282628 KB Output is correct
37 Correct 151 ms 282520 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 282052 KB Output is correct
2 Correct 128 ms 282248 KB Output is correct
3 Correct 149 ms 282572 KB Output is correct
4 Correct 137 ms 282564 KB Output is correct
5 Correct 139 ms 282628 KB Output is correct
6 Correct 149 ms 282712 KB Output is correct
7 Correct 135 ms 282540 KB Output is correct
8 Correct 141 ms 282608 KB Output is correct
9 Correct 142 ms 282516 KB Output is correct
10 Correct 144 ms 282572 KB Output is correct
11 Correct 144 ms 282604 KB Output is correct
12 Correct 143 ms 282540 KB Output is correct
13 Correct 137 ms 282588 KB Output is correct
14 Correct 147 ms 282108 KB Output is correct
15 Correct 131 ms 282116 KB Output is correct
16 Correct 141 ms 282584 KB Output is correct
17 Correct 142 ms 282612 KB Output is correct
18 Correct 142 ms 282556 KB Output is correct
19 Correct 133 ms 282104 KB Output is correct
20 Correct 155 ms 282616 KB Output is correct
21 Correct 156 ms 282616 KB Output is correct
22 Correct 135 ms 282660 KB Output is correct
23 Correct 135 ms 282240 KB Output is correct
24 Correct 124 ms 282396 KB Output is correct
25 Correct 146 ms 282648 KB Output is correct
26 Correct 141 ms 282564 KB Output is correct
27 Correct 153 ms 282540 KB Output is correct
28 Correct 130 ms 282188 KB Output is correct
29 Correct 167 ms 282528 KB Output is correct
30 Correct 144 ms 282640 KB Output is correct
31 Correct 143 ms 282780 KB Output is correct
32 Correct 138 ms 282660 KB Output is correct
33 Correct 142 ms 282632 KB Output is correct
34 Correct 139 ms 282548 KB Output is correct
35 Correct 139 ms 282540 KB Output is correct
36 Correct 149 ms 282628 KB Output is correct
37 Correct 151 ms 282520 KB Output is correct
38 Correct 531 ms 293592 KB Output is correct
39 Correct 854 ms 505512 KB Output is correct
40 Correct 528 ms 296384 KB Output is correct
41 Correct 532 ms 295164 KB Output is correct
42 Correct 450 ms 295744 KB Output is correct
43 Correct 538 ms 296056 KB Output is correct
44 Correct 190 ms 284480 KB Output is correct
45 Correct 938 ms 508028 KB Output is correct
46 Correct 994 ms 507996 KB Output is correct
47 Correct 1000 ms 504668 KB Output is correct
48 Correct 928 ms 504804 KB Output is correct
49 Correct 844 ms 508888 KB Output is correct
50 Correct 864 ms 508752 KB Output is correct
51 Correct 990 ms 507972 KB Output is correct
52 Correct 1141 ms 507908 KB Output is correct
53 Correct 258 ms 298816 KB Output is correct
54 Correct 1298 ms 508928 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 282060 KB Output is correct
2 Correct 126 ms 282148 KB Output is correct
3 Correct 135 ms 282088 KB Output is correct
4 Correct 130 ms 282076 KB Output is correct
5 Correct 176 ms 282200 KB Output is correct
6 Correct 131 ms 282620 KB Output is correct
7 Correct 134 ms 282572 KB Output is correct
8 Correct 131 ms 282208 KB Output is correct
9 Correct 129 ms 282052 KB Output is correct
10 Correct 139 ms 282316 KB Output is correct
11 Correct 139 ms 282128 KB Output is correct
12 Correct 136 ms 282624 KB Output is correct
13 Correct 256 ms 282316 KB Output is correct
14 Correct 381 ms 282404 KB Output is correct
15 Correct 311 ms 282424 KB Output is correct
16 Correct 987 ms 508836 KB Output is correct
17 Correct 1061 ms 517232 KB Output is correct
18 Correct 1250 ms 525328 KB Output is correct
19 Correct 1060 ms 511800 KB Output is correct
20 Correct 1084 ms 511392 KB Output is correct
21 Correct 1088 ms 511556 KB Output is correct
22 Correct 960 ms 517404 KB Output is correct
23 Correct 938 ms 517444 KB Output is correct
24 Correct 1280 ms 517324 KB Output is correct
25 Correct 1273 ms 517224 KB Output is correct
26 Correct 1312 ms 517132 KB Output is correct
27 Correct 1540 ms 520964 KB Output is correct
28 Correct 877 ms 520764 KB Output is correct
29 Correct 890 ms 520848 KB Output is correct
30 Correct 1360 ms 514552 KB Output is correct
31 Correct 894 ms 514548 KB Output is correct
32 Correct 1232 ms 515776 KB Output is correct
33 Correct 868 ms 515752 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 282060 KB Output is correct
2 Correct 135 ms 282216 KB Output is correct
3 Correct 132 ms 282044 KB Output is correct
4 Correct 208 ms 282372 KB Output is correct
5 Correct 321 ms 282600 KB Output is correct
6 Correct 137 ms 282608 KB Output is correct
7 Correct 140 ms 282572 KB Output is correct
8 Correct 136 ms 282628 KB Output is correct
9 Correct 502 ms 293688 KB Output is correct
10 Correct 839 ms 505336 KB Output is correct
11 Correct 171 ms 282264 KB Output is correct
12 Correct 361 ms 283316 KB Output is correct
13 Correct 1045 ms 511588 KB Output is correct
14 Correct 847 ms 511600 KB Output is correct
15 Correct 1134 ms 512988 KB Output is correct
16 Correct 1568 ms 522620 KB Output is correct
17 Correct 946 ms 514216 KB Output is correct
18 Correct 918 ms 515740 KB Output is correct
19 Correct 977 ms 514140 KB Output is correct
20 Correct 865 ms 514132 KB Output is correct
21 Correct 921 ms 514640 KB Output is correct
22 Correct 819 ms 511408 KB Output is correct
23 Correct 131 ms 282052 KB Output is correct
24 Correct 128 ms 282248 KB Output is correct
25 Correct 149 ms 282572 KB Output is correct
26 Correct 137 ms 282564 KB Output is correct
27 Correct 139 ms 282628 KB Output is correct
28 Correct 149 ms 282712 KB Output is correct
29 Correct 135 ms 282540 KB Output is correct
30 Correct 141 ms 282608 KB Output is correct
31 Correct 142 ms 282516 KB Output is correct
32 Correct 144 ms 282572 KB Output is correct
33 Correct 144 ms 282604 KB Output is correct
34 Correct 143 ms 282540 KB Output is correct
35 Correct 137 ms 282588 KB Output is correct
36 Correct 147 ms 282108 KB Output is correct
37 Correct 131 ms 282116 KB Output is correct
38 Correct 141 ms 282584 KB Output is correct
39 Correct 142 ms 282612 KB Output is correct
40 Correct 142 ms 282556 KB Output is correct
41 Correct 133 ms 282104 KB Output is correct
42 Correct 155 ms 282616 KB Output is correct
43 Correct 156 ms 282616 KB Output is correct
44 Correct 135 ms 282660 KB Output is correct
45 Correct 135 ms 282240 KB Output is correct
46 Correct 124 ms 282396 KB Output is correct
47 Correct 146 ms 282648 KB Output is correct
48 Correct 141 ms 282564 KB Output is correct
49 Correct 153 ms 282540 KB Output is correct
50 Correct 130 ms 282188 KB Output is correct
51 Correct 167 ms 282528 KB Output is correct
52 Correct 144 ms 282640 KB Output is correct
53 Correct 143 ms 282780 KB Output is correct
54 Correct 138 ms 282660 KB Output is correct
55 Correct 142 ms 282632 KB Output is correct
56 Correct 139 ms 282548 KB Output is correct
57 Correct 139 ms 282540 KB Output is correct
58 Correct 149 ms 282628 KB Output is correct
59 Correct 151 ms 282520 KB Output is correct
60 Correct 531 ms 293592 KB Output is correct
61 Correct 854 ms 505512 KB Output is correct
62 Correct 528 ms 296384 KB Output is correct
63 Correct 532 ms 295164 KB Output is correct
64 Correct 450 ms 295744 KB Output is correct
65 Correct 538 ms 296056 KB Output is correct
66 Correct 190 ms 284480 KB Output is correct
67 Correct 938 ms 508028 KB Output is correct
68 Correct 994 ms 507996 KB Output is correct
69 Correct 1000 ms 504668 KB Output is correct
70 Correct 928 ms 504804 KB Output is correct
71 Correct 844 ms 508888 KB Output is correct
72 Correct 864 ms 508752 KB Output is correct
73 Correct 990 ms 507972 KB Output is correct
74 Correct 1141 ms 507908 KB Output is correct
75 Correct 258 ms 298816 KB Output is correct
76 Correct 1298 ms 508928 KB Output is correct
77 Correct 140 ms 282060 KB Output is correct
78 Correct 126 ms 282148 KB Output is correct
79 Correct 135 ms 282088 KB Output is correct
80 Correct 130 ms 282076 KB Output is correct
81 Correct 176 ms 282200 KB Output is correct
82 Correct 131 ms 282620 KB Output is correct
83 Correct 134 ms 282572 KB Output is correct
84 Correct 131 ms 282208 KB Output is correct
85 Correct 129 ms 282052 KB Output is correct
86 Correct 139 ms 282316 KB Output is correct
87 Correct 139 ms 282128 KB Output is correct
88 Correct 136 ms 282624 KB Output is correct
89 Correct 256 ms 282316 KB Output is correct
90 Correct 381 ms 282404 KB Output is correct
91 Correct 311 ms 282424 KB Output is correct
92 Correct 987 ms 508836 KB Output is correct
93 Correct 1061 ms 517232 KB Output is correct
94 Correct 1250 ms 525328 KB Output is correct
95 Correct 1060 ms 511800 KB Output is correct
96 Correct 1084 ms 511392 KB Output is correct
97 Correct 1088 ms 511556 KB Output is correct
98 Correct 960 ms 517404 KB Output is correct
99 Correct 938 ms 517444 KB Output is correct
100 Correct 1280 ms 517324 KB Output is correct
101 Correct 1273 ms 517224 KB Output is correct
102 Correct 1312 ms 517132 KB Output is correct
103 Correct 1540 ms 520964 KB Output is correct
104 Correct 877 ms 520764 KB Output is correct
105 Correct 890 ms 520848 KB Output is correct
106 Correct 1360 ms 514552 KB Output is correct
107 Correct 894 ms 514548 KB Output is correct
108 Correct 1232 ms 515776 KB Output is correct
109 Correct 868 ms 515752 KB Output is correct
110 Correct 363 ms 283496 KB Output is correct
111 Correct 314 ms 283104 KB Output is correct
112 Correct 1281 ms 516856 KB Output is correct
113 Correct 1312 ms 508728 KB Output is correct
114 Correct 986 ms 516300 KB Output is correct
115 Correct 718 ms 509280 KB Output is correct
116 Correct 1468 ms 515588 KB Output is correct
117 Correct 1278 ms 526728 KB Output is correct
118 Correct 1266 ms 508900 KB Output is correct
119 Correct 1257 ms 508988 KB Output is correct
120 Correct 226 ms 301520 KB Output is correct
121 Correct 1836 ms 515468 KB Output is correct
122 Correct 1776 ms 515424 KB Output is correct
123 Correct 1504 ms 508640 KB Output is correct
124 Correct 1106 ms 508516 KB Output is correct
125 Correct 1536 ms 509088 KB Output is correct
126 Correct 1809 ms 525216 KB Output is correct
127 Correct 1145 ms 519196 KB Output is correct
128 Correct 989 ms 518952 KB Output is correct
129 Correct 1369 ms 519328 KB Output is correct
130 Correct 1027 ms 519328 KB Output is correct