oj.uz

Submission #580367

# Submission time Handle Problem Language Result Execution time Memory
580367 2022-06-21T07:15:54 Z balbit Jail (JOI22_jail) C++14
72 / 100
 834 ms 558028 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 * 36];

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 * 35) 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 58 ms 104712 KB Output is correct
2 Correct 53 ms 104744 KB Output is correct
3 Correct 56 ms 104628 KB Output is correct
4 Correct 86 ms 104756 KB Output is correct
5 Correct 126 ms 104848 KB Output is correct
6 Correct 58 ms 104876 KB Output is correct
7 Correct 54 ms 105048 KB Output is correct
8 Correct 59 ms 104964 KB Output is correct
9 Correct 224 ms 111416 KB Output is correct
10 Correct 536 ms 273028 KB Output is correct
11 Correct 65 ms 104780 KB Output is correct
12 Correct 136 ms 104908 KB Output is correct
13 Runtime error 699 ms 558028 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 104652 KB Output is correct
2 Correct 59 ms 104656 KB Output is correct
3 Correct 59 ms 104888 KB Output is correct
4 Correct 55 ms 104780 KB Output is correct
5 Correct 56 ms 104792 KB Output is correct
6 Correct 55 ms 104860 KB Output is correct
7 Correct 64 ms 104844 KB Output is correct
8 Correct 64 ms 104776 KB Output is correct
9 Correct 56 ms 104852 KB Output is correct
10 Correct 53 ms 104820 KB Output is correct
11 Correct 60 ms 104856 KB Output is correct
12 Correct 54 ms 104784 KB Output is correct
13 Correct 68 ms 104740 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 104652 KB Output is correct
2 Correct 59 ms 104656 KB Output is correct
3 Correct 59 ms 104888 KB Output is correct
4 Correct 55 ms 104780 KB Output is correct
5 Correct 56 ms 104792 KB Output is correct
6 Correct 55 ms 104860 KB Output is correct
7 Correct 64 ms 104844 KB Output is correct
8 Correct 64 ms 104776 KB Output is correct
9 Correct 56 ms 104852 KB Output is correct
10 Correct 53 ms 104820 KB Output is correct
11 Correct 60 ms 104856 KB Output is correct
12 Correct 54 ms 104784 KB Output is correct
13 Correct 68 ms 104740 KB Output is correct
14 Correct 54 ms 104632 KB Output is correct
15 Correct 53 ms 104656 KB Output is correct
16 Correct 56 ms 104944 KB Output is correct
17 Correct 55 ms 104848 KB Output is correct
18 Correct 54 ms 104932 KB Output is correct
19 Correct 54 ms 104652 KB Output is correct
20 Correct 67 ms 104876 KB Output is correct
21 Correct 58 ms 104932 KB Output is correct
22 Correct 52 ms 104856 KB Output is correct
23 Correct 50 ms 104652 KB Output is correct
24 Correct 56 ms 104704 KB Output is correct
25 Correct 58 ms 104960 KB Output is correct
26 Correct 55 ms 104808 KB Output is correct
27 Correct 60 ms 104812 KB Output is correct
28 Correct 51 ms 104696 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 104652 KB Output is correct
2 Correct 59 ms 104656 KB Output is correct
3 Correct 59 ms 104888 KB Output is correct
4 Correct 55 ms 104780 KB Output is correct
5 Correct 56 ms 104792 KB Output is correct
6 Correct 55 ms 104860 KB Output is correct
7 Correct 64 ms 104844 KB Output is correct
8 Correct 64 ms 104776 KB Output is correct
9 Correct 56 ms 104852 KB Output is correct
10 Correct 53 ms 104820 KB Output is correct
11 Correct 60 ms 104856 KB Output is correct
12 Correct 54 ms 104784 KB Output is correct
13 Correct 68 ms 104740 KB Output is correct
14 Correct 54 ms 104632 KB Output is correct
15 Correct 53 ms 104656 KB Output is correct
16 Correct 56 ms 104944 KB Output is correct
17 Correct 55 ms 104848 KB Output is correct
18 Correct 54 ms 104932 KB Output is correct
19 Correct 54 ms 104652 KB Output is correct
20 Correct 67 ms 104876 KB Output is correct
21 Correct 58 ms 104932 KB Output is correct
22 Correct 52 ms 104856 KB Output is correct
23 Correct 50 ms 104652 KB Output is correct
24 Correct 56 ms 104704 KB Output is correct
25 Correct 58 ms 104960 KB Output is correct
26 Correct 55 ms 104808 KB Output is correct
27 Correct 60 ms 104812 KB Output is correct
28 Correct 51 ms 104696 KB Output is correct
29 Correct 58 ms 104908 KB Output is correct
30 Correct 57 ms 104764 KB Output is correct
31 Correct 61 ms 104912 KB Output is correct
32 Correct 58 ms 104900 KB Output is correct
33 Correct 58 ms 104876 KB Output is correct
34 Correct 55 ms 104832 KB Output is correct
35 Correct 56 ms 104780 KB Output is correct
36 Correct 57 ms 104848 KB Output is correct
37 Correct 59 ms 104804 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 104652 KB Output is correct
2 Correct 59 ms 104656 KB Output is correct
3 Correct 59 ms 104888 KB Output is correct
4 Correct 55 ms 104780 KB Output is correct
5 Correct 56 ms 104792 KB Output is correct
6 Correct 55 ms 104860 KB Output is correct
7 Correct 64 ms 104844 KB Output is correct
8 Correct 64 ms 104776 KB Output is correct
9 Correct 56 ms 104852 KB Output is correct
10 Correct 53 ms 104820 KB Output is correct
11 Correct 60 ms 104856 KB Output is correct
12 Correct 54 ms 104784 KB Output is correct
13 Correct 68 ms 104740 KB Output is correct
14 Correct 54 ms 104632 KB Output is correct
15 Correct 53 ms 104656 KB Output is correct
16 Correct 56 ms 104944 KB Output is correct
17 Correct 55 ms 104848 KB Output is correct
18 Correct 54 ms 104932 KB Output is correct
19 Correct 54 ms 104652 KB Output is correct
20 Correct 67 ms 104876 KB Output is correct
21 Correct 58 ms 104932 KB Output is correct
22 Correct 52 ms 104856 KB Output is correct
23 Correct 50 ms 104652 KB Output is correct
24 Correct 56 ms 104704 KB Output is correct
25 Correct 58 ms 104960 KB Output is correct
26 Correct 55 ms 104808 KB Output is correct
27 Correct 60 ms 104812 KB Output is correct
28 Correct 51 ms 104696 KB Output is correct
29 Correct 58 ms 104908 KB Output is correct
30 Correct 57 ms 104764 KB Output is correct
31 Correct 61 ms 104912 KB Output is correct
32 Correct 58 ms 104900 KB Output is correct
33 Correct 58 ms 104876 KB Output is correct
34 Correct 55 ms 104832 KB Output is correct
35 Correct 56 ms 104780 KB Output is correct
36 Correct 57 ms 104848 KB Output is correct
37 Correct 59 ms 104804 KB Output is correct
38 Correct 240 ms 111432 KB Output is correct
39 Correct 565 ms 273112 KB Output is correct
40 Correct 205 ms 111348 KB Output is correct
41 Correct 164 ms 107568 KB Output is correct
42 Correct 127 ms 109748 KB Output is correct
43 Correct 258 ms 111564 KB Output is correct
44 Correct 76 ms 105220 KB Output is correct
45 Correct 426 ms 174088 KB Output is correct
46 Correct 432 ms 174244 KB Output is correct
47 Correct 726 ms 258160 KB Output is correct
48 Correct 732 ms 258200 KB Output is correct
49 Correct 597 ms 214800 KB Output is correct
50 Correct 560 ms 214868 KB Output is correct
51 Correct 648 ms 243712 KB Output is correct
52 Correct 655 ms 243976 KB Output is correct
53 Correct 100 ms 109108 KB Output is correct
54 Correct 482 ms 165288 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 104708 KB Output is correct
2 Correct 70 ms 104740 KB Output is correct
3 Correct 65 ms 104732 KB Output is correct
4 Correct 69 ms 104600 KB Output is correct
5 Correct 71 ms 104708 KB Output is correct
6 Correct 64 ms 104780 KB Output is correct
7 Correct 68 ms 104832 KB Output is correct
8 Correct 57 ms 104716 KB Output is correct
9 Correct 57 ms 104804 KB Output is correct
10 Correct 62 ms 104776 KB Output is correct
11 Correct 64 ms 104756 KB Output is correct
12 Correct 61 ms 104900 KB Output is correct
13 Correct 100 ms 104808 KB Output is correct
14 Correct 128 ms 104708 KB Output is correct
15 Correct 114 ms 104816 KB Output is correct
16 Correct 399 ms 151756 KB Output is correct
17 Correct 599 ms 158600 KB Output is correct
18 Correct 834 ms 166312 KB Output is correct
19 Correct 517 ms 153532 KB Output is correct
20 Correct 490 ms 152956 KB Output is correct
21 Correct 424 ms 152992 KB Output is correct
22 Correct 525 ms 158004 KB Output is correct
23 Correct 507 ms 157980 KB Output is correct
24 Correct 496 ms 158140 KB Output is correct
25 Correct 511 ms 158540 KB Output is correct
26 Correct 564 ms 158488 KB Output is correct
27 Correct 656 ms 146448 KB Output is correct
28 Correct 506 ms 146332 KB Output is correct
29 Correct 563 ms 146320 KB Output is correct
30 Correct 487 ms 144064 KB Output is correct
31 Correct 437 ms 144068 KB Output is correct
32 Correct 490 ms 144028 KB Output is correct
33 Correct 439 ms 144152 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 104712 KB Output is correct
2 Correct 53 ms 104744 KB Output is correct
3 Correct 56 ms 104628 KB Output is correct
4 Correct 86 ms 104756 KB Output is correct
5 Correct 126 ms 104848 KB Output is correct
6 Correct 58 ms 104876 KB Output is correct
7 Correct 54 ms 105048 KB Output is correct
8 Correct 59 ms 104964 KB Output is correct
9 Correct 224 ms 111416 KB Output is correct
10 Correct 536 ms 273028 KB Output is correct
11 Correct 65 ms 104780 KB Output is correct
12 Correct 136 ms 104908 KB Output is correct
13 Runtime error 699 ms 558028 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -