oj.uz

Submission #877295

# Submission time Handle Problem Language Result Execution time Memory
877295 2023-11-23T05:50:30 Z simona1230 Jail (JOI22_jail) C++17
5 / 100
 2217 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;
long long q,n,m;
vector<long long> f[1000001];
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[1000001];// number of the vertex corresponding
long long te[1000001];// to the given tree and segment of the hld
long long dw[1000001];
long long up[1000001];

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

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[1000001];
long long jump[1000001][21];
long long sz[1000001];
long long pos[1000001];// new number of vertex i in original graph
long long chain[1000001];// leader of the chain in which i is
long long maxx[1000001];
long long lvl[1000001];
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(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);
        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);
            c1=c2;
            if(c2==ver)break;
            c1=jump[c1][0];
        }
        c1=y;
        while(1)
        {
            long long c2=chain[c1];
            if(lvl[c2]<lvl[ver])c2=ver;
            update(1,1,n,c2,c1,i);
            c1=c2;
            if(c2==ver)break;
            c1=jump[c1][0];
        }
    }
}
long long used1[1000001];
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[1000001];
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;
}

Compilation message

jail.cpp: In function 'void necessities(long long int, long long int)':
jail.cpp:69: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]
   69 |     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:91: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]
   91 |     for(long long j=0; j<f[i].size(); j++)
      |                        ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(long long int)':
jail.cpp:196: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]
  196 |     for(long long j=0; j<v[i].size(); j++)
      |                        ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(long long int)':
jail.cpp:210: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]
  210 |     for(long long j=0; j<o[i].size(); j++)
      |                        ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 121948 KB Output is correct
2 Correct 25 ms 121928 KB Output is correct
3 Correct 22 ms 121948 KB Output is correct
4 Correct 996 ms 122192 KB Output is correct
5 Correct 2138 ms 122248 KB Output is correct
6 Correct 61 ms 121948 KB Output is correct
7 Correct 61 ms 121944 KB Output is correct
8 Correct 65 ms 121948 KB Output is correct
9 Correct 124 ms 128564 KB Output is correct
10 Correct 155 ms 188872 KB Output is correct
11 Correct 2037 ms 121996 KB Output is correct
12 Correct 2217 ms 122600 KB Output is correct
13 Correct 278 ms 210392 KB Output is correct
14 Correct 276 ms 210888 KB Output is correct
15 Correct 654 ms 231772 KB Output is correct
16 Correct 1226 ms 297740 KB Output is correct
17 Correct 351 ms 241104 KB Output is correct
18 Correct 275 ms 219728 KB Output is correct
19 Correct 346 ms 233748 KB Output is correct
20 Correct 324 ms 233660 KB Output is correct
21 Correct 380 ms 238152 KB Output is correct
22 Correct 207 ms 200788 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 121948 KB Output is correct
2 Correct 21 ms 121948 KB Output is correct
3 Correct 62 ms 121948 KB Output is correct
4 Correct 61 ms 121948 KB Output is correct
5 Runtime error 561 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 121948 KB Output is correct
2 Correct 21 ms 121948 KB Output is correct
3 Correct 62 ms 121948 KB Output is correct
4 Correct 61 ms 121948 KB Output is correct
5 Runtime error 561 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 121948 KB Output is correct
2 Correct 21 ms 121948 KB Output is correct
3 Correct 62 ms 121948 KB Output is correct
4 Correct 61 ms 121948 KB Output is correct
5 Runtime error 561 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 121948 KB Output is correct
2 Correct 21 ms 121948 KB Output is correct
3 Correct 62 ms 121948 KB Output is correct
4 Correct 61 ms 121948 KB Output is correct
5 Runtime error 561 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 121944 KB Output is correct
2 Correct 23 ms 121948 KB Output is correct
3 Correct 25 ms 121944 KB Output is correct
4 Correct 22 ms 121948 KB Output is correct
5 Correct 2193 ms 122192 KB Output is correct
6 Correct 64 ms 121944 KB Output is correct
7 Runtime error 493 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 121948 KB Output is correct
2 Correct 25 ms 121928 KB Output is correct
3 Correct 22 ms 121948 KB Output is correct
4 Correct 996 ms 122192 KB Output is correct
5 Correct 2138 ms 122248 KB Output is correct
6 Correct 61 ms 121948 KB Output is correct
7 Correct 61 ms 121944 KB Output is correct
8 Correct 65 ms 121948 KB Output is correct
9 Correct 124 ms 128564 KB Output is correct
10 Correct 155 ms 188872 KB Output is correct
11 Correct 2037 ms 121996 KB Output is correct
12 Correct 2217 ms 122600 KB Output is correct
13 Correct 278 ms 210392 KB Output is correct
14 Correct 276 ms 210888 KB Output is correct
15 Correct 654 ms 231772 KB Output is correct
16 Correct 1226 ms 297740 KB Output is correct
17 Correct 351 ms 241104 KB Output is correct
18 Correct 275 ms 219728 KB Output is correct
19 Correct 346 ms 233748 KB Output is correct
20 Correct 324 ms 233660 KB Output is correct
21 Correct 380 ms 238152 KB Output is correct
22 Correct 207 ms 200788 KB Output is correct
23 Correct 21 ms 121948 KB Output is correct
24 Correct 21 ms 121948 KB Output is correct
25 Correct 62 ms 121948 KB Output is correct
26 Correct 61 ms 121948 KB Output is correct
27 Runtime error 561 ms 1048576 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -