oj.uz

Submission #951100

# Submission time Handle Problem Language Result Execution time Memory
951100 2024-03-21T06:47:16 Z hotboy2703 Jail (JOI22_jail) C++14
100 / 100
 1862 ms 442144 KB 
#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
ll n,m;
const ll MAXN = 1.2e5;
const ll MAXK = 17;
ll cur_node;
namespace CYC{
    vector <ll> g[MAXN*MAXK*2 + MAXN * 5 + 100];
    void add_edge(ll u,ll v){g[u].push_back(v);}
    bool in[MAXN*MAXK*2 + MAXN * 5 + 100];
    bool in_st[MAXN*MAXK*2 + MAXN * 5 + 100];
    bool detect_cycle;
    void init(){
        for (ll i = 1;i <= cur_node;i++){g[i].clear();in[i] = 0;in_st[i] = 0;}
        detect_cycle = 0;
    }
    ll depth=0;
    ll cnt = 0;
    void dfs(ll u){
//        cout<<u<<' '<<depth<<' '<<cnt<<endl;
//        depth++;
//        cnt++;
        in_st[u] = 1;
        in[u] = 1;
        for (auto v:g[u]){
            if (in_st[v])detect_cycle = 1;
            if (in[v])continue;
            dfs(v);
        }
        in_st[u] = 0;
//        depth--;
    }
    void solve(){
        for (ll i = 1;i <= cur_node;i++)if (!in[i])dfs(i);
    }
}
vector <ll> g[MAXN+100];
ll sp[MAXK][MAXN+100];
ll node[MAXK][MAXN+100];
ll path[MAXN+100][2];
ll depth[MAXN+100];
ll lca(ll u,ll v){
    if (depth[u] > depth[v])swap(u,v);
    for (ll j = MAXK-1;j>=0;j--){
        if (depth[sp[j][v]]>=depth[u])v=sp[j][v];
    }
    if (v==u)return u;
    for (ll j = MAXK-1;j>=0;j--){
        if (sp[j][v] != sp[j][u]){
            v=sp[j][v];
            u=sp[j][u];
        }
    }
    return sp[0][u];
}
void dfs(ll u,ll p){
    sp[0][u] = p;
    depth[u] = depth[p]+1;
    for (auto v:g[u]){
        if (v==p)continue;
        dfs(v,u);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
//    freopen("code1.inp","r",stdin);
    ll t;
    cin>>t;
    while (t--){
        cin>>n;
        for (ll i = 1;i <= n; i++){
            g[i].clear();

        }
        for (ll i = 1;i < n;i ++){
            ll u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        cin>>m;
        for (ll i = 1;i <= m;i ++){
            ll s,t;
            cin>>s>>t;
            path[i][0] = s,path[i][1] = t;
        }
        dfs(1,1);
        for (ll j = 1;j < MAXK;j ++){
            for (ll i = 1;i <= n;i ++){
                sp[j][i] = sp[j-1][sp[j-1][i]];
//                cout<<sp[j][i]<<' ';
            }
//            cout<<'\n';
        }
//        exit(0);
        vector <pll> edge[2];
        cur_node = m + 1;
        for (ll k = 0;k < 2;k ++){
            for (ll i = 1;i <= n;i ++){
                node[0][i] = cur_node++;
            }
            for (ll j = 1;j < MAXK;j ++){
                for (ll i = 1;i <= n;i ++){
                    node[j][i] = cur_node++;
                    edge[k].push_back(MP(node[j][i],node[j-1][i]));
                    edge[k].push_back(MP(node[j][i],node[j-1][sp[j-1][i]]));
                }
            }
            for (ll i = 1;i <= m;i ++){
                edge[k].push_back(MP(node[0][path[i][k]],i));
            }
            for (ll i = 1;i <= m;i ++){
                ll u = path[i][0],v = path[i][1];
                ll x = lca(u,v);
//                cout<<u<<' '<<v<<' '<<x<<'\n';
                bool no_lca = 0;
                if (k==0){
                    if (u != x)u = sp[0][u];
                    else no_lca = 1;
                }
                if (k==1){
                    if (v != x)v = sp[0][v];
                    else no_lca = 1;
                }
                for (ll j = MAXK-1;j>=0;j--){
                    if (depth[u]-MASK(j) >= depth[x]){
//                        cout<<"U "<<i<<' '<<j<<'\n';
                        edge[k].push_back(MP(i,node[j][u]));
                        u = sp[j][u];
                    }
                    if (depth[v]-MASK(j) >= depth[x]){
//                        cout<<"V "<<i<<' '<<j<<'\n';
                        edge[k].push_back(MP(i,node[j][v]));
                        v = sp[j][v];
                    }
                }
                if (!no_lca)edge[k].push_back(MP(i,node[0][x]));
            }
        }
        CYC::init();
        for (ll j = 0;j < 2;j ++){
            for (auto x:edge[j]){
                if (j)swap(x.fi,x.se);
                CYC::add_edge(x.fi,x.se);
            }
        }
//        exit(0);
//        cout<<cur_node<<endl;
//        exit(0);
        CYC::solve();
        cout<<(CYC::detect_cycle?"No":"Yes")<<'\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 133212 KB Output is correct
2 Correct 32 ms 133204 KB Output is correct
3 Correct 29 ms 133208 KB Output is correct
4 Correct 84 ms 133420 KB Output is correct
5 Correct 152 ms 133468 KB Output is correct
6 Correct 34 ms 135720 KB Output is correct
7 Correct 35 ms 135760 KB Output is correct
8 Correct 44 ms 136072 KB Output is correct
9 Correct 236 ms 149064 KB Output is correct
10 Correct 601 ms 329440 KB Output is correct
11 Correct 53 ms 133464 KB Output is correct
12 Correct 179 ms 134328 KB Output is correct
13 Correct 643 ms 337100 KB Output is correct
14 Correct 591 ms 349428 KB Output is correct
15 Correct 1260 ms 373996 KB Output is correct
16 Correct 1696 ms 438696 KB Output is correct
17 Correct 634 ms 347472 KB Output is correct
18 Correct 552 ms 346200 KB Output is correct
19 Correct 630 ms 343208 KB Output is correct
20 Correct 672 ms 345696 KB Output is correct
21 Correct 959 ms 387756 KB Output is correct
22 Correct 623 ms 335644 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 133424 KB Output is correct
2 Correct 29 ms 133224 KB Output is correct
3 Correct 35 ms 135772 KB Output is correct
4 Correct 35 ms 135772 KB Output is correct
5 Correct 35 ms 135764 KB Output is correct
6 Correct 35 ms 135772 KB Output is correct
7 Correct 34 ms 135764 KB Output is correct
8 Correct 34 ms 135760 KB Output is correct
9 Correct 35 ms 135772 KB Output is correct
10 Correct 35 ms 135764 KB Output is correct
11 Correct 34 ms 135976 KB Output is correct
12 Correct 32 ms 135772 KB Output is correct
13 Correct 32 ms 135720 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 133424 KB Output is correct
2 Correct 29 ms 133224 KB Output is correct
3 Correct 35 ms 135772 KB Output is correct
4 Correct 35 ms 135772 KB Output is correct
5 Correct 35 ms 135764 KB Output is correct
6 Correct 35 ms 135772 KB Output is correct
7 Correct 34 ms 135764 KB Output is correct
8 Correct 34 ms 135760 KB Output is correct
9 Correct 35 ms 135772 KB Output is correct
10 Correct 35 ms 135764 KB Output is correct
11 Correct 34 ms 135976 KB Output is correct
12 Correct 32 ms 135772 KB Output is correct
13 Correct 32 ms 135720 KB Output is correct
14 Correct 28 ms 133328 KB Output is correct
15 Correct 29 ms 133396 KB Output is correct
16 Correct 35 ms 135768 KB Output is correct
17 Correct 34 ms 135768 KB Output is correct
18 Correct 37 ms 135772 KB Output is correct
19 Correct 29 ms 133244 KB Output is correct
20 Correct 35 ms 135760 KB Output is correct
21 Correct 36 ms 135904 KB Output is correct
22 Correct 36 ms 135772 KB Output is correct
23 Correct 29 ms 133212 KB Output is correct
24 Correct 30 ms 133724 KB Output is correct
25 Correct 35 ms 135768 KB Output is correct
26 Correct 32 ms 135768 KB Output is correct
27 Correct 34 ms 135772 KB Output is correct
28 Correct 32 ms 133456 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 133424 KB Output is correct
2 Correct 29 ms 133224 KB Output is correct
3 Correct 35 ms 135772 KB Output is correct
4 Correct 35 ms 135772 KB Output is correct
5 Correct 35 ms 135764 KB Output is correct
6 Correct 35 ms 135772 KB Output is correct
7 Correct 34 ms 135764 KB Output is correct
8 Correct 34 ms 135760 KB Output is correct
9 Correct 35 ms 135772 KB Output is correct
10 Correct 35 ms 135764 KB Output is correct
11 Correct 34 ms 135976 KB Output is correct
12 Correct 32 ms 135772 KB Output is correct
13 Correct 32 ms 135720 KB Output is correct
14 Correct 28 ms 133328 KB Output is correct
15 Correct 29 ms 133396 KB Output is correct
16 Correct 35 ms 135768 KB Output is correct
17 Correct 34 ms 135768 KB Output is correct
18 Correct 37 ms 135772 KB Output is correct
19 Correct 29 ms 133244 KB Output is correct
20 Correct 35 ms 135760 KB Output is correct
21 Correct 36 ms 135904 KB Output is correct
22 Correct 36 ms 135772 KB Output is correct
23 Correct 29 ms 133212 KB Output is correct
24 Correct 30 ms 133724 KB Output is correct
25 Correct 35 ms 135768 KB Output is correct
26 Correct 32 ms 135768 KB Output is correct
27 Correct 34 ms 135772 KB Output is correct
28 Correct 32 ms 133456 KB Output is correct
29 Correct 37 ms 136088 KB Output is correct
30 Correct 36 ms 136228 KB Output is correct
31 Correct 41 ms 136136 KB Output is correct
32 Correct 37 ms 136060 KB Output is correct
33 Correct 35 ms 135768 KB Output is correct
34 Correct 36 ms 133720 KB Output is correct
35 Correct 36 ms 133872 KB Output is correct
36 Correct 34 ms 133752 KB Output is correct
37 Correct 32 ms 133724 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 133424 KB Output is correct
2 Correct 29 ms 133224 KB Output is correct
3 Correct 35 ms 135772 KB Output is correct
4 Correct 35 ms 135772 KB Output is correct
5 Correct 35 ms 135764 KB Output is correct
6 Correct 35 ms 135772 KB Output is correct
7 Correct 34 ms 135764 KB Output is correct
8 Correct 34 ms 135760 KB Output is correct
9 Correct 35 ms 135772 KB Output is correct
10 Correct 35 ms 135764 KB Output is correct
11 Correct 34 ms 135976 KB Output is correct
12 Correct 32 ms 135772 KB Output is correct
13 Correct 32 ms 135720 KB Output is correct
14 Correct 28 ms 133328 KB Output is correct
15 Correct 29 ms 133396 KB Output is correct
16 Correct 35 ms 135768 KB Output is correct
17 Correct 34 ms 135768 KB Output is correct
18 Correct 37 ms 135772 KB Output is correct
19 Correct 29 ms 133244 KB Output is correct
20 Correct 35 ms 135760 KB Output is correct
21 Correct 36 ms 135904 KB Output is correct
22 Correct 36 ms 135772 KB Output is correct
23 Correct 29 ms 133212 KB Output is correct
24 Correct 30 ms 133724 KB Output is correct
25 Correct 35 ms 135768 KB Output is correct
26 Correct 32 ms 135768 KB Output is correct
27 Correct 34 ms 135772 KB Output is correct
28 Correct 32 ms 133456 KB Output is correct
29 Correct 37 ms 136088 KB Output is correct
30 Correct 36 ms 136228 KB Output is correct
31 Correct 41 ms 136136 KB Output is correct
32 Correct 37 ms 136060 KB Output is correct
33 Correct 35 ms 135768 KB Output is correct
34 Correct 36 ms 133720 KB Output is correct
35 Correct 36 ms 133872 KB Output is correct
36 Correct 34 ms 133752 KB Output is correct
37 Correct 32 ms 133724 KB Output is correct
38 Correct 238 ms 149324 KB Output is correct
39 Correct 563 ms 330640 KB Output is correct
40 Correct 295 ms 150032 KB Output is correct
41 Correct 252 ms 147676 KB Output is correct
42 Correct 237 ms 149296 KB Output is correct
43 Correct 244 ms 149140 KB Output is correct
44 Correct 64 ms 138296 KB Output is correct
45 Correct 586 ms 331688 KB Output is correct
46 Correct 556 ms 331768 KB Output is correct
47 Correct 617 ms 328740 KB Output is correct
48 Correct 580 ms 329132 KB Output is correct
49 Correct 501 ms 335612 KB Output is correct
50 Correct 516 ms 333464 KB Output is correct
51 Correct 532 ms 333036 KB Output is correct
52 Correct 560 ms 333472 KB Output is correct
53 Correct 97 ms 152192 KB Output is correct
54 Correct 523 ms 334568 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 133164 KB Output is correct
2 Correct 29 ms 133200 KB Output is correct
3 Correct 28 ms 133212 KB Output is correct
4 Correct 28 ms 133208 KB Output is correct
5 Correct 54 ms 133456 KB Output is correct
6 Correct 36 ms 135768 KB Output is correct
7 Correct 32 ms 135772 KB Output is correct
8 Correct 32 ms 133364 KB Output is correct
9 Correct 29 ms 133196 KB Output is correct
10 Correct 29 ms 133464 KB Output is correct
11 Correct 29 ms 133204 KB Output is correct
12 Correct 36 ms 133892 KB Output is correct
13 Correct 116 ms 133760 KB Output is correct
14 Correct 169 ms 133904 KB Output is correct
15 Correct 138 ms 133724 KB Output is correct
16 Correct 796 ms 334804 KB Output is correct
17 Correct 1177 ms 346680 KB Output is correct
18 Correct 960 ms 375436 KB Output is correct
19 Correct 627 ms 334704 KB Output is correct
20 Correct 652 ms 335868 KB Output is correct
21 Correct 641 ms 334728 KB Output is correct
22 Correct 874 ms 343680 KB Output is correct
23 Correct 745 ms 342252 KB Output is correct
24 Correct 853 ms 342024 KB Output is correct
25 Correct 847 ms 342268 KB Output is correct
26 Correct 858 ms 342048 KB Output is correct
27 Correct 1191 ms 357368 KB Output is correct
28 Correct 1096 ms 358588 KB Output is correct
29 Correct 1026 ms 352412 KB Output is correct
30 Correct 657 ms 347056 KB Output is correct
31 Correct 607 ms 348576 KB Output is correct
32 Correct 861 ms 346496 KB Output is correct
33 Correct 835 ms 349908 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 133212 KB Output is correct
2 Correct 32 ms 133204 KB Output is correct
3 Correct 29 ms 133208 KB Output is correct
4 Correct 84 ms 133420 KB Output is correct
5 Correct 152 ms 133468 KB Output is correct
6 Correct 34 ms 135720 KB Output is correct
7 Correct 35 ms 135760 KB Output is correct
8 Correct 44 ms 136072 KB Output is correct
9 Correct 236 ms 149064 KB Output is correct
10 Correct 601 ms 329440 KB Output is correct
11 Correct 53 ms 133464 KB Output is correct
12 Correct 179 ms 134328 KB Output is correct
13 Correct 643 ms 337100 KB Output is correct
14 Correct 591 ms 349428 KB Output is correct
15 Correct 1260 ms 373996 KB Output is correct
16 Correct 1696 ms 438696 KB Output is correct
17 Correct 634 ms 347472 KB Output is correct
18 Correct 552 ms 346200 KB Output is correct
19 Correct 630 ms 343208 KB Output is correct
20 Correct 672 ms 345696 KB Output is correct
21 Correct 959 ms 387756 KB Output is correct
22 Correct 623 ms 335644 KB Output is correct
23 Correct 29 ms 133424 KB Output is correct
24 Correct 29 ms 133224 KB Output is correct
25 Correct 35 ms 135772 KB Output is correct
26 Correct 35 ms 135772 KB Output is correct
27 Correct 35 ms 135764 KB Output is correct
28 Correct 35 ms 135772 KB Output is correct
29 Correct 34 ms 135764 KB Output is correct
30 Correct 34 ms 135760 KB Output is correct
31 Correct 35 ms 135772 KB Output is correct
32 Correct 35 ms 135764 KB Output is correct
33 Correct 34 ms 135976 KB Output is correct
34 Correct 32 ms 135772 KB Output is correct
35 Correct 32 ms 135720 KB Output is correct
36 Correct 28 ms 133328 KB Output is correct
37 Correct 29 ms 133396 KB Output is correct
38 Correct 35 ms 135768 KB Output is correct
39 Correct 34 ms 135768 KB Output is correct
40 Correct 37 ms 135772 KB Output is correct
41 Correct 29 ms 133244 KB Output is correct
42 Correct 35 ms 135760 KB Output is correct
43 Correct 36 ms 135904 KB Output is correct
44 Correct 36 ms 135772 KB Output is correct
45 Correct 29 ms 133212 KB Output is correct
46 Correct 30 ms 133724 KB Output is correct
47 Correct 35 ms 135768 KB Output is correct
48 Correct 32 ms 135768 KB Output is correct
49 Correct 34 ms 135772 KB Output is correct
50 Correct 32 ms 133456 KB Output is correct
51 Correct 37 ms 136088 KB Output is correct
52 Correct 36 ms 136228 KB Output is correct
53 Correct 41 ms 136136 KB Output is correct
54 Correct 37 ms 136060 KB Output is correct
55 Correct 35 ms 135768 KB Output is correct
56 Correct 36 ms 133720 KB Output is correct
57 Correct 36 ms 133872 KB Output is correct
58 Correct 34 ms 133752 KB Output is correct
59 Correct 32 ms 133724 KB Output is correct
60 Correct 238 ms 149324 KB Output is correct
61 Correct 563 ms 330640 KB Output is correct
62 Correct 295 ms 150032 KB Output is correct
63 Correct 252 ms 147676 KB Output is correct
64 Correct 237 ms 149296 KB Output is correct
65 Correct 244 ms 149140 KB Output is correct
66 Correct 64 ms 138296 KB Output is correct
67 Correct 586 ms 331688 KB Output is correct
68 Correct 556 ms 331768 KB Output is correct
69 Correct 617 ms 328740 KB Output is correct
70 Correct 580 ms 329132 KB Output is correct
71 Correct 501 ms 335612 KB Output is correct
72 Correct 516 ms 333464 KB Output is correct
73 Correct 532 ms 333036 KB Output is correct
74 Correct 560 ms 333472 KB Output is correct
75 Correct 97 ms 152192 KB Output is correct
76 Correct 523 ms 334568 KB Output is correct
77 Correct 29 ms 133164 KB Output is correct
78 Correct 29 ms 133200 KB Output is correct
79 Correct 28 ms 133212 KB Output is correct
80 Correct 28 ms 133208 KB Output is correct
81 Correct 54 ms 133456 KB Output is correct
82 Correct 36 ms 135768 KB Output is correct
83 Correct 32 ms 135772 KB Output is correct
84 Correct 32 ms 133364 KB Output is correct
85 Correct 29 ms 133196 KB Output is correct
86 Correct 29 ms 133464 KB Output is correct
87 Correct 29 ms 133204 KB Output is correct
88 Correct 36 ms 133892 KB Output is correct
89 Correct 116 ms 133760 KB Output is correct
90 Correct 169 ms 133904 KB Output is correct
91 Correct 138 ms 133724 KB Output is correct
92 Correct 796 ms 334804 KB Output is correct
93 Correct 1177 ms 346680 KB Output is correct
94 Correct 960 ms 375436 KB Output is correct
95 Correct 627 ms 334704 KB Output is correct
96 Correct 652 ms 335868 KB Output is correct
97 Correct 641 ms 334728 KB Output is correct
98 Correct 874 ms 343680 KB Output is correct
99 Correct 745 ms 342252 KB Output is correct
100 Correct 853 ms 342024 KB Output is correct
101 Correct 847 ms 342268 KB Output is correct
102 Correct 858 ms 342048 KB Output is correct
103 Correct 1191 ms 357368 KB Output is correct
104 Correct 1096 ms 358588 KB Output is correct
105 Correct 1026 ms 352412 KB Output is correct
106 Correct 657 ms 347056 KB Output is correct
107 Correct 607 ms 348576 KB Output is correct
108 Correct 861 ms 346496 KB Output is correct
109 Correct 835 ms 349908 KB Output is correct
110 Correct 184 ms 136804 KB Output is correct
111 Correct 133 ms 134224 KB Output is correct
112 Correct 1368 ms 379444 KB Output is correct
113 Correct 898 ms 336456 KB Output is correct
114 Correct 934 ms 367380 KB Output is correct
115 Correct 424 ms 334904 KB Output is correct
116 Correct 983 ms 342776 KB Output is correct
117 Correct 1157 ms 384400 KB Output is correct
118 Correct 547 ms 332752 KB Output is correct
119 Correct 538 ms 334096 KB Output is correct
120 Correct 80 ms 154020 KB Output is correct
121 Correct 1040 ms 342792 KB Output is correct
122 Correct 935 ms 343056 KB Output is correct
123 Correct 951 ms 336132 KB Output is correct
124 Correct 1008 ms 336184 KB Output is correct
125 Correct 1004 ms 338084 KB Output is correct
126 Correct 1862 ms 442144 KB Output is correct
127 Correct 1109 ms 392348 KB Output is correct
128 Correct 935 ms 385528 KB Output is correct
129 Correct 889 ms 357660 KB Output is correct
130 Correct 921 ms 387020 KB Output is correct