oj.uz

Submission #580364

# Submission time Handle Problem Language Result Execution time Memory
580364 2022-06-21T07:14:30 Z balbit Jail (JOI22_jail) C++14
60 / 100
 737 ms 121304 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 120000+5;


vector<int> tree[maxn];
int dep[maxn];
int fa[18][maxn];
int tos[18][maxn], toe[18][maxn];
int nxt[maxn];
int st[maxn], en[maxn]; // starting or ending???
vector<int> g[maxn * 20];

int IT = 0;

void dfs(int v, int p) {
    tos[0][v] = IT++; toe[0][v] = IT++;
    if (st[v] != -1) {
        g[tos[0][v]].pb(st[v]);
    }
    if (en[v] != -1) {
        g[en[v]].pb(toe[0][v]);
    }
    if (st[v]!=-1 || en[v]!=-1) {
        nxt[v] = v;

    }else{
        nxt[v] = p == -1? -1 : nxt[p];
    }
    bug(v, nxt[v]);
    for (int u : tree[v]) {
        if (u == p) continue;
        dep[u] = dep[v] + 1;
        fa[0][u] = v;
        dfs(u,v);
    }
}

int snode[maxn], enode[maxn];
void CLR(int n){
    REP(i,n) {
        tree[i].clear(); dep[i] = 0;
        st[i] = en[i] = -1;
        nxt[i] = -1;
    }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a,b);
    int need = dep[a] - dep[b];
    REP(k, 18) if (need & (1<<k)) a = fa[k][a];
    assert(dep[a] == dep[b]);
    for (int j = 17; j>=0; --j) {
        if (fa[j][a] != fa[j][b]) {
            a = fa[j][a]; b = fa[j][b];
        }
    }
    if (a != b) return fa[0][a];
    return a;
}


int indeg[maxn*30];

int kth(int a, int k) {
    REP(j,18) {
        if (k & (1<<j)) a = fa[j][a];
    }
    return a;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);

    int T; cin>>T;
    while (T--) {
        int n; cin>>n;
        CLR(n);

        REP(i,n-1) {
            int a,b; cin>>a>>b; --a; --b;
            tree[a].pb(b); tree[b].pb(a);
        }


        int q; cin>>q;
        REP(i,q) {
            cin>>snode[i]>>enode[i]; --snode[i]; --enode[i];
            st[snode[i]] = i; en[enode[i]] = i;
        }

        IT = q;
        REP(i,q + n * 18) g[i].clear();

        dfs(0,-1);

        REP1(j, 18-1) {
            REP(i,n) {
                fa[j][i] = fa[j-1][fa[j-1][i]];
//                int F = fa[j][i];
                if (dep[i] + 1 - (1<<j) >= 0) {
                    tos[j][i] = IT++;
                    g[tos[j][i]].pb(tos[j-1][i]);
                    g[tos[j][i]].pb(tos[j-1][fa[j-1][i]]);

                    toe[j][i] = IT++;
                    g[toe[j-1][i]].pb(toe[j][i]);
                    g[toe[j-1][fa[j-1][i]]].pb(toe[j][i]);
                }
            }
        }


        REP(i,q) {
//            if (i) continue;
            int a = snode[i], b = enode[i];
            int c = lca(a,b);
//            bool yo = 0;

            for (int go : {a,b}) {

                // do s
                {
                    int v = go;
                    if (st[v] == i && st[c] == i) goto bruh;
                    if (st[v] == i) v = fa[0][v];
                    if (dep[v] < dep[c]) goto bruh;
                    if (st[c] == i) {
                        int ho = dep[v] - dep[c] - 1;
                        bug(ho);
                        c = kth(v, ho);
                    }
                    if (st[v] != i && dep[v] >= dep[c]) {
                        int gap = dep[v] - dep[c] + 1;
                        int L = __lg(gap);
                        bug(v,c,gap,L);
                        g[i].pb(tos[L][v]);
                        int nh = -dep[c] + dep[v] + 1 - (1<<L);
                        bug(kth(v, nh), L);
                        g[i].pb(tos[L][kth(v,nh)]);
                    }
                }
                bruh:;
                {
                    int v = go;
                    if (en[v] == i && en[c] == i) goto bruhh;
                    if (en[v] == i) v = fa[0][v];
                    if (dep[v] < dep[c]) goto bruhh;
                    if (en[c] == i) {
                        int ho = dep[v] - dep[c] - 1;
                        bug(ho);
                        c = kth(v, ho);
                    }
                    if (en[v] != i && dep[v] >= dep[c]) {
                        int gap = dep[v] - dep[c] + 1;
                        int L = __lg(gap);
                        bug(v,c,gap,L);
                        g[toe[L][v]].pb(i);
                        int nh = -dep[c] + dep[v] + 1 - (1<<L);
                        bug(kth(v, nh), L);
                        g[toe[L][kth(v,nh)]].pb(i);
                    }
                }
                bruhh:;

            }
        }

        bug("out");

        REP(i,IT) {
            indeg[i] = 0;
        }
        REP(i,IT) {
            for (int u : g[i]) {
                ++indeg[u];
            }
        }
        queue<int> qq;
        REP(i,IT) {
            if (indeg[i] == 0) {
                qq.push(i);
            }
        }
        int done = 0;
        while (!qq.empty() ){
            int v = qq.front(); qq.pop();
            ++done;
            bug(v, done);
            for (int u : g[v]) {
                if (--indeg[u] == 0) {
                    qq.push(u);
                }
            }
        }

        bug(done, IT);
        cout<<(done==IT?"Yes":"No")<<endl;

    }


}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 59604 KB Output is correct
2 Correct 30 ms 59624 KB Output is correct
3 Correct 29 ms 59656 KB Output is correct
4 Correct 58 ms 59776 KB Output is correct
5 Correct 97 ms 59660 KB Output is correct
6 Correct 35 ms 59868 KB Output is correct
7 Correct 35 ms 59860 KB Output is correct
8 Correct 34 ms 59860 KB Output is correct
9 Incorrect 251 ms 72912 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 59652 KB Output is correct
2 Correct 37 ms 59592 KB Output is correct
3 Correct 36 ms 59752 KB Output is correct
4 Correct 36 ms 59732 KB Output is correct
5 Correct 33 ms 59808 KB Output is correct
6 Correct 34 ms 59732 KB Output is correct
7 Correct 32 ms 59800 KB Output is correct
8 Correct 32 ms 59748 KB Output is correct
9 Correct 33 ms 59820 KB Output is correct
10 Correct 32 ms 59712 KB Output is correct
11 Correct 33 ms 59796 KB Output is correct
12 Correct 38 ms 59660 KB Output is correct
13 Correct 39 ms 59688 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 59652 KB Output is correct
2 Correct 37 ms 59592 KB Output is correct
3 Correct 36 ms 59752 KB Output is correct
4 Correct 36 ms 59732 KB Output is correct
5 Correct 33 ms 59808 KB Output is correct
6 Correct 34 ms 59732 KB Output is correct
7 Correct 32 ms 59800 KB Output is correct
8 Correct 32 ms 59748 KB Output is correct
9 Correct 33 ms 59820 KB Output is correct
10 Correct 32 ms 59712 KB Output is correct
11 Correct 33 ms 59796 KB Output is correct
12 Correct 38 ms 59660 KB Output is correct
13 Correct 39 ms 59688 KB Output is correct
14 Correct 35 ms 59576 KB Output is correct
15 Correct 32 ms 59596 KB Output is correct
16 Correct 32 ms 59892 KB Output is correct
17 Correct 30 ms 59732 KB Output is correct
18 Correct 32 ms 59800 KB Output is correct
19 Correct 30 ms 59616 KB Output is correct
20 Correct 32 ms 59756 KB Output is correct
21 Correct 36 ms 59772 KB Output is correct
22 Correct 34 ms 59860 KB Output is correct
23 Correct 32 ms 59640 KB Output is correct
24 Correct 29 ms 59580 KB Output is correct
25 Correct 31 ms 59724 KB Output is correct
26 Correct 29 ms 59732 KB Output is correct
27 Correct 32 ms 59736 KB Output is correct
28 Correct 36 ms 59612 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 59652 KB Output is correct
2 Correct 37 ms 59592 KB Output is correct
3 Correct 36 ms 59752 KB Output is correct
4 Correct 36 ms 59732 KB Output is correct
5 Correct 33 ms 59808 KB Output is correct
6 Correct 34 ms 59732 KB Output is correct
7 Correct 32 ms 59800 KB Output is correct
8 Correct 32 ms 59748 KB Output is correct
9 Correct 33 ms 59820 KB Output is correct
10 Correct 32 ms 59712 KB Output is correct
11 Correct 33 ms 59796 KB Output is correct
12 Correct 38 ms 59660 KB Output is correct
13 Correct 39 ms 59688 KB Output is correct
14 Correct 35 ms 59576 KB Output is correct
15 Correct 32 ms 59596 KB Output is correct
16 Correct 32 ms 59892 KB Output is correct
17 Correct 30 ms 59732 KB Output is correct
18 Correct 32 ms 59800 KB Output is correct
19 Correct 30 ms 59616 KB Output is correct
20 Correct 32 ms 59756 KB Output is correct
21 Correct 36 ms 59772 KB Output is correct
22 Correct 34 ms 59860 KB Output is correct
23 Correct 32 ms 59640 KB Output is correct
24 Correct 29 ms 59580 KB Output is correct
25 Correct 31 ms 59724 KB Output is correct
26 Correct 29 ms 59732 KB Output is correct
27 Correct 32 ms 59736 KB Output is correct
28 Correct 36 ms 59612 KB Output is correct
29 Correct 36 ms 59848 KB Output is correct
30 Correct 34 ms 59780 KB Output is correct
31 Correct 42 ms 59892 KB Output is correct
32 Correct 38 ms 59752 KB Output is correct
33 Correct 33 ms 59828 KB Output is correct
34 Correct 32 ms 59644 KB Output is correct
35 Correct 31 ms 59740 KB Output is correct
36 Correct 33 ms 59660 KB Output is correct
37 Correct 33 ms 59688 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 59652 KB Output is correct
2 Correct 37 ms 59592 KB Output is correct
3 Correct 36 ms 59752 KB Output is correct
4 Correct 36 ms 59732 KB Output is correct
5 Correct 33 ms 59808 KB Output is correct
6 Correct 34 ms 59732 KB Output is correct
7 Correct 32 ms 59800 KB Output is correct
8 Correct 32 ms 59748 KB Output is correct
9 Correct 33 ms 59820 KB Output is correct
10 Correct 32 ms 59712 KB Output is correct
11 Correct 33 ms 59796 KB Output is correct
12 Correct 38 ms 59660 KB Output is correct
13 Correct 39 ms 59688 KB Output is correct
14 Correct 35 ms 59576 KB Output is correct
15 Correct 32 ms 59596 KB Output is correct
16 Correct 32 ms 59892 KB Output is correct
17 Correct 30 ms 59732 KB Output is correct
18 Correct 32 ms 59800 KB Output is correct
19 Correct 30 ms 59616 KB Output is correct
20 Correct 32 ms 59756 KB Output is correct
21 Correct 36 ms 59772 KB Output is correct
22 Correct 34 ms 59860 KB Output is correct
23 Correct 32 ms 59640 KB Output is correct
24 Correct 29 ms 59580 KB Output is correct
25 Correct 31 ms 59724 KB Output is correct
26 Correct 29 ms 59732 KB Output is correct
27 Correct 32 ms 59736 KB Output is correct
28 Correct 36 ms 59612 KB Output is correct
29 Correct 36 ms 59848 KB Output is correct
30 Correct 34 ms 59780 KB Output is correct
31 Correct 42 ms 59892 KB Output is correct
32 Correct 38 ms 59752 KB Output is correct
33 Correct 33 ms 59828 KB Output is correct
34 Correct 32 ms 59644 KB Output is correct
35 Correct 31 ms 59740 KB Output is correct
36 Correct 33 ms 59660 KB Output is correct
37 Correct 33 ms 59688 KB Output is correct
38 Incorrect 254 ms 72912 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 59604 KB Output is correct
2 Correct 32 ms 59648 KB Output is correct
3 Correct 34 ms 59668 KB Output is correct
4 Correct 31 ms 59648 KB Output is correct
5 Correct 42 ms 59592 KB Output is correct
6 Correct 32 ms 59628 KB Output is correct
7 Correct 31 ms 59688 KB Output is correct
8 Correct 32 ms 59684 KB Output is correct
9 Correct 33 ms 59588 KB Output is correct
10 Correct 35 ms 59596 KB Output is correct
11 Correct 34 ms 59604 KB Output is correct
12 Correct 32 ms 59724 KB Output is correct
13 Correct 65 ms 59868 KB Output is correct
14 Correct 93 ms 59848 KB Output is correct
15 Correct 86 ms 59848 KB Output is correct
16 Correct 365 ms 106668 KB Output is correct
17 Correct 498 ms 113460 KB Output is correct
18 Correct 737 ms 121304 KB Output is correct
19 Correct 413 ms 108384 KB Output is correct
20 Correct 409 ms 107836 KB Output is correct
21 Correct 414 ms 107900 KB Output is correct
22 Correct 419 ms 112828 KB Output is correct
23 Correct 396 ms 112928 KB Output is correct
24 Correct 485 ms 113012 KB Output is correct
25 Correct 448 ms 113428 KB Output is correct
26 Correct 472 ms 113476 KB Output is correct
27 Correct 635 ms 101308 KB Output is correct
28 Correct 546 ms 101308 KB Output is correct
29 Correct 528 ms 101264 KB Output is correct
30 Correct 513 ms 98896 KB Output is correct
31 Correct 470 ms 98984 KB Output is correct
32 Correct 525 ms 98956 KB Output is correct
33 Correct 404 ms 98900 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 59604 KB Output is correct
2 Correct 30 ms 59624 KB Output is correct
3 Correct 29 ms 59656 KB Output is correct
4 Correct 58 ms 59776 KB Output is correct
5 Correct 97 ms 59660 KB Output is correct
6 Correct 35 ms 59868 KB Output is correct
7 Correct 35 ms 59860 KB Output is correct
8 Correct 34 ms 59860 KB Output is correct
9 Incorrect 251 ms 72912 KB Output isn't correct
10 Halted 0 ms 0 KB -