oj.uz

Submission #581630

# Submission time Handle Problem Language Result Execution time Memory
581630 2022-06-22T23:44:23 Z Lobo Jail (JOI22_jail) C++17
5 / 100
 1759 ms 331708 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 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[39*maxn], h[maxn], s[maxn], t[maxn], up[maxn][20], dw[maxn][20];
vector<int> g[maxn], gts[39*maxn];
int cnt = 0;

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

    //cria up
    up[u][0] = ++cnt;
    for(int i = 1; i <= 18; 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 <= 18; 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 = 20; i >= 0; i--) {
        if(h[pp[u][i]] >= h[v]) {
            u = pp[u][i];
        }
    }
    if(u == v) return u;
    for(int i = 20; 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*50; 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 = 18; 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 = 18; 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 113104 KB Output is correct
2 Correct 53 ms 113088 KB Output is correct
3 Correct 54 ms 112972 KB Output is correct
4 Correct 143 ms 113228 KB Output is correct
5 Correct 267 ms 113264 KB Output is correct
6 Correct 62 ms 113484 KB Output is correct
7 Correct 61 ms 113412 KB Output is correct
8 Correct 63 ms 113484 KB Output is correct
9 Correct 601 ms 123680 KB Output is correct
10 Correct 1488 ms 312856 KB Output is correct
11 Correct 93 ms 113124 KB Output is correct
12 Correct 279 ms 113436 KB Output is correct
13 Correct 1676 ms 318132 KB Output is correct
14 Correct 1335 ms 318064 KB Output is correct
15 Correct 1401 ms 319964 KB Output is correct
16 Correct 1759 ms 331708 KB Output is correct
17 Correct 1615 ms 321744 KB Output is correct
18 Correct 1618 ms 321236 KB Output is correct
19 Correct 1671 ms 321804 KB Output is correct
20 Correct 1433 ms 321780 KB Output is correct
21 Correct 1174 ms 321344 KB Output is correct
22 Correct 1371 ms 317024 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 112972 KB Output is correct
2 Correct 55 ms 113000 KB Output is correct
3 Correct 65 ms 113524 KB Output is correct
4 Incorrect 62 ms 113416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 112972 KB Output is correct
2 Correct 55 ms 113000 KB Output is correct
3 Correct 65 ms 113524 KB Output is correct
4 Incorrect 62 ms 113416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 112972 KB Output is correct
2 Correct 55 ms 113000 KB Output is correct
3 Correct 65 ms 113524 KB Output is correct
4 Incorrect 62 ms 113416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 112972 KB Output is correct
2 Correct 55 ms 113000 KB Output is correct
3 Correct 65 ms 113524 KB Output is correct
4 Incorrect 62 ms 113416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 112972 KB Output is correct
2 Incorrect 65 ms 112964 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 113104 KB Output is correct
2 Correct 53 ms 113088 KB Output is correct
3 Correct 54 ms 112972 KB Output is correct
4 Correct 143 ms 113228 KB Output is correct
5 Correct 267 ms 113264 KB Output is correct
6 Correct 62 ms 113484 KB Output is correct
7 Correct 61 ms 113412 KB Output is correct
8 Correct 63 ms 113484 KB Output is correct
9 Correct 601 ms 123680 KB Output is correct
10 Correct 1488 ms 312856 KB Output is correct
11 Correct 93 ms 113124 KB Output is correct
12 Correct 279 ms 113436 KB Output is correct
13 Correct 1676 ms 318132 KB Output is correct
14 Correct 1335 ms 318064 KB Output is correct
15 Correct 1401 ms 319964 KB Output is correct
16 Correct 1759 ms 331708 KB Output is correct
17 Correct 1615 ms 321744 KB Output is correct
18 Correct 1618 ms 321236 KB Output is correct
19 Correct 1671 ms 321804 KB Output is correct
20 Correct 1433 ms 321780 KB Output is correct
21 Correct 1174 ms 321344 KB Output is correct
22 Correct 1371 ms 317024 KB Output is correct
23 Correct 57 ms 112972 KB Output is correct
24 Correct 55 ms 113000 KB Output is correct
25 Correct 65 ms 113524 KB Output is correct
26 Incorrect 62 ms 113416 KB Output isn't correct
27 Halted 0 ms 0 KB -