oj.uz

Submission #567453

# Submission time Handle Problem Language Result Execution time Memory
567453 2022-05-23T13:43:49 Z maomao90 Jail (JOI22_jail) C++17
5 / 100
 2133 ms 498476 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]) {
        cerr << u << ' ' << v << '\n';
        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);
                }
            }
            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 113 ms 239996 KB Output is correct
2 Correct 116 ms 239948 KB Output is correct
3 Correct 135 ms 239900 KB Output is correct
4 Correct 136 ms 240440 KB Output is correct
5 Correct 153 ms 240684 KB Output is correct
6 Correct 116 ms 240204 KB Output is correct
7 Correct 124 ms 240252 KB Output is correct
8 Correct 118 ms 240212 KB Output is correct
9 Correct 386 ms 248036 KB Output is correct
10 Correct 1006 ms 410768 KB Output is correct
11 Correct 123 ms 240240 KB Output is correct
12 Correct 188 ms 241120 KB Output is correct
13 Correct 1184 ms 415880 KB Output is correct
14 Correct 1205 ms 416012 KB Output is correct
15 Correct 1662 ms 442444 KB Output is correct
16 Correct 2133 ms 498476 KB Output is correct
17 Correct 1384 ms 419984 KB Output is correct
18 Correct 1167 ms 419728 KB Output is correct
19 Correct 1274 ms 419892 KB Output is correct
20 Correct 1062 ms 419860 KB Output is correct
21 Correct 1353 ms 442484 KB Output is correct
22 Correct 1008 ms 415340 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 239892 KB Output is correct
2 Correct 123 ms 239888 KB Output is correct
3 Correct 121 ms 240256 KB Output is correct
4 Correct 115 ms 240192 KB Output is correct
5 Correct 143 ms 240084 KB Output is correct
6 Correct 133 ms 240080 KB Output is correct
7 Correct 117 ms 240176 KB Output is correct
8 Correct 124 ms 240264 KB Output is correct
9 Correct 119 ms 240204 KB Output is correct
10 Correct 138 ms 240300 KB Output is correct
11 Correct 119 ms 240108 KB Output is correct
12 Incorrect 115 ms 240048 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 239892 KB Output is correct
2 Correct 123 ms 239888 KB Output is correct
3 Correct 121 ms 240256 KB Output is correct
4 Correct 115 ms 240192 KB Output is correct
5 Correct 143 ms 240084 KB Output is correct
6 Correct 133 ms 240080 KB Output is correct
7 Correct 117 ms 240176 KB Output is correct
8 Correct 124 ms 240264 KB Output is correct
9 Correct 119 ms 240204 KB Output is correct
10 Correct 138 ms 240300 KB Output is correct
11 Correct 119 ms 240108 KB Output is correct
12 Incorrect 115 ms 240048 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 239892 KB Output is correct
2 Correct 123 ms 239888 KB Output is correct
3 Correct 121 ms 240256 KB Output is correct
4 Correct 115 ms 240192 KB Output is correct
5 Correct 143 ms 240084 KB Output is correct
6 Correct 133 ms 240080 KB Output is correct
7 Correct 117 ms 240176 KB Output is correct
8 Correct 124 ms 240264 KB Output is correct
9 Correct 119 ms 240204 KB Output is correct
10 Correct 138 ms 240300 KB Output is correct
11 Correct 119 ms 240108 KB Output is correct
12 Incorrect 115 ms 240048 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 239892 KB Output is correct
2 Correct 123 ms 239888 KB Output is correct
3 Correct 121 ms 240256 KB Output is correct
4 Correct 115 ms 240192 KB Output is correct
5 Correct 143 ms 240084 KB Output is correct
6 Correct 133 ms 240080 KB Output is correct
7 Correct 117 ms 240176 KB Output is correct
8 Correct 124 ms 240264 KB Output is correct
9 Correct 119 ms 240204 KB Output is correct
10 Correct 138 ms 240300 KB Output is correct
11 Correct 119 ms 240108 KB Output is correct
12 Incorrect 115 ms 240048 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 239964 KB Output is correct
2 Correct 119 ms 240016 KB Output is correct
3 Correct 135 ms 239972 KB Output is correct
4 Correct 117 ms 239996 KB Output is correct
5 Correct 134 ms 240084 KB Output is correct
6 Incorrect 117 ms 240072 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 239996 KB Output is correct
2 Correct 116 ms 239948 KB Output is correct
3 Correct 135 ms 239900 KB Output is correct
4 Correct 136 ms 240440 KB Output is correct
5 Correct 153 ms 240684 KB Output is correct
6 Correct 116 ms 240204 KB Output is correct
7 Correct 124 ms 240252 KB Output is correct
8 Correct 118 ms 240212 KB Output is correct
9 Correct 386 ms 248036 KB Output is correct
10 Correct 1006 ms 410768 KB Output is correct
11 Correct 123 ms 240240 KB Output is correct
12 Correct 188 ms 241120 KB Output is correct
13 Correct 1184 ms 415880 KB Output is correct
14 Correct 1205 ms 416012 KB Output is correct
15 Correct 1662 ms 442444 KB Output is correct
16 Correct 2133 ms 498476 KB Output is correct
17 Correct 1384 ms 419984 KB Output is correct
18 Correct 1167 ms 419728 KB Output is correct
19 Correct 1274 ms 419892 KB Output is correct
20 Correct 1062 ms 419860 KB Output is correct
21 Correct 1353 ms 442484 KB Output is correct
22 Correct 1008 ms 415340 KB Output is correct
23 Correct 143 ms 239892 KB Output is correct
24 Correct 123 ms 239888 KB Output is correct
25 Correct 121 ms 240256 KB Output is correct
26 Correct 115 ms 240192 KB Output is correct
27 Correct 143 ms 240084 KB Output is correct
28 Correct 133 ms 240080 KB Output is correct
29 Correct 117 ms 240176 KB Output is correct
30 Correct 124 ms 240264 KB Output is correct
31 Correct 119 ms 240204 KB Output is correct
32 Correct 138 ms 240300 KB Output is correct
33 Correct 119 ms 240108 KB Output is correct
34 Incorrect 115 ms 240048 KB Output isn't correct
35 Halted 0 ms 0 KB -