oj.uz

Submission #1083651

# Submission time Handle Problem Language Result Execution time Memory
1083651 2024-09-03T18:07:26 Z ShaShi Jail (JOI22_jail) C++17
49 / 100
 928 ms 988336 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 + 7;
const int MOD = 998244353;
const ll INF = (ll)1e9 + 7;
const int LG = 20;


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*LG*3];
int seen[MAXN*LG*3];


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, flag+7, 0); fill_n(ind_t, flag+7, 0);  fill_n(par, flag+7, 0); 
    for (int i=1; i<=flag+7; i++) adj[i].clear(), G[i].clear();
}


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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 286804 KB Output is correct
2 Correct 119 ms 286804 KB Output is correct
3 Correct 107 ms 286800 KB Output is correct
4 Correct 140 ms 291796 KB Output is correct
5 Correct 174 ms 296148 KB Output is correct
6 Correct 125 ms 287824 KB Output is correct
7 Correct 118 ms 287896 KB Output is correct
8 Correct 115 ms 287956 KB Output is correct
9 Correct 254 ms 304572 KB Output is correct
10 Runtime error 889 ms 987332 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 286804 KB Output is correct
2 Correct 110 ms 286988 KB Output is correct
3 Correct 152 ms 287844 KB Output is correct
4 Correct 142 ms 288064 KB Output is correct
5 Correct 108 ms 288104 KB Output is correct
6 Correct 118 ms 287984 KB Output is correct
7 Correct 113 ms 287988 KB Output is correct
8 Correct 118 ms 288232 KB Output is correct
9 Correct 149 ms 287988 KB Output is correct
10 Correct 118 ms 287988 KB Output is correct
11 Correct 117 ms 287840 KB Output is correct
12 Correct 174 ms 287996 KB Output is correct
13 Correct 115 ms 287828 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 286804 KB Output is correct
2 Correct 110 ms 286988 KB Output is correct
3 Correct 152 ms 287844 KB Output is correct
4 Correct 142 ms 288064 KB Output is correct
5 Correct 108 ms 288104 KB Output is correct
6 Correct 118 ms 287984 KB Output is correct
7 Correct 113 ms 287988 KB Output is correct
8 Correct 118 ms 288232 KB Output is correct
9 Correct 149 ms 287988 KB Output is correct
10 Correct 118 ms 287988 KB Output is correct
11 Correct 117 ms 287840 KB Output is correct
12 Correct 174 ms 287996 KB Output is correct
13 Correct 115 ms 287828 KB Output is correct
14 Correct 107 ms 286980 KB Output is correct
15 Correct 121 ms 286804 KB Output is correct
16 Correct 119 ms 287900 KB Output is correct
17 Correct 136 ms 287984 KB Output is correct
18 Correct 125 ms 287992 KB Output is correct
19 Correct 121 ms 287056 KB Output is correct
20 Correct 131 ms 287988 KB Output is correct
21 Correct 119 ms 287824 KB Output is correct
22 Correct 115 ms 287988 KB Output is correct
23 Correct 132 ms 286976 KB Output is correct
24 Correct 114 ms 287140 KB Output is correct
25 Correct 121 ms 288160 KB Output is correct
26 Correct 118 ms 287420 KB Output is correct
27 Correct 119 ms 287988 KB Output is correct
28 Correct 154 ms 287060 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 286804 KB Output is correct
2 Correct 110 ms 286988 KB Output is correct
3 Correct 152 ms 287844 KB Output is correct
4 Correct 142 ms 288064 KB Output is correct
5 Correct 108 ms 288104 KB Output is correct
6 Correct 118 ms 287984 KB Output is correct
7 Correct 113 ms 287988 KB Output is correct
8 Correct 118 ms 288232 KB Output is correct
9 Correct 149 ms 287988 KB Output is correct
10 Correct 118 ms 287988 KB Output is correct
11 Correct 117 ms 287840 KB Output is correct
12 Correct 174 ms 287996 KB Output is correct
13 Correct 115 ms 287828 KB Output is correct
14 Correct 107 ms 286980 KB Output is correct
15 Correct 121 ms 286804 KB Output is correct
16 Correct 119 ms 287900 KB Output is correct
17 Correct 136 ms 287984 KB Output is correct
18 Correct 125 ms 287992 KB Output is correct
19 Correct 121 ms 287056 KB Output is correct
20 Correct 131 ms 287988 KB Output is correct
21 Correct 119 ms 287824 KB Output is correct
22 Correct 115 ms 287988 KB Output is correct
23 Correct 132 ms 286976 KB Output is correct
24 Correct 114 ms 287140 KB Output is correct
25 Correct 121 ms 288160 KB Output is correct
26 Correct 118 ms 287420 KB Output is correct
27 Correct 119 ms 287988 KB Output is correct
28 Correct 154 ms 287060 KB Output is correct
29 Correct 122 ms 287952 KB Output is correct
30 Correct 122 ms 288180 KB Output is correct
31 Correct 128 ms 288204 KB Output is correct
32 Correct 121 ms 288136 KB Output is correct
33 Correct 123 ms 288248 KB Output is correct
34 Correct 122 ms 287776 KB Output is correct
35 Correct 122 ms 287748 KB Output is correct
36 Correct 118 ms 287828 KB Output is correct
37 Correct 119 ms 287824 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 286804 KB Output is correct
2 Correct 110 ms 286988 KB Output is correct
3 Correct 152 ms 287844 KB Output is correct
4 Correct 142 ms 288064 KB Output is correct
5 Correct 108 ms 288104 KB Output is correct
6 Correct 118 ms 287984 KB Output is correct
7 Correct 113 ms 287988 KB Output is correct
8 Correct 118 ms 288232 KB Output is correct
9 Correct 149 ms 287988 KB Output is correct
10 Correct 118 ms 287988 KB Output is correct
11 Correct 117 ms 287840 KB Output is correct
12 Correct 174 ms 287996 KB Output is correct
13 Correct 115 ms 287828 KB Output is correct
14 Correct 107 ms 286980 KB Output is correct
15 Correct 121 ms 286804 KB Output is correct
16 Correct 119 ms 287900 KB Output is correct
17 Correct 136 ms 287984 KB Output is correct
18 Correct 125 ms 287992 KB Output is correct
19 Correct 121 ms 287056 KB Output is correct
20 Correct 131 ms 287988 KB Output is correct
21 Correct 119 ms 287824 KB Output is correct
22 Correct 115 ms 287988 KB Output is correct
23 Correct 132 ms 286976 KB Output is correct
24 Correct 114 ms 287140 KB Output is correct
25 Correct 121 ms 288160 KB Output is correct
26 Correct 118 ms 287420 KB Output is correct
27 Correct 119 ms 287988 KB Output is correct
28 Correct 154 ms 287060 KB Output is correct
29 Correct 122 ms 287952 KB Output is correct
30 Correct 122 ms 288180 KB Output is correct
31 Correct 128 ms 288204 KB Output is correct
32 Correct 121 ms 288136 KB Output is correct
33 Correct 123 ms 288248 KB Output is correct
34 Correct 122 ms 287776 KB Output is correct
35 Correct 122 ms 287748 KB Output is correct
36 Correct 118 ms 287828 KB Output is correct
37 Correct 119 ms 287824 KB Output is correct
38 Correct 296 ms 304580 KB Output is correct
39 Runtime error 928 ms 987432 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 286804 KB Output is correct
2 Correct 116 ms 286800 KB Output is correct
3 Correct 127 ms 286980 KB Output is correct
4 Correct 120 ms 286804 KB Output is correct
5 Correct 126 ms 289224 KB Output is correct
6 Correct 125 ms 287824 KB Output is correct
7 Correct 122 ms 287788 KB Output is correct
8 Correct 114 ms 286844 KB Output is correct
9 Correct 119 ms 286880 KB Output is correct
10 Correct 121 ms 287316 KB Output is correct
11 Correct 126 ms 287116 KB Output is correct
12 Correct 121 ms 287824 KB Output is correct
13 Correct 168 ms 295872 KB Output is correct
14 Correct 174 ms 296140 KB Output is correct
15 Correct 173 ms 296236 KB Output is correct
16 Runtime error 791 ms 988336 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 286804 KB Output is correct
2 Correct 119 ms 286804 KB Output is correct
3 Correct 107 ms 286800 KB Output is correct
4 Correct 140 ms 291796 KB Output is correct
5 Correct 174 ms 296148 KB Output is correct
6 Correct 125 ms 287824 KB Output is correct
7 Correct 118 ms 287896 KB Output is correct
8 Correct 115 ms 287956 KB Output is correct
9 Correct 254 ms 304572 KB Output is correct
10 Runtime error 889 ms 987332 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -