oj.uz

Submission #1083660

# Submission time Handle Problem Language Result Execution time Memory
1083660 2024-09-03T18:17:45 Z ShaShi Jail (JOI22_jail) C++17
100 / 100
 1586 ms 470412 KB 
#include <bits/stdc++.h>
 
// #define int long long
 
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
 
const int MAXN = (int)2e5 + 23;
const int MOD = 998244353;
const ll INF = (ll)1e9 + 7;
const int LG = 18;


int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, flag2;
pii arr[MAXN]; int par[MAXN], h[MAXN], pow2dad[MAXN][LG], fake_t[MAXN][LG], fake_s[MAXN][LG], ind_s[MAXN], ind_t[MAXN];
vector<int> adj[MAXN], G[MAXN*40];
int seen[MAXN*40];


inline void add_edge(int u, int v) { G[u].pb(v); }
inline int up(int v, int k) { for (int i=LG-1; i>=0; i--) if (k >= (1<<i)) k -= (1<<i), v = pow2dad[v][i]; return v; }
inline int LCA(int u, int v) { if (h[u] < h[v]) swap(u, v); u = up(u, h[u]-h[v]); if (u == v) return u; for (int i=LG-1; i>=0; i--) if (h[u] >= (1<<i) && pow2dad[u][i] != pow2dad[v][i]) u = pow2dad[u][i], v = pow2dad[v][i]; return pow2dad[u][0]; }



void DFS(int v) {
    for (int u:adj[v]) {
        if (u == par[v]) continue;

        par[u] = v; h[u] = h[v]+1; DFS(u);
    }
}


void DFS2(int v) {
    seen[v] = 1;

    for (int u:G[v]) {
        if (seen[u] == 0) DFS2(u);
        else if (seen[u] == 1) tmp = 0;
    }

    seen[v] = 2;
}


inline void up_s(int v, int k, int ind) {
    // cout << "S : " << v << " " << k << " " << ind << endl;

    for (int i=LG-1; i>=0; i--) {
        if ((1<<i) <= k) {
            k -= (1<<i); add_edge(fake_s[v][i], ind); v = pow2dad[v][i];
        }
    }
}


inline void up_t(int v, int k, int ind) {
    // cout << "T : " << v << " " << k << " " << ind << endl;

    for (int i=LG-1; i>=0; i--) {
        if ((1<<i) <= k) {
            k -= (1<<i); add_edge(ind, fake_t[v][i]); v = pow2dad[v][i];
        }
    }
}


void solve() {
    cin >> n;

    for (int i=1; i<n; i++) {
        cin >> u >> v;

        adj[u].pb(v); adj[v].pb(u);
    }

    cin >> m;

    for (int i=1; i<=m; i++) {
        cin >> u >> v;

        ind_s[u] = i; ind_t[v] = i; arr[i] = {u, v};
    }

    DFS(1); flag = n+1;

    for (int i=1; i<=n; i++) {
        pow2dad[i][0] = par[i];

        fake_s[i][0] = flag++; if (ind_s[i]) add_edge(ind_s[i], fake_s[i][0]);
        fake_t[i][0] = flag++; if (ind_t[i]) add_edge(fake_t[i][0], ind_t[i]);
    }

    for (int j=1; j<LG; j++) {
        for (int i=1; i<=n; i++) {
            pow2dad[i][j] = pow2dad[pow2dad[i][j-1]][j-1];

            fake_s[i][j] = flag++; add_edge(fake_s[i][j-1], fake_s[i][j]); add_edge(fake_s[pow2dad[i][j-1]][j-1], fake_s[i][j]);
            fake_t[i][j] = flag++; add_edge(fake_t[i][j], fake_t[i][j-1]); add_edge(fake_t[i][j], fake_t[pow2dad[i][j-1]][j-1]);
        }
    }


    for (int i=1; i<=m; i++) {
        u = arr[i].F; v = arr[i].S;

        int lca = LCA(u, v);

        if (lca == u) {
            up_s(v, h[v]-h[u], i);
            up_t(par[v], h[v]-h[u], i);
        } else if (lca == v) {
            up_s(par[u], h[u]-h[v], i);
            up_t(u, h[u]-h[v], i);
        } else {
            up_s(par[u], h[u]-h[lca], i); up_t(u, h[u]-h[lca]+1, i);
            up_s(v, h[v]-h[lca]+1, i); up_t(par[v], h[v]-h[lca], i);
        }
    }


    tmp = 1;
    
    for (int i=1; i<=n; i++) {
        if (seen[i]) continue;

        DFS2(i);

        if (!tmp) break;
    }

    cout << (tmp? "Yes\n" : "No\n");

    fill_n(seen, flag+7, 0);  fill_n(ind_s, n+7, 0); fill_n(ind_t, n+7, 0);  fill_n(par, n+7, 0); 
    for (int i=0; i<=n+7; i++) adj[i].clear(); for (int i=0; i<=flag+7; i++) G[i].clear(); flag = tmp = 0;
}


int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> t;

    while (t--) solve();

    return 0;
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:153:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  153 |     for (int i=0; i<=n+7; i++) adj[i].clear(); for (int i=0; i<=flag+7; i++) G[i].clear(); flag = tmp = 0;
      |     ^~~
jail.cpp:153:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  153 |     for (int i=0; i<=n+7; i++) adj[i].clear(); for (int i=0; i<=flag+7; i++) G[i].clear(); flag = tmp = 0;
      |                                                ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 192852 KB Output is correct
2 Correct 78 ms 192972 KB Output is correct
3 Correct 76 ms 192848 KB Output is correct
4 Correct 102 ms 193364 KB Output is correct
5 Correct 122 ms 193616 KB Output is correct
6 Correct 83 ms 193360 KB Output is correct
7 Correct 79 ms 193500 KB Output is correct
8 Correct 81 ms 193316 KB Output is correct
9 Correct 193 ms 203344 KB Output is correct
10 Correct 475 ms 378312 KB Output is correct
11 Correct 94 ms 193104 KB Output is correct
12 Correct 141 ms 194032 KB Output is correct
13 Correct 720 ms 384208 KB Output is correct
14 Correct 634 ms 384224 KB Output is correct
15 Correct 1133 ms 413384 KB Output is correct
16 Correct 1586 ms 470412 KB Output is correct
17 Correct 521 ms 384380 KB Output is correct
18 Correct 518 ms 388408 KB Output is correct
19 Correct 497 ms 384416 KB Output is correct
20 Correct 443 ms 384532 KB Output is correct
21 Correct 947 ms 417992 KB Output is correct
22 Correct 573 ms 383436 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 192852 KB Output is correct
2 Correct 76 ms 192852 KB Output is correct
3 Correct 75 ms 193344 KB Output is correct
4 Correct 83 ms 193360 KB Output is correct
5 Correct 87 ms 193364 KB Output is correct
6 Correct 84 ms 193352 KB Output is correct
7 Correct 84 ms 193360 KB Output is correct
8 Correct 89 ms 193408 KB Output is correct
9 Correct 88 ms 193476 KB Output is correct
10 Correct 85 ms 193364 KB Output is correct
11 Correct 81 ms 193452 KB Output is correct
12 Correct 82 ms 193364 KB Output is correct
13 Correct 78 ms 193352 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 192852 KB Output is correct
2 Correct 76 ms 192852 KB Output is correct
3 Correct 75 ms 193344 KB Output is correct
4 Correct 83 ms 193360 KB Output is correct
5 Correct 87 ms 193364 KB Output is correct
6 Correct 84 ms 193352 KB Output is correct
7 Correct 84 ms 193360 KB Output is correct
8 Correct 89 ms 193408 KB Output is correct
9 Correct 88 ms 193476 KB Output is correct
10 Correct 85 ms 193364 KB Output is correct
11 Correct 81 ms 193452 KB Output is correct
12 Correct 82 ms 193364 KB Output is correct
13 Correct 78 ms 193352 KB Output is correct
14 Correct 82 ms 192848 KB Output is correct
15 Correct 80 ms 193008 KB Output is correct
16 Correct 83 ms 193364 KB Output is correct
17 Correct 84 ms 193372 KB Output is correct
18 Correct 75 ms 193360 KB Output is correct
19 Correct 84 ms 193104 KB Output is correct
20 Correct 85 ms 193364 KB Output is correct
21 Correct 82 ms 193364 KB Output is correct
22 Correct 86 ms 193360 KB Output is correct
23 Correct 79 ms 193104 KB Output is correct
24 Correct 81 ms 193168 KB Output is correct
25 Correct 84 ms 193408 KB Output is correct
26 Correct 80 ms 193312 KB Output is correct
27 Correct 83 ms 193360 KB Output is correct
28 Correct 83 ms 193108 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 192852 KB Output is correct
2 Correct 76 ms 192852 KB Output is correct
3 Correct 75 ms 193344 KB Output is correct
4 Correct 83 ms 193360 KB Output is correct
5 Correct 87 ms 193364 KB Output is correct
6 Correct 84 ms 193352 KB Output is correct
7 Correct 84 ms 193360 KB Output is correct
8 Correct 89 ms 193408 KB Output is correct
9 Correct 88 ms 193476 KB Output is correct
10 Correct 85 ms 193364 KB Output is correct
11 Correct 81 ms 193452 KB Output is correct
12 Correct 82 ms 193364 KB Output is correct
13 Correct 78 ms 193352 KB Output is correct
14 Correct 82 ms 192848 KB Output is correct
15 Correct 80 ms 193008 KB Output is correct
16 Correct 83 ms 193364 KB Output is correct
17 Correct 84 ms 193372 KB Output is correct
18 Correct 75 ms 193360 KB Output is correct
19 Correct 84 ms 193104 KB Output is correct
20 Correct 85 ms 193364 KB Output is correct
21 Correct 82 ms 193364 KB Output is correct
22 Correct 86 ms 193360 KB Output is correct
23 Correct 79 ms 193104 KB Output is correct
24 Correct 81 ms 193168 KB Output is correct
25 Correct 84 ms 193408 KB Output is correct
26 Correct 80 ms 193312 KB Output is correct
27 Correct 83 ms 193360 KB Output is correct
28 Correct 83 ms 193108 KB Output is correct
29 Correct 94 ms 193472 KB Output is correct
30 Correct 81 ms 193364 KB Output is correct
31 Correct 84 ms 193568 KB Output is correct
32 Correct 84 ms 193552 KB Output is correct
33 Correct 83 ms 193360 KB Output is correct
34 Correct 85 ms 193364 KB Output is correct
35 Correct 76 ms 193360 KB Output is correct
36 Correct 83 ms 193520 KB Output is correct
37 Correct 82 ms 193324 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 192852 KB Output is correct
2 Correct 76 ms 192852 KB Output is correct
3 Correct 75 ms 193344 KB Output is correct
4 Correct 83 ms 193360 KB Output is correct
5 Correct 87 ms 193364 KB Output is correct
6 Correct 84 ms 193352 KB Output is correct
7 Correct 84 ms 193360 KB Output is correct
8 Correct 89 ms 193408 KB Output is correct
9 Correct 88 ms 193476 KB Output is correct
10 Correct 85 ms 193364 KB Output is correct
11 Correct 81 ms 193452 KB Output is correct
12 Correct 82 ms 193364 KB Output is correct
13 Correct 78 ms 193352 KB Output is correct
14 Correct 82 ms 192848 KB Output is correct
15 Correct 80 ms 193008 KB Output is correct
16 Correct 83 ms 193364 KB Output is correct
17 Correct 84 ms 193372 KB Output is correct
18 Correct 75 ms 193360 KB Output is correct
19 Correct 84 ms 193104 KB Output is correct
20 Correct 85 ms 193364 KB Output is correct
21 Correct 82 ms 193364 KB Output is correct
22 Correct 86 ms 193360 KB Output is correct
23 Correct 79 ms 193104 KB Output is correct
24 Correct 81 ms 193168 KB Output is correct
25 Correct 84 ms 193408 KB Output is correct
26 Correct 80 ms 193312 KB Output is correct
27 Correct 83 ms 193360 KB Output is correct
28 Correct 83 ms 193108 KB Output is correct
29 Correct 94 ms 193472 KB Output is correct
30 Correct 81 ms 193364 KB Output is correct
31 Correct 84 ms 193568 KB Output is correct
32 Correct 84 ms 193552 KB Output is correct
33 Correct 83 ms 193360 KB Output is correct
34 Correct 85 ms 193364 KB Output is correct
35 Correct 76 ms 193360 KB Output is correct
36 Correct 83 ms 193520 KB Output is correct
37 Correct 82 ms 193324 KB Output is correct
38 Correct 194 ms 203604 KB Output is correct
39 Correct 504 ms 378572 KB Output is correct
40 Correct 174 ms 205000 KB Output is correct
41 Correct 149 ms 203764 KB Output is correct
42 Correct 147 ms 204492 KB Output is correct
43 Correct 164 ms 204860 KB Output is correct
44 Correct 94 ms 194896 KB Output is correct
45 Correct 416 ms 377928 KB Output is correct
46 Correct 439 ms 377768 KB Output is correct
47 Correct 483 ms 375488 KB Output is correct
48 Correct 470 ms 375496 KB Output is correct
49 Correct 418 ms 378548 KB Output is correct
50 Correct 502 ms 378808 KB Output is correct
51 Correct 489 ms 377980 KB Output is correct
52 Correct 471 ms 378044 KB Output is correct
53 Correct 117 ms 206816 KB Output is correct
54 Correct 466 ms 378728 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 193004 KB Output is correct
2 Correct 80 ms 192848 KB Output is correct
3 Correct 79 ms 192944 KB Output is correct
4 Correct 80 ms 192852 KB Output is correct
5 Correct 92 ms 193104 KB Output is correct
6 Correct 81 ms 193364 KB Output is correct
7 Correct 77 ms 193360 KB Output is correct
8 Correct 82 ms 193104 KB Output is correct
9 Correct 85 ms 193108 KB Output is correct
10 Correct 78 ms 193108 KB Output is correct
11 Correct 80 ms 192944 KB Output is correct
12 Correct 85 ms 193512 KB Output is correct
13 Correct 116 ms 193616 KB Output is correct
14 Correct 126 ms 194132 KB Output is correct
15 Correct 117 ms 193872 KB Output is correct
16 Correct 432 ms 379772 KB Output is correct
17 Correct 773 ms 391468 KB Output is correct
18 Correct 944 ms 417540 KB Output is correct
19 Correct 490 ms 381100 KB Output is correct
20 Correct 436 ms 381100 KB Output is correct
21 Correct 534 ms 381104 KB Output is correct
22 Correct 649 ms 387248 KB Output is correct
23 Correct 622 ms 385840 KB Output is correct
24 Correct 634 ms 385712 KB Output is correct
25 Correct 633 ms 385728 KB Output is correct
26 Correct 638 ms 385644 KB Output is correct
27 Correct 624 ms 393640 KB Output is correct
28 Correct 688 ms 406132 KB Output is correct
29 Correct 546 ms 397480 KB Output is correct
30 Correct 544 ms 390320 KB Output is correct
31 Correct 544 ms 391848 KB Output is correct
32 Correct 588 ms 388620 KB Output is correct
33 Correct 598 ms 392796 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 192852 KB Output is correct
2 Correct 78 ms 192972 KB Output is correct
3 Correct 76 ms 192848 KB Output is correct
4 Correct 102 ms 193364 KB Output is correct
5 Correct 122 ms 193616 KB Output is correct
6 Correct 83 ms 193360 KB Output is correct
7 Correct 79 ms 193500 KB Output is correct
8 Correct 81 ms 193316 KB Output is correct
9 Correct 193 ms 203344 KB Output is correct
10 Correct 475 ms 378312 KB Output is correct
11 Correct 94 ms 193104 KB Output is correct
12 Correct 141 ms 194032 KB Output is correct
13 Correct 720 ms 384208 KB Output is correct
14 Correct 634 ms 384224 KB Output is correct
15 Correct 1133 ms 413384 KB Output is correct
16 Correct 1586 ms 470412 KB Output is correct
17 Correct 521 ms 384380 KB Output is correct
18 Correct 518 ms 388408 KB Output is correct
19 Correct 497 ms 384416 KB Output is correct
20 Correct 443 ms 384532 KB Output is correct
21 Correct 947 ms 417992 KB Output is correct
22 Correct 573 ms 383436 KB Output is correct
23 Correct 81 ms 192852 KB Output is correct
24 Correct 76 ms 192852 KB Output is correct
25 Correct 75 ms 193344 KB Output is correct
26 Correct 83 ms 193360 KB Output is correct
27 Correct 87 ms 193364 KB Output is correct
28 Correct 84 ms 193352 KB Output is correct
29 Correct 84 ms 193360 KB Output is correct
30 Correct 89 ms 193408 KB Output is correct
31 Correct 88 ms 193476 KB Output is correct
32 Correct 85 ms 193364 KB Output is correct
33 Correct 81 ms 193452 KB Output is correct
34 Correct 82 ms 193364 KB Output is correct
35 Correct 78 ms 193352 KB Output is correct
36 Correct 82 ms 192848 KB Output is correct
37 Correct 80 ms 193008 KB Output is correct
38 Correct 83 ms 193364 KB Output is correct
39 Correct 84 ms 193372 KB Output is correct
40 Correct 75 ms 193360 KB Output is correct
41 Correct 84 ms 193104 KB Output is correct
42 Correct 85 ms 193364 KB Output is correct
43 Correct 82 ms 193364 KB Output is correct
44 Correct 86 ms 193360 KB Output is correct
45 Correct 79 ms 193104 KB Output is correct
46 Correct 81 ms 193168 KB Output is correct
47 Correct 84 ms 193408 KB Output is correct
48 Correct 80 ms 193312 KB Output is correct
49 Correct 83 ms 193360 KB Output is correct
50 Correct 83 ms 193108 KB Output is correct
51 Correct 94 ms 193472 KB Output is correct
52 Correct 81 ms 193364 KB Output is correct
53 Correct 84 ms 193568 KB Output is correct
54 Correct 84 ms 193552 KB Output is correct
55 Correct 83 ms 193360 KB Output is correct
56 Correct 85 ms 193364 KB Output is correct
57 Correct 76 ms 193360 KB Output is correct
58 Correct 83 ms 193520 KB Output is correct
59 Correct 82 ms 193324 KB Output is correct
60 Correct 194 ms 203604 KB Output is correct
61 Correct 504 ms 378572 KB Output is correct
62 Correct 174 ms 205000 KB Output is correct
63 Correct 149 ms 203764 KB Output is correct
64 Correct 147 ms 204492 KB Output is correct
65 Correct 164 ms 204860 KB Output is correct
66 Correct 94 ms 194896 KB Output is correct
67 Correct 416 ms 377928 KB Output is correct
68 Correct 439 ms 377768 KB Output is correct
69 Correct 483 ms 375488 KB Output is correct
70 Correct 470 ms 375496 KB Output is correct
71 Correct 418 ms 378548 KB Output is correct
72 Correct 502 ms 378808 KB Output is correct
73 Correct 489 ms 377980 KB Output is correct
74 Correct 471 ms 378044 KB Output is correct
75 Correct 117 ms 206816 KB Output is correct
76 Correct 466 ms 378728 KB Output is correct
77 Correct 77 ms 193004 KB Output is correct
78 Correct 80 ms 192848 KB Output is correct
79 Correct 79 ms 192944 KB Output is correct
80 Correct 80 ms 192852 KB Output is correct
81 Correct 92 ms 193104 KB Output is correct
82 Correct 81 ms 193364 KB Output is correct
83 Correct 77 ms 193360 KB Output is correct
84 Correct 82 ms 193104 KB Output is correct
85 Correct 85 ms 193108 KB Output is correct
86 Correct 78 ms 193108 KB Output is correct
87 Correct 80 ms 192944 KB Output is correct
88 Correct 85 ms 193512 KB Output is correct
89 Correct 116 ms 193616 KB Output is correct
90 Correct 126 ms 194132 KB Output is correct
91 Correct 117 ms 193872 KB Output is correct
92 Correct 432 ms 379772 KB Output is correct
93 Correct 773 ms 391468 KB Output is correct
94 Correct 944 ms 417540 KB Output is correct
95 Correct 490 ms 381100 KB Output is correct
96 Correct 436 ms 381100 KB Output is correct
97 Correct 534 ms 381104 KB Output is correct
98 Correct 649 ms 387248 KB Output is correct
99 Correct 622 ms 385840 KB Output is correct
100 Correct 634 ms 385712 KB Output is correct
101 Correct 633 ms 385728 KB Output is correct
102 Correct 638 ms 385644 KB Output is correct
103 Correct 624 ms 393640 KB Output is correct
104 Correct 688 ms 406132 KB Output is correct
105 Correct 546 ms 397480 KB Output is correct
106 Correct 544 ms 390320 KB Output is correct
107 Correct 544 ms 391848 KB Output is correct
108 Correct 588 ms 388620 KB Output is correct
109 Correct 598 ms 392796 KB Output is correct
110 Correct 127 ms 194412 KB Output is correct
111 Correct 111 ms 193872 KB Output is correct
112 Correct 1210 ms 421316 KB Output is correct
113 Correct 691 ms 380104 KB Output is correct
114 Correct 855 ms 414376 KB Output is correct
115 Correct 339 ms 379056 KB Output is correct
116 Correct 612 ms 384424 KB Output is correct
117 Correct 1067 ms 424132 KB Output is correct
118 Correct 463 ms 378800 KB Output is correct
119 Correct 451 ms 378800 KB Output is correct
120 Correct 117 ms 209100 KB Output is correct
121 Correct 777 ms 385452 KB Output is correct
122 Correct 756 ms 385540 KB Output is correct
123 Correct 764 ms 380540 KB Output is correct
124 Correct 873 ms 380584 KB Output is correct
125 Correct 712 ms 381048 KB Output is correct
126 Correct 1559 ms 467448 KB Output is correct
127 Correct 1058 ms 423712 KB Output is correct
128 Correct 969 ms 425140 KB Output is correct
129 Correct 791 ms 399444 KB Output is correct
130 Correct 877 ms 419776 KB Output is correct