oj.uz

Submission #879851

# Submission time Handle Problem Language Result Execution time Memory
879851 2023-11-28T08:33:14 Z vivkostov Jail (JOI22_jail) C++14
0 / 100
 140 ms 536388 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][60],level[2000005],usedl[2000005],in;
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;
    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;
    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 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<=55;i++)
    {
        cout<<i<<" | ";
        for(int j=0;j<p[i].size();j++)
        {
            cout<<p[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    for(int i=1;i<=n*10;i++)
    {
        if(!tin[i])conect(i,0);
        //cout<<endl;
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(comp[i]==comp[j]&&i!=j)
            {
                lamp=1;
                cout<<"No"<<endl;
                break;
            }
        }
        if(lamp)break;
    }
    if(!lamp)cout<<"Yes"<<endl;
    for(int i=0;i<=n*20;i++)
    {
        a[i]=0;
        b[i]=0;
        child[i]=0;
        machild[i]=0;
        used[i]=0;
        up[i]=0;
        level[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<=20*n;i++)p[i].clear();
    while(!s.empty())s.pop();
    co=0;
    in=0;
    tim=0;
    lamp=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: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: 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++)
      |                 ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 533844 KB Output is correct
2 Correct 113 ms 533744 KB Output is correct
3 Correct 113 ms 534064 KB Output is correct
4 Incorrect 140 ms 536344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 533984 KB Output is correct
2 Correct 113 ms 533960 KB Output is correct
3 Correct 116 ms 536388 KB Output is correct
4 Incorrect 118 ms 536008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 533984 KB Output is correct
2 Correct 113 ms 533960 KB Output is correct
3 Correct 116 ms 536388 KB Output is correct
4 Incorrect 118 ms 536008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 533984 KB Output is correct
2 Correct 113 ms 533960 KB Output is correct
3 Correct 116 ms 536388 KB Output is correct
4 Incorrect 118 ms 536008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 533984 KB Output is correct
2 Correct 113 ms 533960 KB Output is correct
3 Correct 116 ms 536388 KB Output is correct
4 Incorrect 118 ms 536008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 533904 KB Output is correct
2 Correct 114 ms 533944 KB Output is correct
3 Correct 110 ms 533844 KB Output is correct
4 Correct 114 ms 533988 KB Output is correct
5 Incorrect 128 ms 534248 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 533844 KB Output is correct
2 Correct 113 ms 533744 KB Output is correct
3 Correct 113 ms 534064 KB Output is correct
4 Incorrect 140 ms 536344 KB Output isn't correct
5 Halted 0 ms 0 KB -