oj.uz

Submission #567474

# Submission time Handle Problem Language Result Execution time Memory
567474 2022-05-23T14:48:58 Z maomao90 Jail (JOI22_jail) C++17
5 / 100
 2201 ms 543920 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 200005;
const int MAXL = 20;

int q;
int n, m;
vi adj[MAXN], radj[MAXN * 60];
int s[MAXN], t[MAXN];
int mps[MAXN], mpt[MAXN];

int p[MAXL][MAXN], id[MAXL][MAXN], ptr;
int lvl[MAXN];
void dfs(int u, int cp) {
    p[0][u] = cp;
    cerr << u << '\n';
    REP (k, 1, MAXL) {
        if (p[k - 1][u] == -1) {
            p[k][u] = -1;
        } else {
            cerr << ' ' << k << '\n';
            p[k][u] = p[k - 1][p[k - 1][u]];
            id[k][u] = ptr;
            radj[id[k - 1][u]].pb(id[k][u]);
            radj[id[k][u] ^ 1].pb(id[k - 1][u] ^ 1);
            cerr << id[k - 1][u] << " -> " << id[k][u] << '\n';
            cerr << (id[k][u] ^ 1) << " -> " << (id[k - 1][u] ^ 1) << '\n';
            if (p[k][u] != -1) {
                radj[id[k - 1][p[k - 1][u]]].pb(id[k][u]);
                radj[id[k][u] ^ 1].pb(id[k - 1][p[k - 1][u]] ^ 1);
                cerr << id[k - 1][p[k - 1][u]] << " -> " << id[k][u] << '\n';
                cerr << (id[k][u] ^ 1) << " -> " << (id[k - 1][p[k - 1][u]] ^ 1) << '\n';
            }
            ptr += 2;
        }
    }
    for (int v : adj[u]) {
        if (v == cp) continue;
        lvl[v] = lvl[u] + 1;
        dfs(v, u);
    }
}

int vis[MAXN * 60];
bool cyc;
void rdfs(int u) {
    vis[u] = 1;
    for (int v : radj[u]) {
        if (vis[v] == 1) {
            cyc = 1;
        } else if (!vis[v]) {
            rdfs(v);
        }
    }
    vis[u] = 2;
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> q;
    while (q--) {
        cin >> n;
        REP (i, 0, n + 1) {
            adj[i].clear();
            mps[i] = 0, mpt[i] = 0;
        }
        REP (i, 1, n) {
            int a, b; cin >> a >> b;
            adj[a].pb(b);
            adj[b].pb(a);
        }
        cin >> m;
        ptr = m;
        if (ptr & 1) {
            ptr++;
        }
        REP (i, 1, n + 1) {
            id[0][i] = ptr;
            ptr += 2;
        }
        REP (i, 0, m) {
            cin >> s[i] >> t[i];
            mps[s[i]] = i, mpt[t[i]] = i;
            radj[i].pb(id[0][s[i]]);
            radj[id[0][t[i]] ^ 1].pb(i);
            cerr << i << " -> " << id[0][s[i]] << '\n';
            cerr << (id[0][t[i]] ^ 1) << " -> " << i << '\n';
        }
        dfs(1, -1);
        REP (i, 0, m) {
            int u = s[i], v = t[i];
            if (mpt[u] != 0) {
                radj[i].pb(mpt[u]);
                cerr << i << " -> " << mpt[u] << '\n';
            }
            if (mps[v] != 0) {
                radj[mps[v]].pb(i);
                cerr << mps[v] << " -> " << i << '\n';
            }
            if (lvl[u] < lvl[v]) {
                swap(u, v);
            }
            auto jump = [&] (int &u, int k) {
                radj[id[k][u]].pb(i);
                radj[i].pb(id[k][u] ^ 1);
                cerr << id[k][u] << " -> " << i << '\n';
                cerr << i << " -> " << (id[k][u] ^ 1) << '\n';
                u = p[k][u];
            };
            u = p[0][u];
            RREP (k, MAXL - 1, 0) {
                if (p[k][u] == -1) continue;
                if (lvl[p[k][u]] >= lvl[v]) {
                    jump(u, k);
                }
            }
            bool hasj = 0;
            if (lvl[u] < lvl[v]) {
                hasj = 1;
                v = p[0][v];
            }
            if (u == v) {
                continue;
            }
            if (hasj) {
                jump(v, 0);
            } else {
                v = p[0][v];
            }
            jump(u, 0);
            RREP (k, MAXL - 1, 0) {
                if (p[k][u] != p[k][v]) {
                    jump(u, k);
                    jump(v, k);
                }
            }
            if (u != v) {
                jump(u, 0); jump(v, 0);
            }
            jump(u, 0);
        }
        cyc = 0;
        REP (i, 0, ptr) {
            if (vis[i]) continue;
            rdfs(i);
            if (cyc) {
                break;
            }
        }
        if (cyc) {
            cout << "No\n";
        } else {
            cout << "Yes\n";
        }
        REP (i, 0, ptr) {
            radj[i].clear();
            vis[i] = 0;
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 286996 KB Output is correct
2 Correct 135 ms 286900 KB Output is correct
3 Correct 136 ms 286900 KB Output is correct
4 Correct 181 ms 286960 KB Output is correct
5 Correct 183 ms 286992 KB Output is correct
6 Correct 135 ms 287192 KB Output is correct
7 Correct 138 ms 287124 KB Output is correct
8 Correct 155 ms 287160 KB Output is correct
9 Correct 351 ms 293844 KB Output is correct
10 Correct 1433 ms 456276 KB Output is correct
11 Correct 142 ms 286924 KB Output is correct
12 Correct 209 ms 287100 KB Output is correct
13 Correct 1228 ms 461100 KB Output is correct
14 Correct 1109 ms 461100 KB Output is correct
15 Correct 1605 ms 487484 KB Output is correct
16 Correct 2201 ms 543920 KB Output is correct
17 Correct 1589 ms 465396 KB Output is correct
18 Correct 1236 ms 465172 KB Output is correct
19 Correct 1459 ms 465652 KB Output is correct
20 Correct 1087 ms 465444 KB Output is correct
21 Correct 1402 ms 487948 KB Output is correct
22 Correct 1052 ms 460760 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 286920 KB Output is correct
2 Correct 143 ms 287088 KB Output is correct
3 Correct 162 ms 287076 KB Output is correct
4 Correct 144 ms 287264 KB Output is correct
5 Correct 137 ms 287048 KB Output is correct
6 Correct 136 ms 287104 KB Output is correct
7 Correct 143 ms 287132 KB Output is correct
8 Correct 149 ms 287224 KB Output is correct
9 Correct 136 ms 287064 KB Output is correct
10 Correct 134 ms 287072 KB Output is correct
11 Correct 139 ms 287084 KB Output is correct
12 Incorrect 143 ms 286924 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 286920 KB Output is correct
2 Correct 143 ms 287088 KB Output is correct
3 Correct 162 ms 287076 KB Output is correct
4 Correct 144 ms 287264 KB Output is correct
5 Correct 137 ms 287048 KB Output is correct
6 Correct 136 ms 287104 KB Output is correct
7 Correct 143 ms 287132 KB Output is correct
8 Correct 149 ms 287224 KB Output is correct
9 Correct 136 ms 287064 KB Output is correct
10 Correct 134 ms 287072 KB Output is correct
11 Correct 139 ms 287084 KB Output is correct
12 Incorrect 143 ms 286924 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 286920 KB Output is correct
2 Correct 143 ms 287088 KB Output is correct
3 Correct 162 ms 287076 KB Output is correct
4 Correct 144 ms 287264 KB Output is correct
5 Correct 137 ms 287048 KB Output is correct
6 Correct 136 ms 287104 KB Output is correct
7 Correct 143 ms 287132 KB Output is correct
8 Correct 149 ms 287224 KB Output is correct
9 Correct 136 ms 287064 KB Output is correct
10 Correct 134 ms 287072 KB Output is correct
11 Correct 139 ms 287084 KB Output is correct
12 Incorrect 143 ms 286924 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 286920 KB Output is correct
2 Correct 143 ms 287088 KB Output is correct
3 Correct 162 ms 287076 KB Output is correct
4 Correct 144 ms 287264 KB Output is correct
5 Correct 137 ms 287048 KB Output is correct
6 Correct 136 ms 287104 KB Output is correct
7 Correct 143 ms 287132 KB Output is correct
8 Correct 149 ms 287224 KB Output is correct
9 Correct 136 ms 287064 KB Output is correct
10 Correct 134 ms 287072 KB Output is correct
11 Correct 139 ms 287084 KB Output is correct
12 Incorrect 143 ms 286924 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 286964 KB Output is correct
2 Correct 151 ms 286972 KB Output is correct
3 Correct 136 ms 286872 KB Output is correct
4 Correct 136 ms 286944 KB Output is correct
5 Correct 167 ms 287012 KB Output is correct
6 Incorrect 143 ms 286924 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 286996 KB Output is correct
2 Correct 135 ms 286900 KB Output is correct
3 Correct 136 ms 286900 KB Output is correct
4 Correct 181 ms 286960 KB Output is correct
5 Correct 183 ms 286992 KB Output is correct
6 Correct 135 ms 287192 KB Output is correct
7 Correct 138 ms 287124 KB Output is correct
8 Correct 155 ms 287160 KB Output is correct
9 Correct 351 ms 293844 KB Output is correct
10 Correct 1433 ms 456276 KB Output is correct
11 Correct 142 ms 286924 KB Output is correct
12 Correct 209 ms 287100 KB Output is correct
13 Correct 1228 ms 461100 KB Output is correct
14 Correct 1109 ms 461100 KB Output is correct
15 Correct 1605 ms 487484 KB Output is correct
16 Correct 2201 ms 543920 KB Output is correct
17 Correct 1589 ms 465396 KB Output is correct
18 Correct 1236 ms 465172 KB Output is correct
19 Correct 1459 ms 465652 KB Output is correct
20 Correct 1087 ms 465444 KB Output is correct
21 Correct 1402 ms 487948 KB Output is correct
22 Correct 1052 ms 460760 KB Output is correct
23 Correct 136 ms 286920 KB Output is correct
24 Correct 143 ms 287088 KB Output is correct
25 Correct 162 ms 287076 KB Output is correct
26 Correct 144 ms 287264 KB Output is correct
27 Correct 137 ms 287048 KB Output is correct
28 Correct 136 ms 287104 KB Output is correct
29 Correct 143 ms 287132 KB Output is correct
30 Correct 149 ms 287224 KB Output is correct
31 Correct 136 ms 287064 KB Output is correct
32 Correct 134 ms 287072 KB Output is correct
33 Correct 139 ms 287084 KB Output is correct
34 Incorrect 143 ms 286924 KB Output isn't correct
35 Halted 0 ms 0 KB -