oj.uz

Submission #582115

# Submission time Handle Problem Language Result Execution time Memory
582115 2022-06-23T11:51:21 Z Lobo Jail (JOI22_jail) C++17
100 / 100
 2367 ms 362416 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e19 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 12e4+10;

int n, m, pp[maxn][20], pai[maxn], gr[45*maxn], h[maxn], s[maxn], t[maxn], up[maxn][20], dw[maxn][20];
vector<int> g[maxn], gts[45*maxn];
int cnt = 0;

void dfslca(int u, int ant) {
    pai[u] = ant;
    pp[u][0] = ant;
    for(int i = 1; i <= 19; i++) {
        pp[u][i] = pp[pp[u][i-1]][i-1];
    }

    //cria up
    up[u][0] = ++cnt;
    for(int i = 1; i <= 19; i++) {
        //liga dos de baixo pra cima
        up[u][i] = ++cnt;
        gts[up[u][i-1]].pb(up[u][i]);
        gts[up[pp[u][i-1]][i-1]].pb(up[u][i]);
    }

    //cria dw
    dw[u][0] = ++cnt;
    for(int i = 1; i <= 19; i++) {
        //liga do de cima para os debaixo
        dw[u][i] = ++cnt;
        gts[dw[u][i]].pb(dw[u][i-1]);
        gts[dw[u][i]].pb(dw[pp[u][i-1]][i-1]);
    }

    for(auto v : g[u]) if(v != ant) {
        h[v] = h[u]+1;
        dfslca(v,u);
    }
}

int lca(int u, int v) {
    if(h[u] < h[v]) swap(u,v);
    for(int i = 19; i >= 0; i--) {
        if(h[pp[u][i]] >= h[v]) {
            u = pp[u][i];
        }
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--) {
        if(pp[u][i] != pp[v][i]) {
            u = pp[u][i];
            v = pp[v][i];
        }
    }
    return pp[u][0];
}

