Submission #877913

#	Time	Username	Problem	Language	Result	Execution time	Memory
877913		vivkostov	Jail (JOI22_jail)	C++14	0 / 100	128 ms	59384 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,in,brr,a[200005],b[200005],child[200005],machild[200005],used[200005],up[200005],bin[200005][30],level[200005],usedl[200005];
vector<int>v[200005],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++;
    used[beg]=in;
    if(!last)last=used[beg];
    up[beg]=last;
    int w;
    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+m].push_back(h*2+m);
    p[h+m].push_back(h*2+1+m);
    make_start(l,mid,h*2);
    make_start(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+m].push_back(to);
        if(type==2)p[to].push_back(h+m);
        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);
    }
}
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,2);
        return;
    }
    if(level[up[beg]]>level[lc])
    {
        update(1,n,used[up[beg]],used[beg],1,prisoner,2);
        go_up_heavy1(bin[up[beg]][0],lc,prisoner);
        return;
    }
    update(1,n,used[lc],used[beg],1,prisoner,2);
}
void go_up_heavy2(int beg,int lc,int prisoner)
{
    if(beg==lc)return;
    if(level[used[up[beg]]]==level[lc])
    {
        update(1,n,used[up[beg]]+1,used[beg],1,prisoner,2);
        return;
    }
    if(level[up[beg]]>level[lc])
    {
        update(1,n,used[up[beg]],used[beg],1,prisoner,2);
        go_up_heavy2(bin[up[beg]][0],lc,prisoner);
        return;
    }
    update(1,n,used[lc]+1,used[beg],1,prisoner,2);
}
void add_path()
{
    for(int i=1; i<=m; i++)
    {
        int g=lca(a[i],b[i]);
        //cout<<used[a[i]]<<" "<<used[b[i]]<<endl;
        go_up_heavy1(a[i],g,i);
        go_up_heavy2(b[i],g,i);
    }
}
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);
    add_all();
    make_bin();
    add_path();
    /*for(int i=1;i<=35;i++)
    {
        cout<<i<<" | ";
        for(int j=0;j<p[i].size();j++)
        {
            cout<<p[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    for(int i=1; i<=m; i++)
    {
        if(!usedl[i])find_cycle(i);
    }
    if(brr!=m)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(child,0,sizeof(child));
    memset(machild,0,sizeof(machild));
    memset(used,0,sizeof(used));
    memset(up,0,sizeof(up));
    memset(level,0,sizeof(level));
    memset(usedl,0,sizeof(usedl));
    for(int i=0; i<=n*10; i++)
    {
        v[i].clear();
        for(int j=0; j<=25; j++)bin[i][j]=0;
    }
    for(int i=0; i<=20*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 (stderr)

jail.cpp: In function 'void find_child(int, int, int)':
jail.cpp:18:19: 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:19: 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:19: 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: In function 'void fill_cycle(int)':
jail.cpp:153:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
jail.cpp: In function 'void find_cycle(int)':
jail.cpp:163:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~

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