oj.uz

Submission #880918

# Submission time Handle Problem Language Result Execution time Memory
880918 2023-11-30T08:43:43 Z vivkostov Jail (JOI22_jail) C++14
5 / 100
 83 ms 158560 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);
}
struct cell
{
    int st,in;
};
bool cmp(cell a1,cell a2)
{
    return a1.st>a2.st;
}
int q,n,m,c,d,a[2000005],b[2000005],child[2000005],machild[2000005],used[2000005],up[2000005],bin[2000005][60],level[2000005],usedl[2000005],in,brr,brj;
vector<int>v[2000005],p[2000005],rp[2000005];
int low[2000005],tim,usedr[2000005];
cell order[2000005];
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]);
        }
    }
}
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<=30;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=30;i>=0;i--)
    {
        if(level[bin[y][i]]>=level[x])y=bin[y][i];
    }
    if(x==y)return x;
    for(int i=30;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_heavy(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_heavy(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 add_path()
{
    for(int i=1;i<=m;i++)
    {
        int g=lca(a[i],b[i]);
        go_up_heavy(a[i],g,i);
        go_up_heavy(b[i],g,i);
    }
}
void add_rv(int beg)
{
    usedr[beg]=1;
    int w;
    for(int i=0;i<p[beg].size();i++)
    {
        w=p[beg][i];
        rp[w].push_back(beg);
        if(!usedr[w])add_rv(w);
    }
}
void fill_cycle(int beg)
{
    if(beg<=m)
    {
        brj++;
    }
    usedl[beg]=2;
    int w;
    for(int i=0; i<rp[beg].size(); i++)
    {
        w=rp[beg][i];
        if(usedl[w]==1)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);
    }
    tim++;
    order[beg].st=tim;
    order[beg].in=beg;
}
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();
    add_rv(1);
    for(int i=1;i<=n*10;i++)
    {
        if(!usedl[i])find_cycle(i);
    }
    sort(order+1,order+n*10+1,cmp);
    for(int i=1;i<=n*10;i++)
    {
        if(usedl[order[i].in]==1)
        {
            fill_cycle(order[i].in);
            if(brj>=2)
            {
                brr=1;
            }
            brj=0;
        }
    }
    /*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*15;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;
        usedr[i]=0;
        low[i]=0;
        rp[i].clear();
        p[i].clear();
        order[i].in=0;
        order[i].st=0;
        v[i].clear();
        for(int j=0;j<=30;j++)bin[i][j]=0;
    }
    in=0;
    brr=0;
    tim=0;
    brj=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:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp: In function 'void heavylight(int, int)':
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:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp:44:11: warning: unused variable 'ma' [-Wunused-variable]
   44 |     int w,ma=0;
      |           ^~
jail.cpp: In function 'void add_rv(int)':
jail.cpp:160:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for(int i=0;i<p[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp: In function 'void fill_cycle(int)':
jail.cpp:175:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for(int i=0; i<rp[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~~
jail.cpp: In function 'void find_cycle(int)':
jail.cpp:185:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 158292 KB Output is correct
2 Correct 34 ms 158288 KB Output is correct
3 Correct 34 ms 158476 KB Output is correct
4 Incorrect 83 ms 158288 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 158348 KB Output is correct
2 Correct 33 ms 158456 KB Output is correct
3 Correct 38 ms 158544 KB Output is correct
4 Correct 38 ms 158544 KB Output is correct
5 Correct 38 ms 158552 KB Output is correct
6 Correct 39 ms 158544 KB Output is correct
7 Correct 39 ms 158552 KB Output is correct
8 Correct 39 ms 158556 KB Output is correct
9 Correct 39 ms 158556 KB Output is correct
10 Correct 39 ms 158560 KB Output is correct
11 Correct 37 ms 158544 KB Output is correct
12 Correct 36 ms 158552 KB Output is correct
13 Correct 37 ms 158432 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 158348 KB Output is correct
2 Correct 33 ms 158456 KB Output is correct
3 Correct 38 ms 158544 KB Output is correct
4 Correct 38 ms 158544 KB Output is correct
5 Correct 38 ms 158552 KB Output is correct
6 Correct 39 ms 158544 KB Output is correct
7 Correct 39 ms 158552 KB Output is correct
8 Correct 39 ms 158556 KB Output is correct
9 Correct 39 ms 158556 KB Output is correct
10 Correct 39 ms 158560 KB Output is correct
11 Correct 37 ms 158544 KB Output is correct
12 Correct 36 ms 158552 KB Output is correct
13 Correct 37 ms 158432 KB Output is correct
14 Correct 33 ms 158296 KB Output is correct
15 Correct 34 ms 158312 KB Output is correct
16 Incorrect 40 ms 158556 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 158348 KB Output is correct
2 Correct 33 ms 158456 KB Output is correct
3 Correct 38 ms 158544 KB Output is correct
4 Correct 38 ms 158544 KB Output is correct
5 Correct 38 ms 158552 KB Output is correct
6 Correct 39 ms 158544 KB Output is correct
7 Correct 39 ms 158552 KB Output is correct
8 Correct 39 ms 158556 KB Output is correct
9 Correct 39 ms 158556 KB Output is correct
10 Correct 39 ms 158560 KB Output is correct
11 Correct 37 ms 158544 KB Output is correct
12 Correct 36 ms 158552 KB Output is correct
13 Correct 37 ms 158432 KB Output is correct
14 Correct 33 ms 158296 KB Output is correct
15 Correct 34 ms 158312 KB Output is correct
16 Incorrect 40 ms 158556 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 158348 KB Output is correct
2 Correct 33 ms 158456 KB Output is correct
3 Correct 38 ms 158544 KB Output is correct
4 Correct 38 ms 158544 KB Output is correct
5 Correct 38 ms 158552 KB Output is correct
6 Correct 39 ms 158544 KB Output is correct
7 Correct 39 ms 158552 KB Output is correct
8 Correct 39 ms 158556 KB Output is correct
9 Correct 39 ms 158556 KB Output is correct
10 Correct 39 ms 158560 KB Output is correct
11 Correct 37 ms 158544 KB Output is correct
12 Correct 36 ms 158552 KB Output is correct
13 Correct 37 ms 158432 KB Output is correct
14 Correct 33 ms 158296 KB Output is correct
15 Correct 34 ms 158312 KB Output is correct
16 Incorrect 40 ms 158556 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 158252 KB Output is correct
2 Correct 35 ms 158228 KB Output is correct
3 Correct 35 ms 158288 KB Output is correct
4 Correct 33 ms 158288 KB Output is correct
5 Incorrect 56 ms 158300 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 158292 KB Output is correct
2 Correct 34 ms 158288 KB Output is correct
3 Correct 34 ms 158476 KB Output is correct
4 Incorrect 83 ms 158288 KB Output isn't correct
5 Halted 0 ms 0 KB -