void solve() {
    cin >> n;
    cnt = 0;
    for(int i = 0; i <= n; i++) {
        g[i].clear();
    }
    for(int i = 0; i < n-1; i++) {
        int u,v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    cin >> m;
    cnt = m;
    h[0] = 0;
    h[1] = 1;
    dfslca(1,0);
    for(int i = 1; i <= m; i++) {
        cin >> s[i] >> t[i];
        if(s[i] == t[i]) return;
        //liga do i para s[i] e t[i]
        gts[i].pb(up[s[i]][0]);
        gts[dw[t[i]][0]].pb(i);
    }

    for(int i = 1; i <= m; i++) {
        int lc = lca(s[i],t[i]);
        // cout << s[i] << " "<< t[i] << " " << lc << endl;
        int v;
        //nao quero ligar do s[i] ate mim, entao faco o dw separado
        gts[i].pb(dw[s[i]][0]);
        v = pai[s[i]];
        //quero ir ate um antes do lc
        for(int j = 19; j >= 0; j--) {
            if(v != 0 && h[pp[v][j]] >= h[lc]) {
                gts[i].pb(dw[v][j]);
                gts[up[v][j]].pb(i);
                v = pp[v][j];
            }
        }
        
        gts[up[t[i]][0]].pb(i);
        v = pai[t[i]];
        //quero ir ate um antes do lc
        for(int j = 19; j >= 0; j--) {
            if(v != 0 && h[pp[v][j]] >= h[lc]) {
                gts[i].pb(dw[v][j]);
                gts[up[v][j]].pb(i);
                v = pp[v][j];
            }
        }

        if(lc != s[i] && lc != t[i]) {
            gts[i].pb(dw[lc][0]);
            gts[up[lc][0]].pb(i);
        }
    }

    for(int i = 1; i <= cnt; i++) {
        for(auto v : gts[i]) {
            gr[v]++;
        }
    }

    queue<int> q;
    for(int i = 1; i <= cnt; i++) {
        // cout << i << " " << gr[i] << endl;
        if(gr[i] == 0) q.push(i);
    }

    while(q.size()) {
        int u = q.front();
        q.pop();
        for(auto v : gts[u]) {
            if(--gr[v] == 0) q.push(v);
        }
    }

    string ans = "Yes";
    for(int i = 1; i <= m; i++) {
        if(gr[i] != 0) ans = "No";
    }
    cout << ans << endl;


    for(int i = 0; i <= cnt; i++) {
        gts[i].clear();
        gr[i] = 0;
    }
}

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

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 129948 KB Output is correct
2 Correct 59 ms 129916 KB Output is correct
3 Correct 66 ms 130072 KB Output is correct
4 Correct 174 ms 130596 KB Output is correct
5 Correct 264 ms 130888 KB Output is correct
6 Correct 80 ms 130452 KB Output is correct
7 Correct 81 ms 130472 KB Output is correct
8 Correct 73 ms 130408 KB Output is correct
9 Correct 594 ms 142020 KB Output is correct
10 Correct 1483 ms 340228 KB Output is correct
11 Correct 102 ms 130252 KB Output is correct
12 Correct 309 ms 131224 KB Output is correct
13 Correct 1809 ms 346268 KB Output is correct
14 Correct 1298 ms 346280 KB Output is correct
15 Correct 1517 ms 348096 KB Output is correct
16 Correct 1869 ms 360880 KB Output is correct
17 Correct 1738 ms 349924 KB Output is correct
18 Correct 1776 ms 350312 KB Output is correct
19 Correct 1804 ms 349872 KB Output is correct
20 Correct 1665 ms 350116 KB Output is correct
21 Correct 1322 ms 349380 KB Output is correct
22 Correct 1506 ms 345208 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 129996 KB Output is correct
2 Correct 67 ms 129900 KB Output is correct
3 Correct 78 ms 130484 KB Output is correct
4 Correct 78 ms 130392 KB Output is correct
5 Correct 79 ms 130380 KB Output is correct
6 Correct 80 ms 130396 KB Output is correct
7 Correct 82 ms 130676 KB Output is correct
8 Correct 87 ms 130484 KB Output is correct
9 Correct 84 ms 130388 KB Output is correct
10 Correct 83 ms 130380 KB Output is correct
11 Correct 71 ms 130432 KB Output is correct
12 Correct 76 ms 130380 KB Output is correct
13 Correct 72 ms 130456 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 129996 KB Output is correct
2 Correct 67 ms 129900 KB Output is correct
3 Correct 78 ms 130484 KB Output is correct
4 Correct 78 ms 130392 KB Output is correct
5 Correct 79 ms 130380 KB Output is correct
6 Correct 80 ms 130396 KB Output is correct
7 Correct 82 ms 130676 KB Output is correct
8 Correct 87 ms 130484 KB Output is correct
9 Correct 84 ms 130388 KB Output is correct
10 Correct 83 ms 130380 KB Output is correct
11 Correct 71 ms 130432 KB Output is correct
12 Correct 76 ms 130380 KB Output is correct
13 Correct 72 ms 130456 KB Output is correct
14 Correct 69 ms 129988 KB Output is correct
15 Correct 65 ms 129932 KB Output is correct
16 Correct 73 ms 130368 KB Output is correct
17 Correct 76 ms 130508 KB Output is correct
18 Correct 71 ms 130384 KB Output is correct
19 Correct 75 ms 130016 KB Output is correct
20 Correct 80 ms 130488 KB Output is correct
21 Correct 77 ms 130480 KB Output is correct
22 Correct 71 ms 130476 KB Output is correct
23 Correct 61 ms 129996 KB Output is correct
24 Correct 67 ms 130124 KB Output is correct
25 Correct 87 ms 130468 KB Output is correct
26 Correct 67 ms 130284 KB Output is correct
27 Correct 79 ms 130476 KB Output is correct
28 Correct 65 ms 130004 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 129996 KB Output is correct
2 Correct 67 ms 129900 KB Output is correct
3 Correct 78 ms 130484 KB Output is correct
4 Correct 78 ms 130392 KB Output is correct
5 Correct 79 ms 130380 KB Output is correct
6 Correct 80 ms 130396 KB Output is correct
7 Correct 82 ms 130676 KB Output is correct
8 Correct 87 ms 130484 KB Output is correct
9 Correct 84 ms 130388 KB Output is correct
10 Correct 83 ms 130380 KB Output is correct
11 Correct 71 ms 130432 KB Output is correct
12 Correct 76 ms 130380 KB Output is correct
13 Correct 72 ms 130456 KB Output is correct
14 Correct 69 ms 129988 KB Output is correct
15 Correct 65 ms 129932 KB Output is correct
16 Correct 73 ms 130368 KB Output is correct
17 Correct 76 ms 130508 KB Output is correct
18 Correct 71 ms 130384 KB Output is correct
19 Correct 75 ms 130016 KB Output is correct
20 Correct 80 ms 130488 KB Output is correct
21 Correct 77 ms 130480 KB Output is correct
22 Correct 71 ms 130476 KB Output is correct
23 Correct 61 ms 129996 KB Output is correct
24 Correct 67 ms 130124 KB Output is correct
25 Correct 87 ms 130468 KB Output is correct
26 Correct 67 ms 130284 KB Output is correct
27 Correct 79 ms 130476 KB Output is correct
28 Correct 65 ms 130004 KB Output is correct
29 Correct 75 ms 130508 KB Output is correct
30 Correct 85 ms 130508 KB Output is correct
31 Correct 89 ms 130500 KB Output is correct
32 Correct 89 ms 130380 KB Output is correct
33 Correct 71 ms 130432 KB Output is correct
34 Correct 75 ms 130380 KB Output is correct
35 Correct 77 ms 130424 KB Output is correct
36 Correct 80 ms 130428 KB Output is correct
37 Correct 82 ms 130388 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 129996 KB Output is correct
2 Correct 67 ms 129900 KB Output is correct
3 Correct 78 ms 130484 KB Output is correct
4 Correct 78 ms 130392 KB Output is correct
5 Correct 79 ms 130380 KB Output is correct
6 Correct 80 ms 130396 KB Output is correct
7 Correct 82 ms 130676 KB Output is correct
8 Correct 87 ms 130484 KB Output is correct
9 Correct 84 ms 130388 KB Output is correct
10 Correct 83 ms 130380 KB Output is correct
11 Correct 71 ms 130432 KB Output is correct
12 Correct 76 ms 130380 KB Output is correct
13 Correct 72 ms 130456 KB Output is correct
14 Correct 69 ms 129988 KB Output is correct
15 Correct 65 ms 129932 KB Output is correct
16 Correct 73 ms 130368 KB Output is correct
17 Correct 76 ms 130508 KB Output is correct
18 Correct 71 ms 130384 KB Output is correct
19 Correct 75 ms 130016 KB Output is correct
20 Correct 80 ms 130488 KB Output is correct
21 Correct 77 ms 130480 KB Output is correct
22 Correct 71 ms 130476 KB Output is correct
23 Correct 61 ms 129996 KB Output is correct
24 Correct 67 ms 130124 KB Output is correct
25 Correct 87 ms 130468 KB Output is correct
26 Correct 67 ms 130284 KB Output is correct
27 Correct 79 ms 130476 KB Output is correct
28 Correct 65 ms 130004 KB Output is correct
29 Correct 75 ms 130508 KB Output is correct
30 Correct 85 ms 130508 KB Output is correct
31 Correct 89 ms 130500 KB Output is correct
32 Correct 89 ms 130380 KB Output is correct
33 Correct 71 ms 130432 KB Output is correct
34 Correct 75 ms 130380 KB Output is correct
35 Correct 77 ms 130424 KB Output is correct
36 Correct 80 ms 130428 KB Output is correct
37 Correct 82 ms 130388 KB Output is correct
38 Correct 684 ms 141828 KB Output is correct
39 Correct 1651 ms 340068 KB Output is correct
40 Correct 635 ms 143356 KB Output is correct
41 Correct 700 ms 142644 KB Output is correct
42 Correct 620 ms 142892 KB Output is correct
43 Correct 796 ms 142440 KB Output is correct
44 Correct 129 ms 132336 KB Output is correct
45 Correct 1313 ms 335684 KB Output is correct
46 Correct 1318 ms 335712 KB Output is correct
47 Correct 1796 ms 334576 KB Output is correct
48 Correct 1609 ms 334576 KB Output is correct
49 Correct 1146 ms 338640 KB Output is correct
50 Correct 1283 ms 338740 KB Output is correct
51 Correct 1444 ms 337164 KB Output is correct
52 Correct 1605 ms 337616 KB Output is correct
53 Correct 183 ms 144464 KB Output is correct
54 Correct 1407 ms 335728 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 129948 KB Output is correct
2 Correct 69 ms 130000 KB Output is correct
3 Correct 73 ms 130032 KB Output is correct
4 Correct 81 ms 129936 KB Output is correct
5 Correct 132 ms 130176 KB Output is correct
6 Correct 92 ms 130452 KB Output is correct
7 Correct 74 ms 130448 KB Output is correct
8 Correct 84 ms 130016 KB Output is correct
9 Correct 83 ms 129900 KB Output is correct
10 Correct 84 ms 130204 KB Output is correct
11 Correct 84 ms 129944 KB Output is correct
12 Correct 83 ms 130440 KB Output is correct
13 Correct 203 ms 130816 KB Output is correct
14 Correct 357 ms 131216 KB Output is correct
15 Correct 272 ms 130976 KB Output is correct
16 Correct 1363 ms 339216 KB Output is correct
17 Correct 1336 ms 351620 KB Output is correct
18 Correct 1668 ms 361452 KB Output is correct
19 Correct 1585 ms 339044 KB Output is correct
20 Correct 1373 ms 339848 KB Output is correct
21 Correct 1523 ms 339416 KB Output is correct
22 Correct 1246 ms 351772 KB Output is correct
23 Correct 1196 ms 351752 KB Output is correct
24 Correct 1274 ms 350852 KB Output is correct
25 Correct 1283 ms 351876 KB Output is correct
26 Correct 1302 ms 352020 KB Output is correct
27 Correct 1184 ms 353148 KB Output is correct
28 Correct 1175 ms 354328 KB Output is correct
29 Correct 1129 ms 354420 KB Output is correct
30 Correct 1476 ms 344412 KB Output is correct
31 Correct 1478 ms 344296 KB Output is correct
32 Correct 1221 ms 348560 KB Output is correct
33 Correct 1118 ms 348492 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 129948 KB Output is correct
2 Correct 59 ms 129916 KB Output is correct
3 Correct 66 ms 130072 KB Output is correct
4 Correct 174 ms 130596 KB Output is correct
5 Correct 264 ms 130888 KB Output is correct
6 Correct 80 ms 130452 KB Output is correct
7 Correct 81 ms 130472 KB Output is correct
8 Correct 73 ms 130408 KB Output is correct
9 Correct 594 ms 142020 KB Output is correct
10 Correct 1483 ms 340228 KB Output is correct
11 Correct 102 ms 130252 KB Output is correct
12 Correct 309 ms 131224 KB Output is correct
13 Correct 1809 ms 346268 KB Output is correct
14 Correct 1298 ms 346280 KB Output is correct
15 Correct 1517 ms 348096 KB Output is correct
16 Correct 1869 ms 360880 KB Output is correct
17 Correct 1738 ms 349924 KB Output is correct
18 Correct 1776 ms 350312 KB Output is correct
19 Correct 1804 ms 349872 KB Output is correct
20 Correct 1665 ms 350116 KB Output is correct
21 Correct 1322 ms 349380 KB Output is correct
22 Correct 1506 ms 345208 KB Output is correct
23 Correct 71 ms 129996 KB Output is correct
24 Correct 67 ms 129900 KB Output is correct
25 Correct 78 ms 130484 KB Output is correct
26 Correct 78 ms 130392 KB Output is correct
27 Correct 79 ms 130380 KB Output is correct
28 Correct 80 ms 130396 KB Output is correct
29 Correct 82 ms 130676 KB Output is correct
30 Correct 87 ms 130484 KB Output is correct
31 Correct 84 ms 130388 KB Output is correct
32 Correct 83 ms 130380 KB Output is correct
33 Correct 71 ms 130432 KB Output is correct
34 Correct 76 ms 130380 KB Output is correct
35 Correct 72 ms 130456 KB Output is correct
36 Correct 69 ms 129988 KB Output is correct
37 Correct 65 ms 129932 KB Output is correct
38 Correct 73 ms 130368 KB Output is correct
39 Correct 76 ms 130508 KB Output is correct
40 Correct 71 ms 130384 KB Output is correct
41 Correct 75 ms 130016 KB Output is correct
42 Correct 80 ms 130488 KB Output is correct
43 Correct 77 ms 130480 KB Output is correct
44 Correct 71 ms 130476 KB Output is correct
45 Correct 61 ms 129996 KB Output is correct
46 Correct 67 ms 130124 KB Output is correct
47 Correct 87 ms 130468 KB Output is correct
48 Correct 67 ms 130284 KB Output is correct
49 Correct 79 ms 130476 KB Output is correct
50 Correct 65 ms 130004 KB Output is correct
51 Correct 75 ms 130508 KB Output is correct
52 Correct 85 ms 130508 KB Output is correct
53 Correct 89 ms 130500 KB Output is correct
54 Correct 89 ms 130380 KB Output is correct
55 Correct 71 ms 130432 KB Output is correct
56 Correct 75 ms 130380 KB Output is correct
57 Correct 77 ms 130424 KB Output is correct
58 Correct 80 ms 130428 KB Output is correct
59 Correct 82 ms 130388 KB Output is correct
60 Correct 684 ms 141828 KB Output is correct
61 Correct 1651 ms 340068 KB Output is correct
62 Correct 635 ms 143356 KB Output is correct
63 Correct 700 ms 142644 KB Output is correct
64 Correct 620 ms 142892 KB Output is correct
65 Correct 796 ms 142440 KB Output is correct
66 Correct 129 ms 132336 KB Output is correct
67 Correct 1313 ms 335684 KB Output is correct
68 Correct 1318 ms 335712 KB Output is correct
69 Correct 1796 ms 334576 KB Output is correct
70 Correct 1609 ms 334576 KB Output is correct
71 Correct 1146 ms 338640 KB Output is correct
72 Correct 1283 ms 338740 KB Output is correct
73 Correct 1444 ms 337164 KB Output is correct
74 Correct 1605 ms 337616 KB Output is correct
75 Correct 183 ms 144464 KB Output is correct
76 Correct 1407 ms 335728 KB Output is correct
77 Correct 74 ms 129948 KB Output is correct
78 Correct 69 ms 130000 KB Output is correct
79 Correct 73 ms 130032 KB Output is correct
80 Correct 81 ms 129936 KB Output is correct
81 Correct 132 ms 130176 KB Output is correct
82 Correct 92 ms 130452 KB Output is correct
83 Correct 74 ms 130448 KB Output is correct
84 Correct 84 ms 130016 KB Output is correct
85 Correct 83 ms 129900 KB Output is correct
86 Correct 84 ms 130204 KB Output is correct
87 Correct 84 ms 129944 KB Output is correct
88 Correct 83 ms 130440 KB Output is correct
89 Correct 203 ms 130816 KB Output is correct
90 Correct 357 ms 131216 KB Output is correct
91 Correct 272 ms 130976 KB Output is correct
92 Correct 1363 ms 339216 KB Output is correct
93 Correct 1336 ms 351620 KB Output is correct
94 Correct 1668 ms 361452 KB Output is correct
95 Correct 1585 ms 339044 KB Output is correct
96 Correct 1373 ms 339848 KB Output is correct
97 Correct 1523 ms 339416 KB Output is correct
98 Correct 1246 ms 351772 KB Output is correct
99 Correct 1196 ms 351752 KB Output is correct
100 Correct 1274 ms 350852 KB Output is correct
101 Correct 1283 ms 351876 KB Output is correct
102 Correct 1302 ms 352020 KB Output is correct
103 Correct 1184 ms 353148 KB Output is correct
104 Correct 1175 ms 354328 KB Output is correct
105 Correct 1129 ms 354420 KB Output is correct
106 Correct 1476 ms 344412 KB Output is correct
107 Correct 1478 ms 344296 KB Output is correct
108 Correct 1221 ms 348560 KB Output is correct
109 Correct 1118 ms 348492 KB Output is correct
110 Correct 329 ms 131596 KB Output is correct
111 Correct 273 ms 130956 KB Output is correct
112 Correct 1853 ms 349692 KB Output is correct
113 Correct 2367 ms 339260 KB Output is correct
114 Correct 1657 ms 350036 KB Output is correct
115 Correct 1212 ms 336128 KB Output is correct
116 Correct 1374 ms 345420 KB Output is correct
117 Correct 1521 ms 362416 KB Output is correct
118 Correct 1199 ms 335812 KB Output is correct
119 Correct 1421 ms 335808 KB Output is correct
120 Correct 158 ms 148032 KB Output is correct
121 Correct 1600 ms 350124 KB Output is correct
122 Correct 1594 ms 346808 KB Output is correct
123 Correct 2168 ms 341476 KB Output is correct
124 Correct 1716 ms 341296 KB Output is correct
125 Correct 2164 ms 341144 KB Output is correct
126 Correct 2164 ms 362228 KB Output is correct
127 Correct 2100 ms 351496 KB Output is correct
128 Correct 1812 ms 351380 KB Output is correct
129 Correct 2003 ms 351752 KB Output is correct
130 Correct 1782 ms 351720 KB Output is correct