Submission #879887

#	Time	Username	Problem	Language	Result	Execution time	Memory
879887		vivkostov	Jail (JOI22_jail)	C++14	54 / 100	973 ms	672948 KiB

jail

#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][60],level[2000005],usedl[2000005],in,brr,brj;
vector<int>v[2000005],p[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);
    }
}
int tin[2000005],low[2000005],tim,lamp,comp[2000005],co;
stack<int>s;
void conect(int beg,int par)
{
    tim++;
    tin[beg]=tim;
    low[beg]=tim;
    s.push(beg);
    int w;
    for(int i=0;i<p[beg].size();i++)
    {
        w=p[beg][i];
        if(tin[w]==-1)continue;
        if(!tin[w])
        {
            conect(w,beg);
            low[beg]=min(low[beg],low[w]);
        }
        if(par!=w)low[beg]=min(low[beg],low[w]);
    }
    if(low[beg]==tin[beg])
    {
        co++;
        while(s.top()!=beg)
        {
            //cout<<s.top()<<" ";
            tin[s.top()]=-1;
            comp[s.top()]=co;
            s.pop();
        }
        //cout<<s.top()<<" ";
        tin[s.top()]=-1;
        comp[s.top()]=co;
        s.pop();
        //cout<<endl;
    }
}
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]==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);
    }
    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*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;
        tin[i]=0;
        low[i]=0;
        comp[i]=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 (stderr)

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:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp:34:11: warning: unused variable 'ma' [-Wunused-variable]
   34 |     int w,ma=0;
      |           ^~
jail.cpp: In function 'void conect(int, int)':
jail.cpp:155:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for(int i=0;i<p[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp: In function 'void fill_cycle(int)':
jail.cpp:188:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
jail.cpp: In function 'void find_cycle(int)':
jail.cpp:198:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23