oj.uz

Submission #581649

# Submission time Handle Problem Language Result Execution time Memory
581649 2022-06-23T00:54:43 Z Lobo Jail (JOI22_jail) C++17
21 / 100
 286 ms 116428 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[40*maxn], h[maxn], s[maxn], t[maxn], up[maxn][20], dw[maxn][20];
vector<int> g[maxn], gts[40*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*40; i++) {
        gts[i].clear();
        gr[i] = 0;
    }
    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;
}

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 115920 KB Output is correct
2 Correct 61 ms 115916 KB Output is correct
3 Correct 61 ms 115828 KB Output is correct
4 Correct 156 ms 116136 KB Output is correct
5 Correct 286 ms 116272 KB Output is correct
6 Correct 76 ms 116428 KB Output is correct
7 Correct 64 ms 116340 KB Output is correct
8 Incorrect 77 ms 116384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 115816 KB Output is correct
2 Correct 58 ms 115884 KB Output is correct
3 Correct 75 ms 116356 KB Output is correct
4 Correct 77 ms 116312 KB Output is correct
5 Correct 71 ms 116300 KB Output is correct
6 Correct 63 ms 116304 KB Output is correct
7 Correct 63 ms 116288 KB Output is correct
8 Correct 69 ms 116264 KB Output is correct
9 Correct 68 ms 116336 KB Output is correct
10 Correct 71 ms 116364 KB Output is correct
11 Correct 70 ms 116260 KB Output is correct
12 Correct 57 ms 116308 KB Output is correct
13 Correct 57 ms 116312 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 115816 KB Output is correct
2 Correct 58 ms 115884 KB Output is correct
3 Correct 75 ms 116356 KB Output is correct
4 Correct 77 ms 116312 KB Output is correct
5 Correct 71 ms 116300 KB Output is correct
6 Correct 63 ms 116304 KB Output is correct
7 Correct 63 ms 116288 KB Output is correct
8 Correct 69 ms 116264 KB Output is correct
9 Correct 68 ms 116336 KB Output is correct
10 Correct 71 ms 116364 KB Output is correct
11 Correct 70 ms 116260 KB Output is correct
12 Correct 57 ms 116308 KB Output is correct
13 Correct 57 ms 116312 KB Output is correct
14 Correct 52 ms 115796 KB Output is correct
15 Correct 53 ms 115920 KB Output is correct
16 Correct 82 ms 116360 KB Output is correct
17 Correct 66 ms 116328 KB Output is correct
18 Correct 62 ms 116356 KB Output is correct
19 Correct 55 ms 115892 KB Output is correct
20 Correct 67 ms 116340 KB Output is correct
21 Correct 72 ms 116364 KB Output is correct
22 Correct 70 ms 116316 KB Output is correct
23 Correct 63 ms 115852 KB Output is correct
24 Correct 52 ms 116124 KB Output is correct
25 Correct 62 ms 116240 KB Output is correct
26 Correct 68 ms 116268 KB Output is correct
27 Correct 67 ms 116280 KB Output is correct
28 Correct 54 ms 115832 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 115816 KB Output is correct
2 Correct 58 ms 115884 KB Output is correct
3 Correct 75 ms 116356 KB Output is correct
4 Correct 77 ms 116312 KB Output is correct
5 Correct 71 ms 116300 KB Output is correct
6 Correct 63 ms 116304 KB Output is correct
7 Correct 63 ms 116288 KB Output is correct
8 Correct 69 ms 116264 KB Output is correct
9 Correct 68 ms 116336 KB Output is correct
10 Correct 71 ms 116364 KB Output is correct
11 Correct 70 ms 116260 KB Output is correct
12 Correct 57 ms 116308 KB Output is correct
13 Correct 57 ms 116312 KB Output is correct
14 Correct 52 ms 115796 KB Output is correct
15 Correct 53 ms 115920 KB Output is correct
16 Correct 82 ms 116360 KB Output is correct
17 Correct 66 ms 116328 KB Output is correct
18 Correct 62 ms 116356 KB Output is correct
19 Correct 55 ms 115892 KB Output is correct
20 Correct 67 ms 116340 KB Output is correct
21 Correct 72 ms 116364 KB Output is correct
22 Correct 70 ms 116316 KB Output is correct
23 Correct 63 ms 115852 KB Output is correct
24 Correct 52 ms 116124 KB Output is correct
25 Correct 62 ms 116240 KB Output is correct
26 Correct 68 ms 116268 KB Output is correct
27 Correct 67 ms 116280 KB Output is correct
28 Correct 54 ms 115832 KB Output is correct
29 Incorrect 70 ms 116364 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 115816 KB Output is correct
2 Correct 58 ms 115884 KB Output is correct
3 Correct 75 ms 116356 KB Output is correct
4 Correct 77 ms 116312 KB Output is correct
5 Correct 71 ms 116300 KB Output is correct
6 Correct 63 ms 116304 KB Output is correct
7 Correct 63 ms 116288 KB Output is correct
8 Correct 69 ms 116264 KB Output is correct
9 Correct 68 ms 116336 KB Output is correct
10 Correct 71 ms 116364 KB Output is correct
11 Correct 70 ms 116260 KB Output is correct
12 Correct 57 ms 116308 KB Output is correct
13 Correct 57 ms 116312 KB Output is correct
14 Correct 52 ms 115796 KB Output is correct
15 Correct 53 ms 115920 KB Output is correct
16 Correct 82 ms 116360 KB Output is correct
17 Correct 66 ms 116328 KB Output is correct
18 Correct 62 ms 116356 KB Output is correct
19 Correct 55 ms 115892 KB Output is correct
20 Correct 67 ms 116340 KB Output is correct
21 Correct 72 ms 116364 KB Output is correct
22 Correct 70 ms 116316 KB Output is correct
23 Correct 63 ms 115852 KB Output is correct
24 Correct 52 ms 116124 KB Output is correct
25 Correct 62 ms 116240 KB Output is correct
26 Correct 68 ms 116268 KB Output is correct
27 Correct 67 ms 116280 KB Output is correct
28 Correct 54 ms 115832 KB Output is correct
29 Incorrect 70 ms 116364 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 115896 KB Output is correct
2 Correct 69 ms 115896 KB Output is correct
3 Correct 68 ms 115916 KB Output is correct
4 Correct 54 ms 115780 KB Output is correct
5 Incorrect 105 ms 116040 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 115920 KB Output is correct
2 Correct 61 ms 115916 KB Output is correct
3 Correct 61 ms 115828 KB Output is correct
4 Correct 156 ms 116136 KB Output is correct
5 Correct 286 ms 116272 KB Output is correct
6 Correct 76 ms 116428 KB Output is correct
7 Correct 64 ms 116340 KB Output is correct
8 Incorrect 77 ms 116384 KB Output isn't correct
9 Halted 0 ms 0 KB -