Submission #877311

#	Time	Username	Problem	Language	Result	Execution time	Memory
877311		simona1230	Jail (JOI22_jail)	C++17	0 / 100	5048 ms	1048576 KiB

jail

#include <bits/stdc++.h>

using namespace std;
const int maxn=4*1e6;
long long q,n,m;
vector<long long> f[maxn];
void read()
{
    cin>>n;
    for(long long i=1; i<=n; i++)
        f[i].clear();
    for(long long i=1; i<n; i++)
    {
        long long x,y;
        cin>>x>>y;
        f[x].push_back(y);
        f[y].push_back(x);
    }
}
long long num;
long long ts[maxn];// number of the vertex corresponding
long long te[maxn];// to the given tree and segment of the hld
long long dw[maxn];
long long up[maxn];

vector<long long> v[maxn],o[maxn];

void make_tree(long long i,long long l,long long r)
{
    if(l==r)
    {
        ts[i]=num++;
        dw[l]=ts[i];
        te[i]=num++;
        up[l]=te[i];
        //cout<<l<<" "<<r<<" "<<te[i]<<endl;
        return;
    }
    long long mid=(l+r)/2;
    ts[i]=num++;
    te[i]=num++;
    //cout<<l<<" "<<r<<" "<<te[i]<<endl;
    make_tree(i*2,l,mid);
    make_tree(i*2+1,mid+1,r);
    long long il=ts[i*2];
    long long ir=ts[i*2+1];
    v[ts[i]].push_back(il);
    v[ts[i]].push_back(ir);
    o[il].push_back(ts[i]);
    o[ir].push_back(ts[i]);
    il=te[i*2];
    ir=te[i*2+1];
    v[il].push_back(te[i]);
    v[ir].push_back(te[i]);
    o[te[i]].push_back(il);
    o[te[i]].push_back(ir);
}

long long used[maxn];
long long jump[1000001][21];
long long sz[maxn];
long long pos[maxn];// new number of vertex i in original graph
long long chain[maxn];// leader of the chain in which i is
long long maxx[maxn];
long long lvl[maxn];
void necessities(long long i,long long h)
{
    sz[i]=1;
    used[i]=1;
    for(long long j=0; j<f[i].size(); j++)
    {
        long long nb=f[i][j];
        if(!used[nb])
        {
            necessities(nb,h+1);
            sz[i]+=sz[nb];
            if(sz[maxx[i]]<sz[nb])maxx[i]=nb;
        }
    }
}
long long cnt=1;
void hld(long long i,long long lead,int h)
{
    pos[i]=cnt++;
    chain[pos[i]]=pos[lead];
    lvl[pos[i]]=h;
    if(maxx[i])
    {
        hld(maxx[i],lead,h+1);
        jump[pos[maxx[i]]][0]=pos[i];
    }
    for(long long j=0; j<f[i].size(); j++)
    {
        long long nb=f[i][j];
        if(pos[nb]==0)
        {
            hld(nb,nb,h+1);
            jump[pos[nb]][0]=pos[i];
        }
    }
}
void prec()
{
    for(long long j=1; j<=20; j++)
    {
        for(long long i=1; i<=n; i++)
        {
            jump[i][j]=jump[jump[i][j-1]][j-1];
            //cout<<i<<" "<<j<<" "<<jump[i][j]<<endl;
        }
    }
}
long long make_jump(long long x,long long k)
{
    for(long long i=20; i>=0; i--)
        if(k&(1<<i))
            x=jump[x][i];
    return x;
}
long long lca(long long x,long long y)
{
    if(lvl[x]>lvl[y])swap(x,y);
    y=make_jump(y,abs(lvl[y]-lvl[x]));
    //cout<<x<<" "<<y<<endl;
    if(x==y)return x;
    for(long long i=20; i>=0; i--)
    {
        if(jump[x][i]!=jump[y][i])
        {
            x=jump[x][i];
            y=jump[y][i];
        }
    }
    return jump[x][0];
}
void update(long long i,long long l,long long r,long long ql,long long qr,long long pr)
{
    if(ql>qr)return;
    if(ql<=l&&r<=qr)
    {
        //cout<<l<<"-"<<r<<endl;
        long long idx=ts[i];
        //cout<<idx<<endl;
        v[pr].push_back(idx);
        o[idx].push_back(pr);
        idx=te[i];
        //cout<<idx<<endl;
        v[idx].push_back(pr);
        o[pr].push_back(idx);
        return;
    }
    long long mid=(l+r)/2;
    update(i*2,l,mid,ql,min(mid,qr),pr);
    update(i*2+1,mid+1,r,max(ql,mid+1),qr,pr);
}
void make_graph()
{
    /*for(int i=1;i<=n;i++)
        cout<<chain[i]<<" ";
    cout<<endl;*/
    for(long long i=1; i<=m; i++)
    {
        long long x,y;
        cin>>x>>y;
        x=pos[x];
        y=pos[y];
        //cout<<i<<" "<<dw[pos[x]]<<" "<<up[pos[y]]<<endl;
        v[dw[x]].push_back(i);
        o[i].push_back(dw[x]);
        v[i].push_back(up[y]);
        o[up[y]].push_back(i);
        long long ver=lca(x,y);
        //cout<<ver<<endl;
        long long c1=x;
        while(1)
        {
            long long c2=chain[c1];
            if(lvl[c2]<lvl[ver])c2=ver;
            update(1,1,n,c2,c1,i);
            //cout<<c2<<" "<<c1<<endl;
            if(c2==ver)break;
            c1=jump[c2][0];
        }
        c1=y;
        while(1)
        {
            long long c2=chain[c1];
            if(lvl[c2]<lvl[ver])c2=ver;
            update(1,1,n,c2,c1,i);
            //cout<<c2<<" "<<c1<<endl;
            if(c2==ver)break;
            c1=jump[c2][0];
        }
    }
}
long long used1[maxn];
stack<long long> st;
void dfs1(long long i)
{
    used1[i]=1;
    for(long long j=0; j<v[i].size(); j++)
    {
        long long nb=v[i][j];
        if(!used1[nb])
        {
            dfs1(nb);
        }
    }
    st.push(i);
}
long long used2[maxn];
void dfs2(long long i)
{
    used2[i]=1;
    for(long long j=0; j<o[i].size(); j++)
    {
        long long nb=o[i][j];
        if(!used2[nb])
        {
            dfs2(nb);
        }
    }
}
void check()
{
    memset(used1,0,sizeof(used1));
    memset(used2,0,sizeof(used2));
    for(long long i=1;i<=m;i++)
    {
        if(!used1[i])dfs1(i);
    }
    long long cnt=0;
    while(st.size())
    {
        long long vr=st.top();
        st.pop();
        if(vr<=m&&!used2[vr])
        {
            cnt++;
            dfs2(vr);
        }
    }
    if(cnt==m)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>q;
    while(q--)
    {
        for(long long i=1; i<=num; i++)
        {
            o[i].clear();
            v[i].clear();
        }
        memset(maxx,0,sizeof(maxx));
        memset(used,0,sizeof(used));
        read();
        cnt=1;
        necessities(1,1);
        hld(1,1,1);
        prec();
        cin>>m;
        num=m+1;
        make_tree(1,1,n);
        make_graph();
        /*for(long long i=1;i<num;i++)
        {
            cout<<i<<": ";
            for(long long j=0;j<v[i].size();j++)
                cout<<v[i][j]<<" ";
            cout<<endl;
        }*/
        check();
    }
    return 0;
}
/*
1
8
1 7
1 8
8 3
3 2
7 6
7 5
5 4
*/

Compilation message (stderr)

jail.cpp: In function 'void necessities(long long int, long long int)':
jail.cpp:70:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(long long j=0; j<f[i].size(); j++)
      |                        ~^~~~~~~~~~~~
jail.cpp: In function 'void hld(long long int, long long int, int)':
jail.cpp:92:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(long long j=0; j<f[i].size(); j++)
      |                        ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(long long int)':
jail.cpp:201:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |     for(long long j=0; j<v[i].size(); j++)
      |                        ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(long long int)':
jail.cpp:215:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |     for(long long j=0; j<o[i].size(); j++)
      |                        ~^~~~~~~~~~~~

• 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