oj.uz

Submission #877612

# Submission time Handle Problem Language Result Execution time Memory
877612 2023-11-23T11:05:23 Z simona1230 Jail (JOI22_jail) C++17
0 / 100
 4932 ms 285268 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxver=1e6;
const int maxn=4*120005;
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);
    }
    cin>>m;
}

int num;
int ts[4*maxn];
int te[4*maxn];
int dw[maxn];
int up[maxn];

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

void add_edge(int x,int y)
{
    v[x].push_back(y);
    o[y].push_back(x);
}

void make_tree(int i,int l,int r)
{
    if(l==r)
    {
        ts[i]=num++;
        te[i]=num++;
        dw[l]=ts[i];
        up[l]=te[i];
        return;
    }

    ts[i]=num++;
    te[i]=num++;

    int mid=(l+r)/2;

    make_tree(i*2,l,mid);
    make_tree(i*2+1,mid+1,r);

    add_edge(ts[i],ts[i*2]);
    add_edge(ts[i],ts[i*2+1]);
    add_edge(te[i*2],te[i]);
    add_edge(te[i*2+1],te[i]);
}

int used[maxn];
int sz[maxn];

void size_(int i)
{
    used[i]=1;
    sz[i]=1;
    for(int j=0; j<f[i].size(); j++)
    {
        int nb=f[i][j];
        if(!used[nb])
        {
            size_(nb);
            sz[i]+=sz[nb];
        }
    }
}

int jump[maxn][21];

int pos[maxn];
int chain[maxn];
int lvl[maxn];
int cnt=1;

void hld(int i,int lead,int level,int par)
{
    pos[i]=cnt++;
    chain[i]=lead;
    lvl[i]=level;

    int maxx=0,big=0;
    for(int j=0; j<f[i].size(); j++)
    {
        int nb=f[i][j];
        if(sz[nb]>maxx&&nb!=par)
        {
            maxx=sz[nb];
            big=nb;
        }
    }

    if(big)
    {
        //cout<<"here "<<i<<" "<<lead<<" "<<ver<<endl;
        hld(big,lead,level+1,i);
        jump[big][0]=i;
    }

    for(int j=0; j<f[i].size(); j++)
    {
        int nb=f[i][j];
        if(nb!=big&&nb!=par)
        {
            hld(nb,nb,level+1,i);
            jump[nb][0]=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];
}

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);
    x=make_jump(x,abs(lvl[x]-lvl[y]));
    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||r<ql||l>qr)return;

    if(ql<=l&&r<=qr)
    {
        add_edge(pr,ts[i]);
        add_edge(te[i],pr);
        return;
    }

    int mid=(l+r)/2;
    update(i*2,l,mid,ql,qr,pr);
    update(i*2+1,mid+1,r,ql,qr,pr);
}
void make_graph()
{
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;
        add_edge(dw[x],i);
        add_edge(i,up[y]);

        int st,lca_=lca(x,y);

        st=x;
        while(true)
        {
            int ed=chain[st];
            if(lvl[ed]<lvl[lca_])ed=lca_;
            update(1,1,n,pos[ed],pos[st],i);
            if(ed==lca_)break;
            st=jump[ed][0];
        }

        st=y;
        while(true)
        {
            int ed=chain[st];
            if(lvl[ed]<lvl[lca_])ed=lca_;
            update(1,1,n,pos[ed],pos[st],i);
            if(ed==lca_)break;
            st=jump[ed][0];
        }
    }
}

stack<int> topo;
int used1[maxn];
int used2[maxn];

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);
    }
    topo.push(i);
}

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()
{
    for(int i=1; i<=m; i++)
        if(!used1[i])dfs1(i);

    int comp=0;
    while(topo.size())
    {
        int ver=topo.top();
        topo.pop();
        if(ver<=m&&!used2[ver])
        {
            comp++;
            dfs2(ver);
        }
    }

    if(comp==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--)
    {
        read();

        for(int i=1; i<maxver; i++)
        {
            v[i].clear();
            o[i].clear();
        }
        memset(used,0,sizeof(used));
        memset(pos,0,sizeof(pos));
        memset(used1,0,sizeof(used1));
        memset(used2,0,sizeof(used2));
        memset(chain,0,sizeof(chain));
        memset(ts,0,sizeof(ts));
        memset(te,0,sizeof(te));
        memset(sz,0,sizeof(sz));
        memset(dw,0,sizeof(dw));
        memset(up,0,sizeof(up));
        memset(lvl,0,sizeof(lvl));
        for(int i=1; i<=n; i++)
            for(int j=0; j<=20; j++)
                jump[i][j]=0;

        size_(1);
        cnt=1;
        hld(1,1,1,-1);
        prec();
        num=m+1;
        make_tree(1,1,n);
        make_graph();
        check();
    }
    return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 93016 KB Output is correct
2 Correct 31 ms 93020 KB Output is correct
3 Correct 22 ms 93020 KB Output is correct
4 Correct 2383 ms 93520 KB Output is correct
5 Correct 4926 ms 93288 KB Output is correct
6 Correct 114 ms 93240 KB Output is correct
7 Correct 118 ms 93020 KB Output is correct
8 Correct 117 ms 93268 KB Output is correct
9 Correct 165 ms 96592 KB Output is correct
10 Runtime error 197 ms 285268 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 93016 KB Output is correct
2 Correct 21 ms 93020 KB Output is correct
3 Correct 116 ms 93148 KB Output is correct
4 Incorrect 115 ms 93196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 93016 KB Output is correct
2 Correct 21 ms 93020 KB Output is correct
3 Correct 116 ms 93148 KB Output is correct
4 Incorrect 115 ms 93196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 93016 KB Output is correct
2 Correct 21 ms 93020 KB Output is correct
3 Correct 116 ms 93148 KB Output is correct
4 Incorrect 115 ms 93196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 93016 KB Output is correct
2 Correct 21 ms 93020 KB Output is correct
3 Correct 116 ms 93148 KB Output is correct
4 Incorrect 115 ms 93196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 93016 KB Output is correct
2 Correct 27 ms 93020 KB Output is correct
3 Correct 31 ms 93156 KB Output is correct
4 Correct 21 ms 93020 KB Output is correct
5 Correct 4932 ms 93156 KB Output is correct
6 Correct 118 ms 93268 KB Output is correct
7 Incorrect 120 ms 93212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 93016 KB Output is correct
2 Correct 31 ms 93020 KB Output is correct
3 Correct 22 ms 93020 KB Output is correct
4 Correct 2383 ms 93520 KB Output is correct
5 Correct 4926 ms 93288 KB Output is correct
6 Correct 114 ms 93240 KB Output is correct
7 Correct 118 ms 93020 KB Output is correct
8 Correct 117 ms 93268 KB Output is correct
9 Correct 165 ms 96592 KB Output is correct
10 Runtime error 197 ms 285268 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -