oj.uz

Submission #544563

# Submission time Handle Problem Language Result Execution time Memory
544563 2022-04-02T11:15:04 Z Rafi22 Jail (JOI22_jail) C++14
100 / 100
 2849 ms 292860 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=120007;

vector<int>G[N];
int skok[N][17];
vector<int>G1[N*37];
int ile[N*37];
int pre[N],post[N],c;
int n;

void edge(int u,int v)
{
    //cout<<u<<" "<<v<<endl;
    G1[u].pb(v);
    ile[v]++;
}

void dfs(int v,int o)
{
    pre[v]=++c;
    skok[v][0]=o;
    edge(n+v,v);
    edge(n+v,o);
    edge(v+n*18,n+v+n*18);
    edge(o+n*18,n+v+n*18);
    for(int i=1;i<17;i++)
    {
        skok[v][i]=skok[skok[v][i-1]][i-1];
        edge((i+1)*n+v,i*n+v);
        edge((i+1)*n+v,i*n+skok[v][i-1]);
        edge(i*n+v+n*18,(i+1)*n+v+n*18);
        edge(i*n+skok[v][i-1]+n*18,(i+1)*n+v+n*18);
    }
    for(auto u:G[v])
    {
        if(u==o) continue;
        dfs(u,v);
    }
    post[v]=c;
}

bool anc(int u,int v){return pre[u]<=pre[v]&&post[u]>=post[v];}
int lca(int u,int v)
{
    if(anc(u,v)) return u;
    for(int i=16;i>=0;i--) if(!anc(skok[u][i],v)) u=skok[u][i];
    return skok[u][0];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt,xd=0;
    cin>>tt;
    while(tt--)
    {
        int a,b,m;
        cin>>n;
        for(int i=1;i<n;i++)
        {
            cin>>a>>b;
            G[a].pb(b);
            G[b].pb(a);
        }
        c=0;
        dfs(1,1);
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>a>>b;
            edge(a,b);
            edge(a+n*18,a);
            int l=lca(a,b);
           // cout<<l<<endl;
            if(a!=l)
            {
                edge(a,l);
                int x=skok[a][0];
                if(x!=l&&skok[x][0]==l)
                {
                    edge(a,x);
                    edge(x+n*18,a);
                }
                for(int j=16;j>=0;j--)
                {
                    if(!anc(skok[x][j],l))
                    {
                        //cout<<"XD"<<skok[x][j]<<endl;
                        edge(a,(j+1)*n+x);
                        edge((j+1)*n+x+n*18,a);
                        x=skok[x][j];
                    }
                }
            }
            if(b!=l)
            {
                edge(l+n*18,a);
                int x=skok[b][0];
                if(x!=l&&skok[x][0]==l)
                {
                    edge(a,x);
                    edge(x+n*18,a);
                }
                for(int j=16;j>=0;j--)
                {
                    if(!anc(skok[x][j],l))
                    {
                        edge(a,(j+1)*n+x);
                        edge((j+1)*n+x+n*18,a);
                        x=skok[x][j];
                    }
                }
            }
            edge(a,b+n*18);
        }
        deque<int>Q;
        for(int i=1;i<=n*36;i++) if(ile[i]==0) Q.pb(i);
        int c=0;
        while(sz(Q)>0)
        {
            int v=Q[0];
            Q.pop_front();
            c++;
            for(auto u:G1[v])
            {
                ile[u]--;
                if(ile[u]==0) Q.pb(u);
            }
        }
        if(c==n*36) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=1;i<=n*36;i++)
        {
            ile[i]=0;
            G1[i].clear();
        }
    }

    return 0;
}

Compilation message

jail.cpp: In function 'int main()':
jail.cpp:69:12: warning: unused variable 'xd' [-Wunused-variable]
   69 |     int tt,xd=0;
      |            ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 107340 KB Output is correct
2 Correct 51 ms 107412 KB Output is correct
3 Correct 50 ms 107340 KB Output is correct
4 Correct 124 ms 107944 KB Output is correct
5 Correct 207 ms 108240 KB Output is correct
6 Correct 63 ms 107764 KB Output is correct
7 Correct 58 ms 107748 KB Output is correct
8 Correct 62 ms 107864 KB Output is correct
9 Correct 460 ms 117536 KB Output is correct
10 Correct 832 ms 280656 KB Output is correct
11 Correct 84 ms 107568 KB Output is correct
12 Correct 219 ms 108536 KB Output is correct
13 Correct 1078 ms 283344 KB Output is correct
14 Correct 836 ms 283592 KB Output is correct
15 Correct 928 ms 284828 KB Output is correct
16 Correct 1229 ms 291864 KB Output is correct
17 Correct 1080 ms 285600 KB Output is correct
18 Correct 1000 ms 285196 KB Output is correct
19 Correct 1031 ms 285772 KB Output is correct
20 Correct 944 ms 285752 KB Output is correct
21 Correct 838 ms 286256 KB Output is correct
22 Correct 801 ms 282760 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 107340 KB Output is correct
2 Correct 52 ms 107404 KB Output is correct
3 Correct 65 ms 107904 KB Output is correct
4 Correct 66 ms 107740 KB Output is correct
5 Correct 61 ms 107800 KB Output is correct
6 Correct 63 ms 107780 KB Output is correct
7 Correct 62 ms 107820 KB Output is correct
8 Correct 63 ms 107764 KB Output is correct
9 Correct 63 ms 107740 KB Output is correct
10 Correct 62 ms 107828 KB Output is correct
11 Correct 68 ms 107740 KB Output is correct
12 Correct 59 ms 107680 KB Output is correct
13 Correct 62 ms 107680 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 107340 KB Output is correct
2 Correct 52 ms 107404 KB Output is correct
3 Correct 65 ms 107904 KB Output is correct
4 Correct 66 ms 107740 KB Output is correct
5 Correct 61 ms 107800 KB Output is correct
6 Correct 63 ms 107780 KB Output is correct
7 Correct 62 ms 107820 KB Output is correct
8 Correct 63 ms 107764 KB Output is correct
9 Correct 63 ms 107740 KB Output is correct
10 Correct 62 ms 107828 KB Output is correct
11 Correct 68 ms 107740 KB Output is correct
12 Correct 59 ms 107680 KB Output is correct
13 Correct 62 ms 107680 KB Output is correct
14 Correct 57 ms 107404 KB Output is correct
15 Correct 67 ms 107412 KB Output is correct
16 Correct 74 ms 107820 KB Output is correct
17 Correct 68 ms 107828 KB Output is correct
18 Correct 68 ms 107732 KB Output is correct
19 Correct 58 ms 107408 KB Output is correct
20 Correct 77 ms 107852 KB Output is correct
21 Correct 74 ms 107816 KB Output is correct
22 Correct 66 ms 107804 KB Output is correct
23 Correct 58 ms 107472 KB Output is correct
24 Correct 60 ms 107548 KB Output is correct
25 Correct 66 ms 107852 KB Output is correct
26 Correct 58 ms 107800 KB Output is correct
27 Correct 65 ms 107796 KB Output is correct
28 Correct 64 ms 107372 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 107340 KB Output is correct
2 Correct 52 ms 107404 KB Output is correct
3 Correct 65 ms 107904 KB Output is correct
4 Correct 66 ms 107740 KB Output is correct
5 Correct 61 ms 107800 KB Output is correct
6 Correct 63 ms 107780 KB Output is correct
7 Correct 62 ms 107820 KB Output is correct
8 Correct 63 ms 107764 KB Output is correct
9 Correct 63 ms 107740 KB Output is correct
10 Correct 62 ms 107828 KB Output is correct
11 Correct 68 ms 107740 KB Output is correct
12 Correct 59 ms 107680 KB Output is correct
13 Correct 62 ms 107680 KB Output is correct
14 Correct 57 ms 107404 KB Output is correct
15 Correct 67 ms 107412 KB Output is correct
16 Correct 74 ms 107820 KB Output is correct
17 Correct 68 ms 107828 KB Output is correct
18 Correct 68 ms 107732 KB Output is correct
19 Correct 58 ms 107408 KB Output is correct
20 Correct 77 ms 107852 KB Output is correct
21 Correct 74 ms 107816 KB Output is correct
22 Correct 66 ms 107804 KB Output is correct
23 Correct 58 ms 107472 KB Output is correct
24 Correct 60 ms 107548 KB Output is correct
25 Correct 66 ms 107852 KB Output is correct
26 Correct 58 ms 107800 KB Output is correct
27 Correct 65 ms 107796 KB Output is correct
28 Correct 64 ms 107372 KB Output is correct
29 Correct 69 ms 107852 KB Output is correct
30 Correct 66 ms 107788 KB Output is correct
31 Correct 69 ms 107880 KB Output is correct
32 Correct 77 ms 107788 KB Output is correct
33 Correct 71 ms 107804 KB Output is correct
34 Correct 69 ms 107752 KB Output is correct
35 Correct 64 ms 107728 KB Output is correct
36 Correct 66 ms 107724 KB Output is correct
37 Correct 66 ms 107716 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 107340 KB Output is correct
2 Correct 52 ms 107404 KB Output is correct
3 Correct 65 ms 107904 KB Output is correct
4 Correct 66 ms 107740 KB Output is correct
5 Correct 61 ms 107800 KB Output is correct
6 Correct 63 ms 107780 KB Output is correct
7 Correct 62 ms 107820 KB Output is correct
8 Correct 63 ms 107764 KB Output is correct
9 Correct 63 ms 107740 KB Output is correct
10 Correct 62 ms 107828 KB Output is correct
11 Correct 68 ms 107740 KB Output is correct
12 Correct 59 ms 107680 KB Output is correct
13 Correct 62 ms 107680 KB Output is correct
14 Correct 57 ms 107404 KB Output is correct
15 Correct 67 ms 107412 KB Output is correct
16 Correct 74 ms 107820 KB Output is correct
17 Correct 68 ms 107828 KB Output is correct
18 Correct 68 ms 107732 KB Output is correct
19 Correct 58 ms 107408 KB Output is correct
20 Correct 77 ms 107852 KB Output is correct
21 Correct 74 ms 107816 KB Output is correct
22 Correct 66 ms 107804 KB Output is correct
23 Correct 58 ms 107472 KB Output is correct
24 Correct 60 ms 107548 KB Output is correct
25 Correct 66 ms 107852 KB Output is correct
26 Correct 58 ms 107800 KB Output is correct
27 Correct 65 ms 107796 KB Output is correct
28 Correct 64 ms 107372 KB Output is correct
29 Correct 69 ms 107852 KB Output is correct
30 Correct 66 ms 107788 KB Output is correct
31 Correct 69 ms 107880 KB Output is correct
32 Correct 77 ms 107788 KB Output is correct
33 Correct 71 ms 107804 KB Output is correct
34 Correct 69 ms 107752 KB Output is correct
35 Correct 64 ms 107728 KB Output is correct
36 Correct 66 ms 107724 KB Output is correct
37 Correct 66 ms 107716 KB Output is correct
38 Correct 504 ms 117600 KB Output is correct
39 Correct 985 ms 280628 KB Output is correct
40 Correct 748 ms 119104 KB Output is correct
41 Correct 861 ms 117664 KB Output is correct
42 Correct 371 ms 118648 KB Output is correct
43 Correct 671 ms 118460 KB Output is correct
44 Correct 103 ms 109132 KB Output is correct
45 Correct 2047 ms 274248 KB Output is correct
46 Correct 2033 ms 274292 KB Output is correct
47 Correct 1456 ms 274452 KB Output is correct
48 Correct 1390 ms 274556 KB Output is correct
49 Correct 1510 ms 275148 KB Output is correct
50 Correct 1487 ms 275068 KB Output is correct
51 Correct 1444 ms 275156 KB Output is correct
52 Correct 1427 ms 275512 KB Output is correct
53 Correct 197 ms 120012 KB Output is correct
54 Correct 2328 ms 274656 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 107440 KB Output is correct
2 Correct 52 ms 107428 KB Output is correct
3 Correct 53 ms 107340 KB Output is correct
4 Correct 52 ms 107408 KB Output is correct
5 Correct 82 ms 107540 KB Output is correct
6 Correct 55 ms 107792 KB Output is correct
7 Correct 57 ms 107740 KB Output is correct
8 Correct 52 ms 107340 KB Output is correct
9 Correct 53 ms 107508 KB Output is correct
10 Correct 54 ms 107560 KB Output is correct
11 Correct 54 ms 107456 KB Output is correct
12 Correct 60 ms 107744 KB Output is correct
13 Correct 150 ms 108204 KB Output is correct
14 Correct 246 ms 108484 KB Output is correct
15 Correct 198 ms 108348 KB Output is correct
16 Correct 2222 ms 275856 KB Output is correct
17 Correct 2203 ms 280120 KB Output is correct
18 Correct 2325 ms 285340 KB Output is correct
19 Correct 2359 ms 276832 KB Output is correct
20 Correct 2411 ms 276424 KB Output is correct
21 Correct 2520 ms 276364 KB Output is correct
22 Correct 2226 ms 280200 KB Output is correct
23 Correct 2270 ms 279836 KB Output is correct
24 Correct 2372 ms 279968 KB Output is correct
25 Correct 2340 ms 280532 KB Output is correct
26 Correct 2357 ms 280244 KB Output is correct
27 Correct 2449 ms 281024 KB Output is correct
28 Correct 2077 ms 281128 KB Output is correct
29 Correct 2053 ms 281048 KB Output is correct
30 Correct 2409 ms 277620 KB Output is correct
31 Correct 2064 ms 277368 KB Output is correct
32 Correct 2342 ms 276808 KB Output is correct
33 Correct 2224 ms 277536 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 107340 KB Output is correct
2 Correct 51 ms 107412 KB Output is correct
3 Correct 50 ms 107340 KB Output is correct
4 Correct 124 ms 107944 KB Output is correct
5 Correct 207 ms 108240 KB Output is correct
6 Correct 63 ms 107764 KB Output is correct
7 Correct 58 ms 107748 KB Output is correct
8 Correct 62 ms 107864 KB Output is correct
9 Correct 460 ms 117536 KB Output is correct
10 Correct 832 ms 280656 KB Output is correct
11 Correct 84 ms 107568 KB Output is correct
12 Correct 219 ms 108536 KB Output is correct
13 Correct 1078 ms 283344 KB Output is correct
14 Correct 836 ms 283592 KB Output is correct
15 Correct 928 ms 284828 KB Output is correct
16 Correct 1229 ms 291864 KB Output is correct
17 Correct 1080 ms 285600 KB Output is correct
18 Correct 1000 ms 285196 KB Output is correct
19 Correct 1031 ms 285772 KB Output is correct
20 Correct 944 ms 285752 KB Output is correct
21 Correct 838 ms 286256 KB Output is correct
22 Correct 801 ms 282760 KB Output is correct
23 Correct 52 ms 107340 KB Output is correct
24 Correct 52 ms 107404 KB Output is correct
25 Correct 65 ms 107904 KB Output is correct
26 Correct 66 ms 107740 KB Output is correct
27 Correct 61 ms 107800 KB Output is correct
28 Correct 63 ms 107780 KB Output is correct
29 Correct 62 ms 107820 KB Output is correct
30 Correct 63 ms 107764 KB Output is correct
31 Correct 63 ms 107740 KB Output is correct
32 Correct 62 ms 107828 KB Output is correct
33 Correct 68 ms 107740 KB Output is correct
34 Correct 59 ms 107680 KB Output is correct
35 Correct 62 ms 107680 KB Output is correct
36 Correct 57 ms 107404 KB Output is correct
37 Correct 67 ms 107412 KB Output is correct
38 Correct 74 ms 107820 KB Output is correct
39 Correct 68 ms 107828 KB Output is correct
40 Correct 68 ms 107732 KB Output is correct
41 Correct 58 ms 107408 KB Output is correct
42 Correct 77 ms 107852 KB Output is correct
43 Correct 74 ms 107816 KB Output is correct
44 Correct 66 ms 107804 KB Output is correct
45 Correct 58 ms 107472 KB Output is correct
46 Correct 60 ms 107548 KB Output is correct
47 Correct 66 ms 107852 KB Output is correct
48 Correct 58 ms 107800 KB Output is correct
49 Correct 65 ms 107796 KB Output is correct
50 Correct 64 ms 107372 KB Output is correct
51 Correct 69 ms 107852 KB Output is correct
52 Correct 66 ms 107788 KB Output is correct
53 Correct 69 ms 107880 KB Output is correct
54 Correct 77 ms 107788 KB Output is correct
55 Correct 71 ms 107804 KB Output is correct
56 Correct 69 ms 107752 KB Output is correct
57 Correct 64 ms 107728 KB Output is correct
58 Correct 66 ms 107724 KB Output is correct
59 Correct 66 ms 107716 KB Output is correct
60 Correct 504 ms 117600 KB Output is correct
61 Correct 985 ms 280628 KB Output is correct
62 Correct 748 ms 119104 KB Output is correct
63 Correct 861 ms 117664 KB Output is correct
64 Correct 371 ms 118648 KB Output is correct
65 Correct 671 ms 118460 KB Output is correct
66 Correct 103 ms 109132 KB Output is correct
67 Correct 2047 ms 274248 KB Output is correct
68 Correct 2033 ms 274292 KB Output is correct
69 Correct 1456 ms 274452 KB Output is correct
70 Correct 1390 ms 274556 KB Output is correct
71 Correct 1510 ms 275148 KB Output is correct
72 Correct 1487 ms 275068 KB Output is correct
73 Correct 1444 ms 275156 KB Output is correct
74 Correct 1427 ms 275512 KB Output is correct
75 Correct 197 ms 120012 KB Output is correct
76 Correct 2328 ms 274656 KB Output is correct
77 Correct 52 ms 107440 KB Output is correct
78 Correct 52 ms 107428 KB Output is correct
79 Correct 53 ms 107340 KB Output is correct
80 Correct 52 ms 107408 KB Output is correct
81 Correct 82 ms 107540 KB Output is correct
82 Correct 55 ms 107792 KB Output is correct
83 Correct 57 ms 107740 KB Output is correct
84 Correct 52 ms 107340 KB Output is correct
85 Correct 53 ms 107508 KB Output is correct
86 Correct 54 ms 107560 KB Output is correct
87 Correct 54 ms 107456 KB Output is correct
88 Correct 60 ms 107744 KB Output is correct
89 Correct 150 ms 108204 KB Output is correct
90 Correct 246 ms 108484 KB Output is correct
91 Correct 198 ms 108348 KB Output is correct
92 Correct 2222 ms 275856 KB Output is correct
93 Correct 2203 ms 280120 KB Output is correct
94 Correct 2325 ms 285340 KB Output is correct
95 Correct 2359 ms 276832 KB Output is correct
96 Correct 2411 ms 276424 KB Output is correct
97 Correct 2520 ms 276364 KB Output is correct
98 Correct 2226 ms 280200 KB Output is correct
99 Correct 2270 ms 279836 KB Output is correct
100 Correct 2372 ms 279968 KB Output is correct
101 Correct 2340 ms 280532 KB Output is correct
102 Correct 2357 ms 280244 KB Output is correct
103 Correct 2449 ms 281024 KB Output is correct
104 Correct 2077 ms 281128 KB Output is correct
105 Correct 2053 ms 281048 KB Output is correct
106 Correct 2409 ms 277620 KB Output is correct
107 Correct 2064 ms 277368 KB Output is correct
108 Correct 2342 ms 276808 KB Output is correct
109 Correct 2224 ms 277536 KB Output is correct
110 Correct 263 ms 108760 KB Output is correct
111 Correct 199 ms 108240 KB Output is correct
112 Correct 1422 ms 285204 KB Output is correct
113 Correct 1711 ms 277852 KB Output is correct
114 Correct 952 ms 283464 KB Output is correct
115 Correct 718 ms 275728 KB Output is correct
116 Correct 2719 ms 278280 KB Output is correct
117 Correct 2446 ms 285548 KB Output is correct
118 Correct 2563 ms 274672 KB Output is correct
119 Correct 2471 ms 274620 KB Output is correct
120 Correct 223 ms 121704 KB Output is correct
121 Correct 2755 ms 278588 KB Output is correct
122 Correct 2849 ms 278596 KB Output is correct
123 Correct 1651 ms 278896 KB Output is correct
124 Correct 1239 ms 278992 KB Output is correct
125 Correct 1631 ms 279412 KB Output is correct
126 Correct 1491 ms 292860 KB Output is correct
127 Correct 1543 ms 285336 KB Output is correct
128 Correct 1506 ms 285284 KB Output is correct
129 Correct 1759 ms 285316 KB Output is correct
130 Correct 1534 ms 285236 KB Output is correct