oj.uz

Submission #986522

# Submission time Handle Problem Language Result Execution time Memory
986522 2024-05-20T17:43:56 Z ShaShi Jail (JOI22_jail) C++17
72 / 100
 2659 ms 1048576 KB 
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define kill(x) cout << x << endl, exit(0);
#define endl "\n"

 
using namespace std;
typedef long long ll;
typedef long double ld;
 

const int MAXN = (int)1e6 + 7;
const int MOD = 998244853;
const ll INF = (ll)1e18 + 7;


int t, n, m, q, tmp, tmp2, tmp3, tmp4, ans, k, u, v, w, flag, N, M;
int arr[MAXN], h[MAXN], st[MAXN], fn[MAXN], ind[MAXN], par[MAXN];
bool seen[MAXN];
vector<int> adj[MAXN], G[MAXN], ord, Ss[MAXN], T[MAXN];
vector<pii> edge;


void DFSsz(int v) {
    seen[v] = 1;

    for (int u:adj[v]) {
        if (seen[u]) continue;
        
        h[u] = h[v]+1; par[u] = v;

        DFSsz(u);
    }
}


inline void add_edge(int u, int v) {
    if (u == v) return;

    G[u].pb(v);
    edge.pb(mp(u, v));
}


inline void check(int ind, int v) {
    for (int x:Ss[v]) add_edge(x, ind);
    for (int x:T[v]) add_edge(ind, x);
}


inline void process(int ind, int u, int v) {
    if (h[u] > h[v]) swap(u, v);

    while (h[v] > h[u]) {
        check(ind, v); v = par[v];
    }

    while (u != v) {
        check(ind, u); check(ind, v);
        u = par[u]; v = par[v];
    }

    check(ind, u);
}


void DFS(int v) {
    seen[v] = 1;

    for (int u:G[v]) if (!seen[u]) DFS(u);
    
    ord.pb(v);
}


void solve() {
    cin >> n;

    for (int i=0; i<n+7; i++) adj[i].clear(), G[i].clear(), Ss[i].clear(), T[i].clear();
    edge.clear(); ord.clear(); fill(seen, seen+n+7, 0);
    fill(h, h+n+7, 0); fill(ind, ind+n+7, 0); fill(par, par+n+7, 0);

    for (int i=1; i<n; i++) {
        cin >> u >> v;

        adj[u].pb(v); adj[v].pb(u);
    }
    
    DFSsz(1);

    cin >> m;

    for (int i=1; i<=m; i++) {
        cin >> st[i] >> fn[i];

        Ss[st[i]].pb(i); T[fn[i]].pb(i);
    }

    for (int i=1; i<=m; i++) process(i, st[i], fn[i]);

    ord.clear(); fill(seen, seen+n+1, 0);

    for (int i=1; i<=m; i++) if (!seen[i]) DFS(i);
    for (int i=0; i<m; i++) ind[ord[i]] = i;

    for (auto cur:edge) {
        if (ind[cur.F] < ind[cur.S]) {
            cout << "No\n";
            return;
        }
    }

    cout << "Yes\n";
}


int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> t;

    while (t--) solve();

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94300 KB Output is correct
2 Correct 42 ms 94292 KB Output is correct
3 Correct 44 ms 94352 KB Output is correct
4 Correct 48 ms 94556 KB Output is correct
5 Correct 56 ms 95068 KB Output is correct
6 Correct 46 ms 94308 KB Output is correct
7 Correct 45 ms 94480 KB Output is correct
8 Correct 46 ms 94872 KB Output is correct
9 Correct 117 ms 104320 KB Output is correct
10 Correct 236 ms 116524 KB Output is correct
11 Correct 46 ms 94548 KB Output is correct
12 Correct 72 ms 95800 KB Output is correct
13 Correct 280 ms 292216 KB Output is correct
14 Correct 321 ms 317788 KB Output is correct
15 Runtime error 2659 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94292 KB Output is correct
2 Correct 48 ms 94400 KB Output is correct
3 Correct 48 ms 94288 KB Output is correct
4 Correct 49 ms 94468 KB Output is correct
5 Correct 54 ms 94472 KB Output is correct
6 Correct 49 ms 94300 KB Output is correct
7 Correct 51 ms 94332 KB Output is correct
8 Correct 52 ms 94228 KB Output is correct
9 Correct 50 ms 94280 KB Output is correct
10 Correct 48 ms 94468 KB Output is correct
11 Correct 49 ms 94288 KB Output is correct
12 Correct 53 ms 94296 KB Output is correct
13 Correct 48 ms 94316 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94292 KB Output is correct
2 Correct 48 ms 94400 KB Output is correct
3 Correct 48 ms 94288 KB Output is correct
4 Correct 49 ms 94468 KB Output is correct
5 Correct 54 ms 94472 KB Output is correct
6 Correct 49 ms 94300 KB Output is correct
7 Correct 51 ms 94332 KB Output is correct
8 Correct 52 ms 94228 KB Output is correct
9 Correct 50 ms 94280 KB Output is correct
10 Correct 48 ms 94468 KB Output is correct
11 Correct 49 ms 94288 KB Output is correct
12 Correct 53 ms 94296 KB Output is correct
13 Correct 48 ms 94316 KB Output is correct
14 Correct 47 ms 94292 KB Output is correct
15 Correct 53 ms 94360 KB Output is correct
16 Correct 50 ms 94404 KB Output is correct
17 Correct 48 ms 94352 KB Output is correct
18 Correct 48 ms 94300 KB Output is correct
19 Correct 47 ms 94300 KB Output is correct
20 Correct 48 ms 94292 KB Output is correct
21 Correct 48 ms 94268 KB Output is correct
22 Correct 48 ms 94488 KB Output is correct
23 Correct 54 ms 94292 KB Output is correct
24 Correct 47 ms 94416 KB Output is correct
25 Correct 49 ms 94288 KB Output is correct
26 Correct 49 ms 94296 KB Output is correct
27 Correct 48 ms 94292 KB Output is correct
28 Correct 49 ms 94300 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94292 KB Output is correct
2 Correct 48 ms 94400 KB Output is correct
3 Correct 48 ms 94288 KB Output is correct
4 Correct 49 ms 94468 KB Output is correct
5 Correct 54 ms 94472 KB Output is correct
6 Correct 49 ms 94300 KB Output is correct
7 Correct 51 ms 94332 KB Output is correct
8 Correct 52 ms 94228 KB Output is correct
9 Correct 50 ms 94280 KB Output is correct
10 Correct 48 ms 94468 KB Output is correct
11 Correct 49 ms 94288 KB Output is correct
12 Correct 53 ms 94296 KB Output is correct
13 Correct 48 ms 94316 KB Output is correct
14 Correct 47 ms 94292 KB Output is correct
15 Correct 53 ms 94360 KB Output is correct
16 Correct 50 ms 94404 KB Output is correct
17 Correct 48 ms 94352 KB Output is correct
18 Correct 48 ms 94300 KB Output is correct
19 Correct 47 ms 94300 KB Output is correct
20 Correct 48 ms 94292 KB Output is correct
21 Correct 48 ms 94268 KB Output is correct
22 Correct 48 ms 94488 KB Output is correct
23 Correct 54 ms 94292 KB Output is correct
24 Correct 47 ms 94416 KB Output is correct
25 Correct 49 ms 94288 KB Output is correct
26 Correct 49 ms 94296 KB Output is correct
27 Correct 48 ms 94292 KB Output is correct
28 Correct 49 ms 94300 KB Output is correct
29 Correct 51 ms 94948 KB Output is correct
30 Correct 49 ms 94292 KB Output is correct
31 Correct 49 ms 94556 KB Output is correct
32 Correct 48 ms 94296 KB Output is correct
33 Correct 49 ms 94292 KB Output is correct
34 Correct 52 ms 94544 KB Output is correct
35 Correct 50 ms 94704 KB Output is correct
36 Correct 49 ms 94548 KB Output is correct
37 Correct 49 ms 94504 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94292 KB Output is correct
2 Correct 48 ms 94400 KB Output is correct
3 Correct 48 ms 94288 KB Output is correct
4 Correct 49 ms 94468 KB Output is correct
5 Correct 54 ms 94472 KB Output is correct
6 Correct 49 ms 94300 KB Output is correct
7 Correct 51 ms 94332 KB Output is correct
8 Correct 52 ms 94228 KB Output is correct
9 Correct 50 ms 94280 KB Output is correct
10 Correct 48 ms 94468 KB Output is correct
11 Correct 49 ms 94288 KB Output is correct
12 Correct 53 ms 94296 KB Output is correct
13 Correct 48 ms 94316 KB Output is correct
14 Correct 47 ms 94292 KB Output is correct
15 Correct 53 ms 94360 KB Output is correct
16 Correct 50 ms 94404 KB Output is correct
17 Correct 48 ms 94352 KB Output is correct
18 Correct 48 ms 94300 KB Output is correct
19 Correct 47 ms 94300 KB Output is correct
20 Correct 48 ms 94292 KB Output is correct
21 Correct 48 ms 94268 KB Output is correct
22 Correct 48 ms 94488 KB Output is correct
23 Correct 54 ms 94292 KB Output is correct
24 Correct 47 ms 94416 KB Output is correct
25 Correct 49 ms 94288 KB Output is correct
26 Correct 49 ms 94296 KB Output is correct
27 Correct 48 ms 94292 KB Output is correct
28 Correct 49 ms 94300 KB Output is correct
29 Correct 51 ms 94948 KB Output is correct
30 Correct 49 ms 94292 KB Output is correct
31 Correct 49 ms 94556 KB Output is correct
32 Correct 48 ms 94296 KB Output is correct
33 Correct 49 ms 94292 KB Output is correct
34 Correct 52 ms 94544 KB Output is correct
35 Correct 50 ms 94704 KB Output is correct
36 Correct 49 ms 94548 KB Output is correct
37 Correct 49 ms 94504 KB Output is correct
38 Correct 117 ms 104272 KB Output is correct
39 Correct 248 ms 116508 KB Output is correct
40 Correct 89 ms 99780 KB Output is correct
41 Correct 69 ms 96340 KB Output is correct
42 Correct 83 ms 100100 KB Output is correct
43 Correct 63 ms 96088 KB Output is correct
44 Correct 53 ms 95056 KB Output is correct
45 Correct 82 ms 102996 KB Output is correct
46 Correct 99 ms 103116 KB Output is correct
47 Correct 104 ms 107076 KB Output is correct
48 Correct 105 ms 106676 KB Output is correct
49 Correct 93 ms 103324 KB Output is correct
50 Correct 87 ms 103312 KB Output is correct
51 Correct 86 ms 104320 KB Output is correct
52 Correct 79 ms 104260 KB Output is correct
53 Correct 55 ms 95316 KB Output is correct
54 Correct 87 ms 103816 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94300 KB Output is correct
2 Correct 48 ms 94276 KB Output is correct
3 Correct 49 ms 94372 KB Output is correct
4 Correct 48 ms 94404 KB Output is correct
5 Correct 53 ms 94544 KB Output is correct
6 Correct 51 ms 94224 KB Output is correct
7 Correct 49 ms 94300 KB Output is correct
8 Correct 49 ms 94404 KB Output is correct
9 Correct 48 ms 94288 KB Output is correct
10 Correct 48 ms 94292 KB Output is correct
11 Correct 48 ms 94420 KB Output is correct
12 Correct 48 ms 94312 KB Output is correct
13 Correct 60 ms 95056 KB Output is correct
14 Correct 66 ms 95092 KB Output is correct
15 Correct 62 ms 95060 KB Output is correct
16 Correct 92 ms 104984 KB Output is correct
17 Correct 233 ms 132508 KB Output is correct
18 Correct 553 ms 229692 KB Output is correct
19 Correct 99 ms 106320 KB Output is correct
20 Correct 84 ms 106692 KB Output is correct
21 Correct 83 ms 106516 KB Output is correct
22 Correct 183 ms 135348 KB Output is correct
23 Correct 155 ms 135896 KB Output is correct
24 Correct 150 ms 135104 KB Output is correct
25 Correct 156 ms 135824 KB Output is correct
26 Correct 162 ms 135840 KB Output is correct
27 Correct 201 ms 125832 KB Output is correct
28 Correct 198 ms 129716 KB Output is correct
29 Correct 197 ms 126892 KB Output is correct
30 Correct 117 ms 114872 KB Output is correct
31 Correct 120 ms 115400 KB Output is correct
32 Correct 115 ms 114120 KB Output is correct
33 Correct 117 ms 115400 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94300 KB Output is correct
2 Correct 42 ms 94292 KB Output is correct
3 Correct 44 ms 94352 KB Output is correct
4 Correct 48 ms 94556 KB Output is correct
5 Correct 56 ms 95068 KB Output is correct
6 Correct 46 ms 94308 KB Output is correct
7 Correct 45 ms 94480 KB Output is correct
8 Correct 46 ms 94872 KB Output is correct
9 Correct 117 ms 104320 KB Output is correct
10 Correct 236 ms 116524 KB Output is correct
11 Correct 46 ms 94548 KB Output is correct
12 Correct 72 ms 95800 KB Output is correct
13 Correct 280 ms 292216 KB Output is correct
14 Correct 321 ms 317788 KB Output is correct
15 Runtime error 2659 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -