oj.uz

Submission #877940

# Submission time Handle Problem Language Result Execution time Memory
877940 2023-11-23T22:25:07 Z vivkostov Jail (JOI22_jail) C++14
26 / 100
 1043 ms 769364 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)
{
    if(beg<=m)brj++;
    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);
        if(brj>=2)brr++;
        brj=0;
    }
}
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<=n*10;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)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:172:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
jail.cpp: In function 'void find_cycle(int)':
jail.cpp:182:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 517612 KB Output is correct
2 Correct 125 ms 517716 KB Output is correct
3 Correct 124 ms 517716 KB Output is correct
4 Correct 144 ms 517936 KB Output is correct
5 Correct 164 ms 518228 KB Output is correct
6 Correct 128 ms 518008 KB Output is correct
7 Correct 125 ms 518200 KB Output is correct
8 Correct 129 ms 518128 KB Output is correct
9 Correct 206 ms 528136 KB Output is correct
10 Correct 272 ms 720180 KB Output is correct
11 Correct 136 ms 517580 KB Output is correct
12 Correct 201 ms 517948 KB Output is correct
13 Correct 403 ms 726776 KB Output is correct
14 Correct 366 ms 727184 KB Output is correct
15 Correct 595 ms 737288 KB Output is correct
16 Correct 1043 ms 769364 KB Output is correct
17 Correct 417 ms 734908 KB Output is correct
18 Correct 442 ms 733120 KB Output is correct
19 Correct 406 ms 732756 KB Output is correct
20 Correct 418 ms 732988 KB Output is correct
21 Correct 410 ms 734032 KB Output is correct
22 Correct 354 ms 723728 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 517796 KB Output is correct
2 Correct 122 ms 517716 KB Output is correct
3 Correct 122 ms 517960 KB Output is correct
4 Correct 122 ms 517972 KB Output is correct
5 Correct 123 ms 517972 KB Output is correct
6 Correct 122 ms 517996 KB Output is correct
7 Correct 123 ms 517968 KB Output is correct
8 Correct 125 ms 517968 KB Output is correct
9 Correct 126 ms 517972 KB Output is correct
10 Correct 125 ms 518108 KB Output is correct
11 Correct 124 ms 517972 KB Output is correct
12 Correct 123 ms 517968 KB Output is correct
13 Correct 123 ms 517984 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 517796 KB Output is correct
2 Correct 122 ms 517716 KB Output is correct
3 Correct 122 ms 517960 KB Output is correct
4 Correct 122 ms 517972 KB Output is correct
5 Correct 123 ms 517972 KB Output is correct
6 Correct 122 ms 517996 KB Output is correct
7 Correct 123 ms 517968 KB Output is correct
8 Correct 125 ms 517968 KB Output is correct
9 Correct 126 ms 517972 KB Output is correct
10 Correct 125 ms 518108 KB Output is correct
11 Correct 124 ms 517972 KB Output is correct
12 Correct 123 ms 517968 KB Output is correct
13 Correct 123 ms 517984 KB Output is correct
14 Correct 124 ms 517968 KB Output is correct
15 Correct 120 ms 517632 KB Output is correct
16 Correct 125 ms 517996 KB Output is correct
17 Correct 124 ms 518112 KB Output is correct
18 Correct 124 ms 517968 KB Output is correct
19 Correct 123 ms 517712 KB Output is correct
20 Correct 129 ms 518180 KB Output is correct
21 Correct 123 ms 517972 KB Output is correct
22 Correct 124 ms 518196 KB Output is correct
23 Correct 121 ms 517716 KB Output is correct
24 Correct 121 ms 517944 KB Output is correct
25 Correct 126 ms 518132 KB Output is correct
26 Correct 126 ms 517968 KB Output is correct
27 Correct 122 ms 517972 KB Output is correct
28 Correct 125 ms 517760 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 517796 KB Output is correct
2 Correct 122 ms 517716 KB Output is correct
3 Correct 122 ms 517960 KB Output is correct
4 Correct 122 ms 517972 KB Output is correct
5 Correct 123 ms 517972 KB Output is correct
6 Correct 122 ms 517996 KB Output is correct
7 Correct 123 ms 517968 KB Output is correct
8 Correct 125 ms 517968 KB Output is correct
9 Correct 126 ms 517972 KB Output is correct
10 Correct 125 ms 518108 KB Output is correct
11 Correct 124 ms 517972 KB Output is correct
12 Correct 123 ms 517968 KB Output is correct
13 Correct 123 ms 517984 KB Output is correct
14 Correct 124 ms 517968 KB Output is correct
15 Correct 120 ms 517632 KB Output is correct
16 Correct 125 ms 517996 KB Output is correct
17 Correct 124 ms 518112 KB Output is correct
18 Correct 124 ms 517968 KB Output is correct
19 Correct 123 ms 517712 KB Output is correct
20 Correct 129 ms 518180 KB Output is correct
21 Correct 123 ms 517972 KB Output is correct
22 Correct 124 ms 518196 KB Output is correct
23 Correct 121 ms 517716 KB Output is correct
24 Correct 121 ms 517944 KB Output is correct
25 Correct 126 ms 518132 KB Output is correct
26 Correct 126 ms 517968 KB Output is correct
27 Correct 122 ms 517972 KB Output is correct
28 Correct 125 ms 517760 KB Output is correct
29 Correct 125 ms 518044 KB Output is correct
30 Correct 125 ms 518212 KB Output is correct
31 Correct 126 ms 518208 KB Output is correct
32 Correct 125 ms 517968 KB Output is correct
33 Correct 125 ms 518184 KB Output is correct
34 Correct 129 ms 518112 KB Output is correct
35 Correct 124 ms 517968 KB Output is correct
36 Correct 126 ms 517976 KB Output is correct
37 Incorrect 126 ms 517888 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 517796 KB Output is correct
2 Correct 122 ms 517716 KB Output is correct
3 Correct 122 ms 517960 KB Output is correct
4 Correct 122 ms 517972 KB Output is correct
5 Correct 123 ms 517972 KB Output is correct
6 Correct 122 ms 517996 KB Output is correct
7 Correct 123 ms 517968 KB Output is correct
8 Correct 125 ms 517968 KB Output is correct
9 Correct 126 ms 517972 KB Output is correct
10 Correct 125 ms 518108 KB Output is correct
11 Correct 124 ms 517972 KB Output is correct
12 Correct 123 ms 517968 KB Output is correct
13 Correct 123 ms 517984 KB Output is correct
14 Correct 124 ms 517968 KB Output is correct
15 Correct 120 ms 517632 KB Output is correct
16 Correct 125 ms 517996 KB Output is correct
17 Correct 124 ms 518112 KB Output is correct
18 Correct 124 ms 517968 KB Output is correct
19 Correct 123 ms 517712 KB Output is correct
20 Correct 129 ms 518180 KB Output is correct
21 Correct 123 ms 517972 KB Output is correct
22 Correct 124 ms 518196 KB Output is correct
23 Correct 121 ms 517716 KB Output is correct
24 Correct 121 ms 517944 KB Output is correct
25 Correct 126 ms 518132 KB Output is correct
26 Correct 126 ms 517968 KB Output is correct
27 Correct 122 ms 517972 KB Output is correct
28 Correct 125 ms 517760 KB Output is correct
29 Correct 125 ms 518044 KB Output is correct
30 Correct 125 ms 518212 KB Output is correct
31 Correct 126 ms 518208 KB Output is correct
32 Correct 125 ms 517968 KB Output is correct
33 Correct 125 ms 518184 KB Output is correct
34 Correct 129 ms 518112 KB Output is correct
35 Correct 124 ms 517968 KB Output is correct
36 Correct 126 ms 517976 KB Output is correct
37 Incorrect 126 ms 517888 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 517792 KB Output is correct
2 Correct 121 ms 517748 KB Output is correct
3 Correct 124 ms 517692 KB Output is correct
4 Correct 124 ms 517684 KB Output is correct
5 Correct 132 ms 517940 KB Output is correct
6 Correct 124 ms 517976 KB Output is correct
7 Correct 125 ms 518116 KB Output is correct
8 Correct 120 ms 517736 KB Output is correct
9 Correct 121 ms 517660 KB Output is correct
10 Correct 124 ms 517840 KB Output is correct
11 Correct 121 ms 517712 KB Output is correct
12 Correct 125 ms 517980 KB Output is correct
13 Incorrect 176 ms 517972 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 517612 KB Output is correct
2 Correct 125 ms 517716 KB Output is correct
3 Correct 124 ms 517716 KB Output is correct
4 Correct 144 ms 517936 KB Output is correct
5 Correct 164 ms 518228 KB Output is correct
6 Correct 128 ms 518008 KB Output is correct
7 Correct 125 ms 518200 KB Output is correct
8 Correct 129 ms 518128 KB Output is correct
9 Correct 206 ms 528136 KB Output is correct
10 Correct 272 ms 720180 KB Output is correct
11 Correct 136 ms 517580 KB Output is correct
12 Correct 201 ms 517948 KB Output is correct
13 Correct 403 ms 726776 KB Output is correct
14 Correct 366 ms 727184 KB Output is correct
15 Correct 595 ms 737288 KB Output is correct
16 Correct 1043 ms 769364 KB Output is correct
17 Correct 417 ms 734908 KB Output is correct
18 Correct 442 ms 733120 KB Output is correct
19 Correct 406 ms 732756 KB Output is correct
20 Correct 418 ms 732988 KB Output is correct
21 Correct 410 ms 734032 KB Output is correct
22 Correct 354 ms 723728 KB Output is correct
23 Correct 123 ms 517796 KB Output is correct
24 Correct 122 ms 517716 KB Output is correct
25 Correct 122 ms 517960 KB Output is correct
26 Correct 122 ms 517972 KB Output is correct
27 Correct 123 ms 517972 KB Output is correct
28 Correct 122 ms 517996 KB Output is correct
29 Correct 123 ms 517968 KB Output is correct
30 Correct 125 ms 517968 KB Output is correct
31 Correct 126 ms 517972 KB Output is correct
32 Correct 125 ms 518108 KB Output is correct
33 Correct 124 ms 517972 KB Output is correct
34 Correct 123 ms 517968 KB Output is correct
35 Correct 123 ms 517984 KB Output is correct
36 Correct 124 ms 517968 KB Output is correct
37 Correct 120 ms 517632 KB Output is correct
38 Correct 125 ms 517996 KB Output is correct
39 Correct 124 ms 518112 KB Output is correct
40 Correct 124 ms 517968 KB Output is correct
41 Correct 123 ms 517712 KB Output is correct
42 Correct 129 ms 518180 KB Output is correct
43 Correct 123 ms 517972 KB Output is correct
44 Correct 124 ms 518196 KB Output is correct
45 Correct 121 ms 517716 KB Output is correct
46 Correct 121 ms 517944 KB Output is correct
47 Correct 126 ms 518132 KB Output is correct
48 Correct 126 ms 517968 KB Output is correct
49 Correct 122 ms 517972 KB Output is correct
50 Correct 125 ms 517760 KB Output is correct
51 Correct 125 ms 518044 KB Output is correct
52 Correct 125 ms 518212 KB Output is correct
53 Correct 126 ms 518208 KB Output is correct
54 Correct 125 ms 517968 KB Output is correct
55 Correct 125 ms 518184 KB Output is correct
56 Correct 129 ms 518112 KB Output is correct
57 Correct 124 ms 517968 KB Output is correct
58 Correct 126 ms 517976 KB Output is correct
59 Incorrect 126 ms 517888 KB Output isn't correct
60 Halted 0 ms 0 KB -