oj.uz

Submission #877937

# Submission time Handle Problem Language Result Execution time Memory
877937 2023-11-23T22:21:56 Z vivkostov Jail (JOI22_jail) C++14
26 / 100
 1034 ms 772132 KB 
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int q,n,m,c,d,a[2000005],b[2000005],child[2000005],machild[2000005],used[2000005],up[2000005],bin[2000005][30],level[2000005],usedl[2000005];
vector<int>v[2000005],p[20000005];
void find_child(int beg,int par,int lev)
{
    level[beg]=lev;
    child[beg]++;
    bin[beg][0]=par;
    int w=0;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!child[w])
        {
            find_child(w,beg,lev+1);
            child[beg]+=child[w];
            machild[beg]=max(machild[beg],child[w]);
        }
    }
}
int in;
void heavylight(int beg,int last)
{
    in++;
    up[beg]=last;
    used[beg]=in;
    int w,ma=0;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w]&&child[w]==machild[beg])
        {
            heavylight(w,last);
            break;
        }
    }
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w])heavylight(w,w);
    }
}
void make_start(int l,int r,int h)
{
    if(l==r)return;
    int mid=(l+r)/2;
    p[h+n].push_back(h*2+n);
    p[h+n].push_back(h*2+1+n);
    make_start(l,mid,h*2);
    make_start(mid+1,r,h*2+1);
}
void make_finish(int l,int r,int h)
{
    if(l==r)return;
    int mid=(l+r)/2;
    p[h*2+n*5].push_back(h+n*5);
    p[h*2+1+n*5].push_back(h+n*5);
    make_finish(l,mid,h*2);
    make_finish(mid+1,r,h*2+1);
}
void update(int l,int r,int ql,int qr,int h,int to,int type)
{
    if(l>qr||r<ql)return;
    if(l>=ql&&r<=qr)
    {
        if(type==1)p[h+n].push_back(to);
        if(type==2)p[to].push_back(h+n*5);
        if(type==3)p[to].push_back(h+n);
        if(type==4)p[h+n*5].push_back(to);
        return;
    }
    int mid=(l+r)/2;
    update(l,mid,ql,qr,h*2,to,type);
    update(mid+1,r,ql,qr,h*2+1,to,type);
}
void make_bin()
{
    for(int j=1;j<=20;j++)
    {
        for(int i=1;i<=n;i++)
        {
            bin[i][j]=bin[bin[i][j-1]][j-1];
        }
    }
}
void add_all()
{
    for(int i=1;i<=m;i++)
    {
        update(1,n,used[a[i]],used[a[i]],1,i,1);
        update(1,n,used[b[i]],used[b[i]],1,i,2);
    }
}
int lca(int x,int y)
{
    if(level[x]>level[y])swap(x,y);
    for(int i=20;i>=0;i--)
    {
        if(level[bin[y][i]]>=level[x])y=bin[y][i];
    }
    if(x==y)return x;
    for(int i=20;i>=0;i--)
    {
        if(bin[x][i]!=bin[y][i])
        {
            x=bin[x][i];
            y=bin[y][i];
        }
    }
    return bin[x][0];
}
void go_up_heavy1(int beg,int lc,int prisoner)
{
    if(level[up[beg]]==level[lc])
    {
        update(1,n,used[up[beg]],used[beg],1,prisoner,3);
        update(1,n,used[up[beg]],used[beg],1,prisoner,4);
        return;
    }
    if(level[up[beg]]>level[lc])
    {
        update(1,n,used[up[beg]],used[beg],1,prisoner,3);
        update(1,n,used[up[beg]],used[beg],1,prisoner,4);
        go_up_heavy1(bin[up[beg]][0],lc,prisoner);
        return;
    }
    update(1,n,used[lc],used[beg],1,prisoner,3);
    update(1,n,used[lc],used[beg],1,prisoner,4);
}
void go_up_heavy2(int beg,int lc,int prisoner)
{
    if(beg==lc)return;
    if(level[up[beg]]==level[lc])
    {
        update(1,n,used[up[beg]]+1,used[beg],1,prisoner,3);
        update(1,n,used[up[beg]]+1,used[beg],1,prisoner,4);
        return;
    }
    if(level[up[beg]]>level[lc])
    {
        update(1,n,used[up[beg]],used[beg],1,prisoner,3);
        update(1,n,used[up[beg]],used[beg],1,prisoner,4);
        go_up_heavy2(bin[up[beg]][0],lc,prisoner);
        return;
    }
    update(1,n,used[lc]+1,used[beg],1,prisoner,3);
    update(1,n,used[lc]+1,used[beg],1,prisoner,4);
}
void add_path()
{
    for(int i=1;i<=m;i++)
    {
        int g=lca(a[i],b[i]);
        go_up_heavy1(a[i],g,i);
        go_up_heavy2(b[i],g,i);
    }
}
int brr,brj;
void fill_cycle(int beg)
{
    usedl[beg]=2;
    int w;
    for(int i=0; i<p[beg].size(); i++)
    {
        w=p[beg][i];
        if(usedl[w]!=2)fill_cycle(w);
    }
}
void find_cycle(int beg)
{
    usedl[beg]=1;
    int w;
    for(int i=0; i<p[beg].size(); i++)
    {
        w=p[beg][i];
        if(!usedl[w])find_cycle(w);
    }
    if(usedl[beg]!=2&&beg<=m)
    {
        fill_cycle(beg);
        brr++;
    }
}
void resh()
{
    find_child(1,0,1);
    heavylight(1,1);
    make_start(1,n,1);
    make_finish(1,n,1);
    add_all();
    make_bin();
    add_path();
    for(int i=1;i<=m;i++)
    {
        if(!usedl[i])find_cycle(i);
    }
    /*for(int i=1;i<=48;i++)
    {
        cout<<i<<" | ";
        for(int j=0;j<p[i].size();j++)
        {
            cout<<p[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    if(brr!=m)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    for(int i=0;i<=n*10;i++)
    {
        a[i]=0;
        b[i]=0;
        child[i]=0;
        machild[i]=0;
        used[i]=0;
        up[i]=0;
        level[i]=0;
        usedl[i]=0;
        v[i].clear();
        for(int j=0;j<=20;j++)bin[i][j]=0;
    }
    for(int i=0;i<=10*n;i++)p[i].clear();
    in=0;
    brr=0;
}
void read()
{
    cin>>q;
    for(int z=1;z<=q;z++)
    {
        cin>>n;
        for(int i=1;i<n;i++)
        {
            cin>>c>>d;
            v[c].push_back(d);
            v[d].push_back(c);
        }
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>a[i]>>b[i];
        }
        resh();
    }
}
int main()
{
    speed();
    read();
    return 0;
}

Compilation message

jail.cpp: In function 'void find_child(int, int, int)':
jail.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp: In function 'void heavylight(int, int)':
jail.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp:35:11: warning: unused variable 'ma' [-Wunused-variable]
   35 |     int w,ma=0;
      |           ^~
jail.cpp: In function 'void fill_cycle(int)':
jail.cpp:171:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
jail.cpp: In function 'void find_cycle(int)':
jail.cpp:181:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 517716 KB Output is correct
2 Correct 154 ms 517876 KB Output is correct
3 Correct 145 ms 517708 KB Output is correct
4 Correct 164 ms 517984 KB Output is correct
5 Correct 176 ms 517972 KB Output is correct
6 Correct 141 ms 517968 KB Output is correct
7 Correct 136 ms 518156 KB Output is correct
8 Correct 141 ms 517988 KB Output is correct
9 Correct 193 ms 527700 KB Output is correct
10 Correct 287 ms 719960 KB Output is correct
11 Correct 147 ms 517972 KB Output is correct
12 Correct 201 ms 518992 KB Output is correct
13 Correct 404 ms 728912 KB Output is correct
14 Correct 365 ms 729264 KB Output is correct
15 Correct 575 ms 739168 KB Output is correct
16 Correct 1034 ms 772132 KB Output is correct
17 Correct 413 ms 736888 KB Output is correct
18 Correct 450 ms 736004 KB Output is correct
19 Correct 404 ms 735064 KB Output is correct
20 Correct 408 ms 734900 KB Output is correct
21 Correct 417 ms 738196 KB Output is correct
22 Correct 352 ms 726128 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 517788 KB Output is correct
2 Correct 123 ms 517780 KB Output is correct
3 Correct 135 ms 518348 KB Output is correct
4 Correct 125 ms 517968 KB Output is correct
5 Correct 126 ms 517924 KB Output is correct
6 Correct 125 ms 517988 KB Output is correct
7 Correct 129 ms 518048 KB Output is correct
8 Correct 124 ms 517972 KB Output is correct
9 Correct 127 ms 517968 KB Output is correct
10 Correct 126 ms 518180 KB Output is correct
11 Correct 127 ms 518224 KB Output is correct
12 Correct 131 ms 518140 KB Output is correct
13 Correct 128 ms 518172 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 517788 KB Output is correct
2 Correct 123 ms 517780 KB Output is correct
3 Correct 135 ms 518348 KB Output is correct
4 Correct 125 ms 517968 KB Output is correct
5 Correct 126 ms 517924 KB Output is correct
6 Correct 125 ms 517988 KB Output is correct
7 Correct 129 ms 518048 KB Output is correct
8 Correct 124 ms 517972 KB Output is correct
9 Correct 127 ms 517968 KB Output is correct
10 Correct 126 ms 518180 KB Output is correct
11 Correct 127 ms 518224 KB Output is correct
12 Correct 131 ms 518140 KB Output is correct
13 Correct 128 ms 518172 KB Output is correct
14 Correct 125 ms 517776 KB Output is correct
15 Correct 129 ms 517804 KB Output is correct
16 Correct 126 ms 517972 KB Output is correct
17 Correct 126 ms 517968 KB Output is correct
18 Correct 139 ms 517972 KB Output is correct
19 Correct 135 ms 517716 KB Output is correct
20 Correct 127 ms 518188 KB Output is correct
21 Correct 127 ms 517968 KB Output is correct
22 Correct 131 ms 517972 KB Output is correct
23 Correct 127 ms 517804 KB Output is correct
24 Correct 127 ms 517796 KB Output is correct
25 Correct 127 ms 518104 KB Output is correct
26 Correct 126 ms 518108 KB Output is correct
27 Correct 126 ms 518148 KB Output is correct
28 Correct 125 ms 517712 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 517788 KB Output is correct
2 Correct 123 ms 517780 KB Output is correct
3 Correct 135 ms 518348 KB Output is correct
4 Correct 125 ms 517968 KB Output is correct
5 Correct 126 ms 517924 KB Output is correct
6 Correct 125 ms 517988 KB Output is correct
7 Correct 129 ms 518048 KB Output is correct
8 Correct 124 ms 517972 KB Output is correct
9 Correct 127 ms 517968 KB Output is correct
10 Correct 126 ms 518180 KB Output is correct
11 Correct 127 ms 518224 KB Output is correct
12 Correct 131 ms 518140 KB Output is correct
13 Correct 128 ms 518172 KB Output is correct
14 Correct 125 ms 517776 KB Output is correct
15 Correct 129 ms 517804 KB Output is correct
16 Correct 126 ms 517972 KB Output is correct
17 Correct 126 ms 517968 KB Output is correct
18 Correct 139 ms 517972 KB Output is correct
19 Correct 135 ms 517716 KB Output is correct
20 Correct 127 ms 518188 KB Output is correct
21 Correct 127 ms 517968 KB Output is correct
22 Correct 131 ms 517972 KB Output is correct
23 Correct 127 ms 517804 KB Output is correct
24 Correct 127 ms 517796 KB Output is correct
25 Correct 127 ms 518104 KB Output is correct
26 Correct 126 ms 518108 KB Output is correct
27 Correct 126 ms 518148 KB Output is correct
28 Correct 125 ms 517712 KB Output is correct
29 Correct 128 ms 518228 KB Output is correct
30 Correct 129 ms 518200 KB Output is correct
31 Correct 129 ms 517972 KB Output is correct
32 Correct 129 ms 518188 KB Output is correct
33 Correct 131 ms 517980 KB Output is correct
34 Correct 131 ms 518228 KB Output is correct
35 Correct 129 ms 518012 KB Output is correct
36 Correct 127 ms 517968 KB Output is correct
37 Incorrect 126 ms 517980 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 517788 KB Output is correct
2 Correct 123 ms 517780 KB Output is correct
3 Correct 135 ms 518348 KB Output is correct
4 Correct 125 ms 517968 KB Output is correct
5 Correct 126 ms 517924 KB Output is correct
6 Correct 125 ms 517988 KB Output is correct
7 Correct 129 ms 518048 KB Output is correct
8 Correct 124 ms 517972 KB Output is correct
9 Correct 127 ms 517968 KB Output is correct
10 Correct 126 ms 518180 KB Output is correct
11 Correct 127 ms 518224 KB Output is correct
12 Correct 131 ms 518140 KB Output is correct
13 Correct 128 ms 518172 KB Output is correct
14 Correct 125 ms 517776 KB Output is correct
15 Correct 129 ms 517804 KB Output is correct
16 Correct 126 ms 517972 KB Output is correct
17 Correct 126 ms 517968 KB Output is correct
18 Correct 139 ms 517972 KB Output is correct
19 Correct 135 ms 517716 KB Output is correct
20 Correct 127 ms 518188 KB Output is correct
21 Correct 127 ms 517968 KB Output is correct
22 Correct 131 ms 517972 KB Output is correct
23 Correct 127 ms 517804 KB Output is correct
24 Correct 127 ms 517796 KB Output is correct
25 Correct 127 ms 518104 KB Output is correct
26 Correct 126 ms 518108 KB Output is correct
27 Correct 126 ms 518148 KB Output is correct
28 Correct 125 ms 517712 KB Output is correct
29 Correct 128 ms 518228 KB Output is correct
30 Correct 129 ms 518200 KB Output is correct
31 Correct 129 ms 517972 KB Output is correct
32 Correct 129 ms 518188 KB Output is correct
33 Correct 131 ms 517980 KB Output is correct
34 Correct 131 ms 518228 KB Output is correct
35 Correct 129 ms 518012 KB Output is correct
36 Correct 127 ms 517968 KB Output is correct
37 Incorrect 126 ms 517980 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 517656 KB Output is correct
2 Correct 124 ms 517716 KB Output is correct
3 Correct 129 ms 517712 KB Output is correct
4 Correct 137 ms 517716 KB Output is correct
5 Correct 134 ms 517716 KB Output is correct
6 Correct 124 ms 517968 KB Output is correct
7 Correct 128 ms 517996 KB Output is correct
8 Correct 126 ms 517968 KB Output is correct
9 Correct 127 ms 517736 KB Output is correct
10 Correct 125 ms 517968 KB Output is correct
11 Correct 136 ms 517712 KB Output is correct
12 Correct 133 ms 517952 KB Output is correct
13 Incorrect 173 ms 517952 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 517716 KB Output is correct
2 Correct 154 ms 517876 KB Output is correct
3 Correct 145 ms 517708 KB Output is correct
4 Correct 164 ms 517984 KB Output is correct
5 Correct 176 ms 517972 KB Output is correct
6 Correct 141 ms 517968 KB Output is correct
7 Correct 136 ms 518156 KB Output is correct
8 Correct 141 ms 517988 KB Output is correct
9 Correct 193 ms 527700 KB Output is correct
10 Correct 287 ms 719960 KB Output is correct
11 Correct 147 ms 517972 KB Output is correct
12 Correct 201 ms 518992 KB Output is correct
13 Correct 404 ms 728912 KB Output is correct
14 Correct 365 ms 729264 KB Output is correct
15 Correct 575 ms 739168 KB Output is correct
16 Correct 1034 ms 772132 KB Output is correct
17 Correct 413 ms 736888 KB Output is correct
18 Correct 450 ms 736004 KB Output is correct
19 Correct 404 ms 735064 KB Output is correct
20 Correct 408 ms 734900 KB Output is correct
21 Correct 417 ms 738196 KB Output is correct
22 Correct 352 ms 726128 KB Output is correct
23 Correct 125 ms 517788 KB Output is correct
24 Correct 123 ms 517780 KB Output is correct
25 Correct 135 ms 518348 KB Output is correct
26 Correct 125 ms 517968 KB Output is correct
27 Correct 126 ms 517924 KB Output is correct
28 Correct 125 ms 517988 KB Output is correct
29 Correct 129 ms 518048 KB Output is correct
30 Correct 124 ms 517972 KB Output is correct
31 Correct 127 ms 517968 KB Output is correct
32 Correct 126 ms 518180 KB Output is correct
33 Correct 127 ms 518224 KB Output is correct
34 Correct 131 ms 518140 KB Output is correct
35 Correct 128 ms 518172 KB Output is correct
36 Correct 125 ms 517776 KB Output is correct
37 Correct 129 ms 517804 KB Output is correct
38 Correct 126 ms 517972 KB Output is correct
39 Correct 126 ms 517968 KB Output is correct
40 Correct 139 ms 517972 KB Output is correct
41 Correct 135 ms 517716 KB Output is correct
42 Correct 127 ms 518188 KB Output is correct
43 Correct 127 ms 517968 KB Output is correct
44 Correct 131 ms 517972 KB Output is correct
45 Correct 127 ms 517804 KB Output is correct
46 Correct 127 ms 517796 KB Output is correct
47 Correct 127 ms 518104 KB Output is correct
48 Correct 126 ms 518108 KB Output is correct
49 Correct 126 ms 518148 KB Output is correct
50 Correct 125 ms 517712 KB Output is correct
51 Correct 128 ms 518228 KB Output is correct
52 Correct 129 ms 518200 KB Output is correct
53 Correct 129 ms 517972 KB Output is correct
54 Correct 129 ms 518188 KB Output is correct
55 Correct 131 ms 517980 KB Output is correct
56 Correct 131 ms 518228 KB Output is correct
57 Correct 129 ms 518012 KB Output is correct
58 Correct 127 ms 517968 KB Output is correct
59 Incorrect 126 ms 517980 KB Output isn't correct
60 Halted 0 ms 0 KB -