oj.uz

Submission #567468

# Submission time Handle Problem Language Result Execution time Memory
567468 2022-05-23T14:39:12 Z maomao90 Jail (JOI22_jail) C++17
5 / 100
 2141 ms 497148 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 * 50];
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, m) {
            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 115 ms 239956 KB Output is correct
2 Correct 119 ms 240000 KB Output is correct
3 Correct 111 ms 239908 KB Output is correct
4 Correct 129 ms 240124 KB Output is correct
5 Correct 171 ms 240232 KB Output is correct
6 Correct 133 ms 240280 KB Output is correct
7 Correct 113 ms 240204 KB Output is correct
8 Correct 130 ms 240268 KB Output is correct
9 Correct 338 ms 246824 KB Output is correct
10 Correct 954 ms 409464 KB Output is correct
11 Correct 121 ms 240168 KB Output is correct
12 Correct 172 ms 240260 KB Output is correct
13 Correct 1169 ms 414192 KB Output is correct
14 Correct 1057 ms 414248 KB Output is correct
15 Correct 1735 ms 440508 KB Output is correct
16 Correct 2141 ms 497148 KB Output is correct
17 Correct 1308 ms 418728 KB Output is correct
18 Correct 1143 ms 418320 KB Output is correct
19 Correct 1313 ms 418648 KB Output is correct
20 Correct 1116 ms 418652 KB Output is correct
21 Correct 1422 ms 441128 KB Output is correct
22 Correct 987 ms 413936 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 239972 KB Output is correct
2 Correct 120 ms 239952 KB Output is correct
3 Correct 116 ms 240324 KB Output is correct
4 Correct 123 ms 240212 KB Output is correct
5 Correct 120 ms 240180 KB Output is correct
6 Correct 117 ms 240192 KB Output is correct
7 Correct 112 ms 240172 KB Output is correct
8 Correct 111 ms 240208 KB Output is correct
9 Correct 120 ms 240076 KB Output is correct
10 Correct 118 ms 240200 KB Output is correct
11 Correct 117 ms 240148 KB Output is correct
12 Incorrect 112 ms 240180 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 239972 KB Output is correct
2 Correct 120 ms 239952 KB Output is correct
3 Correct 116 ms 240324 KB Output is correct
4 Correct 123 ms 240212 KB Output is correct
5 Correct 120 ms 240180 KB Output is correct
6 Correct 117 ms 240192 KB Output is correct
7 Correct 112 ms 240172 KB Output is correct
8 Correct 111 ms 240208 KB Output is correct
9 Correct 120 ms 240076 KB Output is correct
10 Correct 118 ms 240200 KB Output is correct
11 Correct 117 ms 240148 KB Output is correct
12 Incorrect 112 ms 240180 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 239972 KB Output is correct
2 Correct 120 ms 239952 KB Output is correct
3 Correct 116 ms 240324 KB Output is correct
4 Correct 123 ms 240212 KB Output is correct
5 Correct 120 ms 240180 KB Output is correct
6 Correct 117 ms 240192 KB Output is correct
7 Correct 112 ms 240172 KB Output is correct
8 Correct 111 ms 240208 KB Output is correct
9 Correct 120 ms 240076 KB Output is correct
10 Correct 118 ms 240200 KB Output is correct
11 Correct 117 ms 240148 KB Output is correct
12 Incorrect 112 ms 240180 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 239972 KB Output is correct
2 Correct 120 ms 239952 KB Output is correct
3 Correct 116 ms 240324 KB Output is correct
4 Correct 123 ms 240212 KB Output is correct
5 Correct 120 ms 240180 KB Output is correct
6 Correct 117 ms 240192 KB Output is correct
7 Correct 112 ms 240172 KB Output is correct
8 Correct 111 ms 240208 KB Output is correct
9 Correct 120 ms 240076 KB Output is correct
10 Correct 118 ms 240200 KB Output is correct
11 Correct 117 ms 240148 KB Output is correct
12 Incorrect 112 ms 240180 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 240012 KB Output is correct
2 Correct 124 ms 239996 KB Output is correct
3 Correct 109 ms 239896 KB Output is correct
4 Correct 114 ms 240000 KB Output is correct
5 Correct 128 ms 240108 KB Output is correct
6 Incorrect 118 ms 240024 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 239956 KB Output is correct
2 Correct 119 ms 240000 KB Output is correct
3 Correct 111 ms 239908 KB Output is correct
4 Correct 129 ms 240124 KB Output is correct
5 Correct 171 ms 240232 KB Output is correct
6 Correct 133 ms 240280 KB Output is correct
7 Correct 113 ms 240204 KB Output is correct
8 Correct 130 ms 240268 KB Output is correct
9 Correct 338 ms 246824 KB Output is correct
10 Correct 954 ms 409464 KB Output is correct
11 Correct 121 ms 240168 KB Output is correct
12 Correct 172 ms 240260 KB Output is correct
13 Correct 1169 ms 414192 KB Output is correct
14 Correct 1057 ms 414248 KB Output is correct
15 Correct 1735 ms 440508 KB Output is correct
16 Correct 2141 ms 497148 KB Output is correct
17 Correct 1308 ms 418728 KB Output is correct
18 Correct 1143 ms 418320 KB Output is correct
19 Correct 1313 ms 418648 KB Output is correct
20 Correct 1116 ms 418652 KB Output is correct
21 Correct 1422 ms 441128 KB Output is correct
22 Correct 987 ms 413936 KB Output is correct
23 Correct 131 ms 239972 KB Output is correct
24 Correct 120 ms 239952 KB Output is correct
25 Correct 116 ms 240324 KB Output is correct
26 Correct 123 ms 240212 KB Output is correct
27 Correct 120 ms 240180 KB Output is correct
28 Correct 117 ms 240192 KB Output is correct
29 Correct 112 ms 240172 KB Output is correct
30 Correct 111 ms 240208 KB Output is correct
31 Correct 120 ms 240076 KB Output is correct
32 Correct 118 ms 240200 KB Output is correct
33 Correct 117 ms 240148 KB Output is correct
34 Incorrect 112 ms 240180 KB Output isn't correct
35 Halted 0 ms 0 KB -