oj.uz

Submission #581645

# Submission time Handle Problem Language Result Execution time Memory
581645 2022-06-23T00:52:39 Z Lobo Jail (JOI22_jail) C++17
5 / 100
 1786 ms 334852 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[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 <= 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*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 = 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 56 ms 115916 KB Output is correct
2 Correct 54 ms 115916 KB Output is correct
3 Correct 52 ms 115800 KB Output is correct
4 Correct 148 ms 116084 KB Output is correct
5 Correct 250 ms 116120 KB Output is correct
6 Correct 72 ms 116240 KB Output is correct
7 Correct 73 ms 116280 KB Output is correct
8 Correct 68 ms 116300 KB Output is correct
9 Correct 587 ms 126376 KB Output is correct
10 Correct 1448 ms 316368 KB Output is correct
11 Correct 101 ms 115960 KB Output is correct
12 Correct 298 ms 116156 KB Output is correct
13 Correct 1657 ms 321276 KB Output is correct
14 Correct 1403 ms 321460 KB Output is correct
15 Correct 1355 ms 323448 KB Output is correct
16 Correct 1786 ms 334852 KB Output is correct
17 Correct 1573 ms 325064 KB Output is correct
18 Correct 1739 ms 324632 KB Output is correct
19 Correct 1639 ms 325016 KB Output is correct
20 Correct 1614 ms 325048 KB Output is correct
21 Correct 1534 ms 324536 KB Output is correct
22 Correct 1448 ms 320288 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 115920 KB Output is correct
2 Correct 63 ms 115900 KB Output is correct
3 Correct 74 ms 116256 KB Output is correct
4 Incorrect 75 ms 116232 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 115920 KB Output is correct
2 Correct 63 ms 115900 KB Output is correct
3 Correct 74 ms 116256 KB Output is correct
4 Incorrect 75 ms 116232 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 115920 KB Output is correct
2 Correct 63 ms 115900 KB Output is correct
3 Correct 74 ms 116256 KB Output is correct
4 Incorrect 75 ms 116232 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 115920 KB Output is correct
2 Correct 63 ms 115900 KB Output is correct
3 Correct 74 ms 116256 KB Output is correct
4 Incorrect 75 ms 116232 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 115916 KB Output is correct
2 Incorrect 70 ms 115808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 115916 KB Output is correct
2 Correct 54 ms 115916 KB Output is correct
3 Correct 52 ms 115800 KB Output is correct
4 Correct 148 ms 116084 KB Output is correct
5 Correct 250 ms 116120 KB Output is correct
6 Correct 72 ms 116240 KB Output is correct
7 Correct 73 ms 116280 KB Output is correct
8 Correct 68 ms 116300 KB Output is correct
9 Correct 587 ms 126376 KB Output is correct
10 Correct 1448 ms 316368 KB Output is correct
11 Correct 101 ms 115960 KB Output is correct
12 Correct 298 ms 116156 KB Output is correct
13 Correct 1657 ms 321276 KB Output is correct
14 Correct 1403 ms 321460 KB Output is correct
15 Correct 1355 ms 323448 KB Output is correct
16 Correct 1786 ms 334852 KB Output is correct
17 Correct 1573 ms 325064 KB Output is correct
18 Correct 1739 ms 324632 KB Output is correct
19 Correct 1639 ms 325016 KB Output is correct
20 Correct 1614 ms 325048 KB Output is correct
21 Correct 1534 ms 324536 KB Output is correct
22 Correct 1448 ms 320288 KB Output is correct
23 Correct 59 ms 115920 KB Output is correct
24 Correct 63 ms 115900 KB Output is correct
25 Correct 74 ms 116256 KB Output is correct
26 Incorrect 75 ms 116232 KB Output isn't correct
27 Halted 0 ms 0 KB -