oj.uz

Submission #880903

# Submission time Handle Problem Language Result Execution time Memory
880903 2023-11-30T08:26:34 Z vivkostov Jail (JOI22_jail) C++14
5 / 100
 92 ms 164948 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 tin[2000005],low[2000005],tim,lamp,comp[2000005],co,usedr[2000005];
stack<int>s;
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++)
    {
        //cout<<order[i].st<<" "<<order[i].in<<endl;
        if(order[i].st!=0&&usedl[order[i].in]==1)
        {
            fill_cycle(order[i].in);
            //cout<<endl;
            if(brj>=2)
            {
                //cout<<order[i].in<<endl;
                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;
        tin[i]=0;
        low[i]=0;
        comp[i]=0;
        rp[i].clear();
        order[i].in=0;
        order[i].st=0;
        v[i].clear();
        for(int j=0;j<=30;j++)bin[i][j]=0;
    }
    for(int i=0;i<=15*n;i++)p[i].clear();
    while(!s.empty())s.pop();
    in=0;
    brr=0;
    brj=0;
    lamp=0;
    tim=0;
    co=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:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp: In function 'void heavylight(int, int)':
jail.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp:45:11: warning: unused variable 'ma' [-Wunused-variable]
   45 |     int w,ma=0;
      |           ^~
jail.cpp: In function 'void add_rv(int)':
jail.cpp:161:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for(int i=0;i<p[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp: In function 'void fill_cycle(int)':
jail.cpp:176:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |     for(int i=0; i<rp[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~~
jail.cpp: In function 'void find_cycle(int)':
jail.cpp:186:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164624 KB Output is correct
2 Correct 36 ms 164520 KB Output is correct
3 Correct 35 ms 164432 KB Output is correct
4 Incorrect 92 ms 164948 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 34 ms 164624 KB Output is correct
2 Correct 41 ms 164444 KB Output is correct
3 Correct 41 ms 164700 KB Output is correct
4 Correct 39 ms 164612 KB Output is correct
5 Correct 39 ms 164700 KB Output is correct
6 Correct 40 ms 164692 KB Output is correct
7 Correct 44 ms 164700 KB Output is correct
8 Correct 46 ms 164688 KB Output is correct
9 Correct 40 ms 164760 KB Output is correct
10 Correct 40 ms 164688 KB Output is correct
11 Correct 40 ms 164700 KB Output is correct
12 Correct 38 ms 164692 KB Output is correct
13 Correct 36 ms 164700 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 164624 KB Output is correct
2 Correct 41 ms 164444 KB Output is correct
3 Correct 41 ms 164700 KB Output is correct
4 Correct 39 ms 164612 KB Output is correct
5 Correct 39 ms 164700 KB Output is correct
6 Correct 40 ms 164692 KB Output is correct
7 Correct 44 ms 164700 KB Output is correct
8 Correct 46 ms 164688 KB Output is correct
9 Correct 40 ms 164760 KB Output is correct
10 Correct 40 ms 164688 KB Output is correct
11 Correct 40 ms 164700 KB Output is correct
12 Correct 38 ms 164692 KB Output is correct
13 Correct 36 ms 164700 KB Output is correct
14 Correct 36 ms 164392 KB Output is correct
15 Correct 35 ms 164444 KB Output is correct
16 Incorrect 44 ms 164692 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 164624 KB Output is correct
2 Correct 41 ms 164444 KB Output is correct
3 Correct 41 ms 164700 KB Output is correct
4 Correct 39 ms 164612 KB Output is correct
5 Correct 39 ms 164700 KB Output is correct
6 Correct 40 ms 164692 KB Output is correct
7 Correct 44 ms 164700 KB Output is correct
8 Correct 46 ms 164688 KB Output is correct
9 Correct 40 ms 164760 KB Output is correct
10 Correct 40 ms 164688 KB Output is correct
11 Correct 40 ms 164700 KB Output is correct
12 Correct 38 ms 164692 KB Output is correct
13 Correct 36 ms 164700 KB Output is correct
14 Correct 36 ms 164392 KB Output is correct
15 Correct 35 ms 164444 KB Output is correct
16 Incorrect 44 ms 164692 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 164624 KB Output is correct
2 Correct 41 ms 164444 KB Output is correct
3 Correct 41 ms 164700 KB Output is correct
4 Correct 39 ms 164612 KB Output is correct
5 Correct 39 ms 164700 KB Output is correct
6 Correct 40 ms 164692 KB Output is correct
7 Correct 44 ms 164700 KB Output is correct
8 Correct 46 ms 164688 KB Output is correct
9 Correct 40 ms 164760 KB Output is correct
10 Correct 40 ms 164688 KB Output is correct
11 Correct 40 ms 164700 KB Output is correct
12 Correct 38 ms 164692 KB Output is correct
13 Correct 36 ms 164700 KB Output is correct
14 Correct 36 ms 164392 KB Output is correct
15 Correct 35 ms 164444 KB Output is correct
16 Incorrect 44 ms 164692 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 164536 KB Output is correct
2 Correct 34 ms 164444 KB Output is correct
3 Correct 37 ms 164432 KB Output is correct
4 Correct 37 ms 164444 KB Output is correct
5 Incorrect 68 ms 164836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164624 KB Output is correct
2 Correct 36 ms 164520 KB Output is correct
3 Correct 35 ms 164432 KB Output is correct
4 Incorrect 92 ms 164948 KB Output isn't correct
5 Halted 0 ms 0 KB -