oj.uz

Submission #567477

# Submission time Handle Problem Language Result Execution time Memory
567477 2022-05-23T15:00:37 Z maomao90 Jail (JOI22_jail) C++17
5 / 100
 2308 ms 546988 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;
            id[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 (id[k - 1][p[k - 1][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 164 ms 286992 KB Output is correct
2 Correct 143 ms 287120 KB Output is correct
3 Correct 146 ms 287060 KB Output is correct
4 Correct 167 ms 287148 KB Output is correct
5 Correct 178 ms 287188 KB Output is correct
6 Correct 141 ms 287268 KB Output is correct
7 Correct 154 ms 287260 KB Output is correct
8 Correct 142 ms 287284 KB Output is correct
9 Correct 357 ms 293952 KB Output is correct
10 Correct 1434 ms 459508 KB Output is correct
11 Correct 147 ms 287064 KB Output is correct
12 Correct 225 ms 287160 KB Output is correct
13 Correct 1253 ms 464160 KB Output is correct
14 Correct 1150 ms 464468 KB Output is correct
15 Correct 1726 ms 490592 KB Output is correct
16 Correct 2308 ms 546988 KB Output is correct
17 Correct 1527 ms 468556 KB Output is correct
18 Correct 1311 ms 468300 KB Output is correct
19 Correct 1484 ms 468640 KB Output is correct
20 Correct 1114 ms 468528 KB Output is correct
21 Correct 1398 ms 491044 KB Output is correct
22 Correct 1018 ms 463828 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 287060 KB Output is correct
2 Correct 138 ms 287040 KB Output is correct
3 Correct 145 ms 287152 KB Output is correct
4 Correct 152 ms 287352 KB Output is correct
5 Correct 145 ms 287124 KB Output is correct
6 Correct 139 ms 287120 KB Output is correct
7 Correct 137 ms 287228 KB Output is correct
8 Correct 138 ms 287164 KB Output is correct
9 Correct 142 ms 287216 KB Output is correct
10 Correct 151 ms 287244 KB Output is correct
11 Correct 141 ms 287240 KB Output is correct
12 Incorrect 145 ms 287064 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 287060 KB Output is correct
2 Correct 138 ms 287040 KB Output is correct
3 Correct 145 ms 287152 KB Output is correct
4 Correct 152 ms 287352 KB Output is correct
5 Correct 145 ms 287124 KB Output is correct
6 Correct 139 ms 287120 KB Output is correct
7 Correct 137 ms 287228 KB Output is correct
8 Correct 138 ms 287164 KB Output is correct
9 Correct 142 ms 287216 KB Output is correct
10 Correct 151 ms 287244 KB Output is correct
11 Correct 141 ms 287240 KB Output is correct
12 Incorrect 145 ms 287064 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 287060 KB Output is correct
2 Correct 138 ms 287040 KB Output is correct
3 Correct 145 ms 287152 KB Output is correct
4 Correct 152 ms 287352 KB Output is correct
5 Correct 145 ms 287124 KB Output is correct
6 Correct 139 ms 287120 KB Output is correct
7 Correct 137 ms 287228 KB Output is correct
8 Correct 138 ms 287164 KB Output is correct
9 Correct 142 ms 287216 KB Output is correct
10 Correct 151 ms 287244 KB Output is correct
11 Correct 141 ms 287240 KB Output is correct
12 Incorrect 145 ms 287064 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 287060 KB Output is correct
2 Correct 138 ms 287040 KB Output is correct
3 Correct 145 ms 287152 KB Output is correct
4 Correct 152 ms 287352 KB Output is correct
5 Correct 145 ms 287124 KB Output is correct
6 Correct 139 ms 287120 KB Output is correct
7 Correct 137 ms 287228 KB Output is correct
8 Correct 138 ms 287164 KB Output is correct
9 Correct 142 ms 287216 KB Output is correct
10 Correct 151 ms 287244 KB Output is correct
11 Correct 141 ms 287240 KB Output is correct
12 Incorrect 145 ms 287064 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 286988 KB Output is correct
2 Correct 157 ms 287028 KB Output is correct
3 Correct 136 ms 287124 KB Output is correct
4 Correct 140 ms 287048 KB Output is correct
5 Correct 155 ms 287192 KB Output is correct
6 Incorrect 143 ms 287128 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 286992 KB Output is correct
2 Correct 143 ms 287120 KB Output is correct
3 Correct 146 ms 287060 KB Output is correct
4 Correct 167 ms 287148 KB Output is correct
5 Correct 178 ms 287188 KB Output is correct
6 Correct 141 ms 287268 KB Output is correct
7 Correct 154 ms 287260 KB Output is correct
8 Correct 142 ms 287284 KB Output is correct
9 Correct 357 ms 293952 KB Output is correct
10 Correct 1434 ms 459508 KB Output is correct
11 Correct 147 ms 287064 KB Output is correct
12 Correct 225 ms 287160 KB Output is correct
13 Correct 1253 ms 464160 KB Output is correct
14 Correct 1150 ms 464468 KB Output is correct
15 Correct 1726 ms 490592 KB Output is correct
16 Correct 2308 ms 546988 KB Output is correct
17 Correct 1527 ms 468556 KB Output is correct
18 Correct 1311 ms 468300 KB Output is correct
19 Correct 1484 ms 468640 KB Output is correct
20 Correct 1114 ms 468528 KB Output is correct
21 Correct 1398 ms 491044 KB Output is correct
22 Correct 1018 ms 463828 KB Output is correct
23 Correct 139 ms 287060 KB Output is correct
24 Correct 138 ms 287040 KB Output is correct
25 Correct 145 ms 287152 KB Output is correct
26 Correct 152 ms 287352 KB Output is correct
27 Correct 145 ms 287124 KB Output is correct
28 Correct 139 ms 287120 KB Output is correct
29 Correct 137 ms 287228 KB Output is correct
30 Correct 138 ms 287164 KB Output is correct
31 Correct 142 ms 287216 KB Output is correct
32 Correct 151 ms 287244 KB Output is correct
33 Correct 141 ms 287240 KB Output is correct
34 Incorrect 145 ms 287064 KB Output isn't correct
35 Halted 0 ms 0 KB -