oj.uz

Submission #877314

# Submission time Handle Problem Language Result Execution time Memory
877314 2023-11-23T06:16:53 Z simona1230 Jail (JOI22_jail) C++17
5 / 100
 4445 ms 1048576 KB 
#include <bits/stdc++.h>

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

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

void make_tree(int i,int l,int 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;
    }
    int 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);
    int il=ts[i*2];
    int 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);
}

int used[maxn];
int jump[maxn][21];
int sz[maxn];
int pos[maxn];// new number of vertex i in original graph
int chain[maxn];// leader of the chain in which i is
int maxx[maxn];
int lvl[maxn];
void necessities(int i,int h)
{
    sz[i]=1;
    used[i]=1;
    for(int j=0; j<f[i].size(); j++)
    {
        int nb=f[i][j];
        if(!used[nb])
        {
            necessities(nb,h+1);
            sz[i]+=sz[nb];
            if(sz[maxx[i]]<sz[nb])maxx[i]=nb;
        }
    }
}
int cnt=1;
void hld(int i,int 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(int j=0; j<f[i].size(); j++)
    {
        int nb=f[i][j];
        if(pos[nb]==0)
        {
            hld(nb,nb,h+1);
            jump[pos[nb]][0]=pos[i];
        }
    }
}
void prec()
{
    for(int j=1; j<=20; j++)
    {
        for(int i=1; i<=n; i++)
        {
            jump[i][j]=jump[jump[i][j-1]][j-1];
            //cout<<i<<" "<<j<<" "<<jump[i][j]<<endl;
        }
    }
}
int make_jump(int x,int k)
{
    for(int i=20; i>=0; i--)
        if(k&(1<<i))
            x=jump[x][i];
    return x;
}
int lca(int x,int 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(int 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(int i,int l,int r,int ql,int qr,int pr)
{
    if(ql>qr)return;
    if(ql<=l&&r<=qr)
    {
        //cout<<l<<"-"<<r<<endl;
        int 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;
    }
    int 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(int i=1; i<=m; i++)
    {
        int 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);
        int ver=lca(x,y);
        //cout<<ver<<endl;
        int c1=x;
        while(1)
        {
            int 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)
        {
            int 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];
        }
    }
}
int used1[maxn];
stack<int> st;
void dfs1(int i)
{
    used1[i]=1;
    for(int j=0; j<v[i].size(); j++)
    {
        int nb=v[i][j];
        if(!used1[nb])
        {
            dfs1(nb);
        }
    }
    st.push(i);
}
int used2[maxn];
void dfs2(int i)
{
    used2[i]=1;
    for(int j=0; j<o[i].size(); j++)
    {
        int nb=o[i][j];
        if(!used2[nb])
        {
            dfs2(nb);
        }
    }
}
void check()
{
    memset(used1,0,sizeof(used1));
    memset(used2,0,sizeof(used2));
    for(int i=1;i<=m;i++)
    {
        if(!used1[i])dfs1(i);
    }
    int cnt=0;
    while(st.size())
    {
        int 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(int 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(int i=1;i<num;i++)
        {
            cout<<i<<": ";
            for(int 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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 363688 KB Output is correct
2 Correct 79 ms 363600 KB Output is correct
3 Correct 69 ms 363600 KB Output is correct
4 Correct 2052 ms 363888 KB Output is correct
5 Correct 4418 ms 363892 KB Output is correct
6 Correct 153 ms 363808 KB Output is correct
7 Correct 156 ms 363860 KB Output is correct
8 Correct 155 ms 364400 KB Output is correct
9 Correct 217 ms 369316 KB Output is correct
10 Correct 173 ms 416568 KB Output is correct
11 Correct 4346 ms 364224 KB Output is correct
12 Correct 4445 ms 365124 KB Output is correct
13 Correct 289 ms 428248 KB Output is correct
14 Correct 334 ms 428724 KB Output is correct
15 Correct 626 ms 438280 KB Output is correct
16 Correct 1168 ms 476280 KB Output is correct
17 Correct 364 ms 444192 KB Output is correct
18 Correct 306 ms 438100 KB Output is correct
19 Correct 344 ms 440484 KB Output is correct
20 Correct 333 ms 440216 KB Output is correct
21 Correct 387 ms 442620 KB Output is correct
22 Correct 265 ms 425296 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 363604 KB Output is correct
2 Correct 75 ms 363600 KB Output is correct
3 Correct 151 ms 363856 KB Output is correct
4 Correct 152 ms 363860 KB Output is correct
5 Runtime error 481 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 70 ms 363604 KB Output is correct
2 Correct 75 ms 363600 KB Output is correct
3 Correct 151 ms 363856 KB Output is correct
4 Correct 152 ms 363860 KB Output is correct
5 Runtime error 481 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 70 ms 363604 KB Output is correct
2 Correct 75 ms 363600 KB Output is correct
3 Correct 151 ms 363856 KB Output is correct
4 Correct 152 ms 363860 KB Output is correct
5 Runtime error 481 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 70 ms 363604 KB Output is correct
2 Correct 75 ms 363600 KB Output is correct
3 Correct 151 ms 363856 KB Output is correct
4 Correct 152 ms 363860 KB Output is correct
5 Runtime error 481 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 69 ms 363604 KB Output is correct
2 Correct 75 ms 363676 KB Output is correct
3 Correct 77 ms 363600 KB Output is correct
4 Correct 71 ms 363600 KB Output is correct
5 Correct 4388 ms 363852 KB Output is correct
6 Correct 156 ms 363920 KB Output is correct
7 Runtime error 446 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 72 ms 363688 KB Output is correct
2 Correct 79 ms 363600 KB Output is correct
3 Correct 69 ms 363600 KB Output is correct
4 Correct 2052 ms 363888 KB Output is correct
5 Correct 4418 ms 363892 KB Output is correct
6 Correct 153 ms 363808 KB Output is correct
7 Correct 156 ms 363860 KB Output is correct
8 Correct 155 ms 364400 KB Output is correct
9 Correct 217 ms 369316 KB Output is correct
10 Correct 173 ms 416568 KB Output is correct
11 Correct 4346 ms 364224 KB Output is correct
12 Correct 4445 ms 365124 KB Output is correct
13 Correct 289 ms 428248 KB Output is correct
14 Correct 334 ms 428724 KB Output is correct
15 Correct 626 ms 438280 KB Output is correct
16 Correct 1168 ms 476280 KB Output is correct
17 Correct 364 ms 444192 KB Output is correct
18 Correct 306 ms 438100 KB Output is correct
19 Correct 344 ms 440484 KB Output is correct
20 Correct 333 ms 440216 KB Output is correct
21 Correct 387 ms 442620 KB Output is correct
22 Correct 265 ms 425296 KB Output is correct
23 Correct 70 ms 363604 KB Output is correct
24 Correct 75 ms 363600 KB Output is correct
25 Correct 151 ms 363856 KB Output is correct
26 Correct 152 ms 363860 KB Output is correct
27 Runtime error 481 ms 1048576 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -