oj.uz

Submission #877668

# Submission time Handle Problem Language Result Execution time Memory
877668 2023-11-23T12:28:44 Z simona1230 Jail (JOI22_jail) C++17
21 / 100
 4974 ms 284084 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++;
        //cout<<ts[i]<<" "<<te[i]<<" "<<l<<" "<<r<<endl;
        dw[l]=ts[i];
        up[l]=te[i];
        return;
    }

    ts[i]=num++;
    te[i]=num++;
    //cout<<ts[i]<<" "<<te[i]<<" "<<l<<" "<<r<<endl;
    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[pos[x]],i);
        add_edge(i,up[pos[y]]);

        int st,lca_=lca(x,y);
        //cout<<lca_<<endl;

        st=x;
        while(true)
        {
            int ed=chain[st];
            if(lvl[ed]<lvl[lca_])ed=lca_;
            update(1,1,n,pos[ed],pos[st],i);
            //cout<<pos[ed]<<" "<<pos[st]<<endl;
            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);
            //cout<<pos[ed]<<" "<<pos[st]<<endl;
            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();
        /*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
6
2 4
4 1
1 5
5 3
3 6
2
2 3
6 1
*/

Compilation message

jail.cpp: In function 'void size_(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, int)':
jail.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int j=0; j<f[i].size(); j++)
      |                  ~^~~~~~~~~~~~
jail.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int j=0; j<f[i].size(); j++)
      |                  ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(int)':
jail.cpp:213:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(int)':
jail.cpp:225:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |     for(int j=0; j<o[i].size(); j++)
      |                  ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 93020 KB Output is correct
2 Correct 32 ms 93016 KB Output is correct
3 Correct 23 ms 93020 KB Output is correct
4 Correct 2310 ms 93180 KB Output is correct
5 Correct 4974 ms 93176 KB Output is correct
6 Correct 115 ms 93016 KB Output is correct
7 Correct 114 ms 93016 KB Output is correct
8 Correct 119 ms 93240 KB Output is correct
9 Correct 162 ms 95312 KB Output is correct
10 Runtime error 219 ms 284084 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 93016 KB Output is correct
2 Correct 20 ms 93020 KB Output is correct
3 Correct 123 ms 93020 KB Output is correct
4 Correct 118 ms 93224 KB Output is correct
5 Correct 116 ms 93020 KB Output is correct
6 Correct 117 ms 93020 KB Output is correct
7 Correct 119 ms 93224 KB Output is correct
8 Correct 118 ms 93220 KB Output is correct
9 Correct 119 ms 93232 KB Output is correct
10 Correct 114 ms 93228 KB Output is correct
11 Correct 100 ms 93460 KB Output is correct
12 Correct 117 ms 93020 KB Output is correct
13 Correct 112 ms 93016 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 93016 KB Output is correct
2 Correct 20 ms 93020 KB Output is correct
3 Correct 123 ms 93020 KB Output is correct
4 Correct 118 ms 93224 KB Output is correct
5 Correct 116 ms 93020 KB Output is correct
6 Correct 117 ms 93020 KB Output is correct
7 Correct 119 ms 93224 KB Output is correct
8 Correct 118 ms 93220 KB Output is correct
9 Correct 119 ms 93232 KB Output is correct
10 Correct 114 ms 93228 KB Output is correct
11 Correct 100 ms 93460 KB Output is correct
12 Correct 117 ms 93020 KB Output is correct
13 Correct 112 ms 93016 KB Output is correct
14 Correct 26 ms 92932 KB Output is correct
15 Correct 30 ms 93140 KB Output is correct
16 Correct 115 ms 93016 KB Output is correct
17 Correct 114 ms 93236 KB Output is correct
18 Correct 114 ms 93240 KB Output is correct
19 Correct 111 ms 93016 KB Output is correct
20 Correct 114 ms 93236 KB Output is correct
21 Correct 112 ms 93232 KB Output is correct
22 Correct 111 ms 93240 KB Output is correct
23 Correct 112 ms 93012 KB Output is correct
24 Correct 112 ms 93256 KB Output is correct
25 Correct 117 ms 93016 KB Output is correct
26 Correct 111 ms 93152 KB Output is correct
27 Correct 113 ms 93228 KB Output is correct
28 Correct 111 ms 93016 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 93016 KB Output is correct
2 Correct 20 ms 93020 KB Output is correct
3 Correct 123 ms 93020 KB Output is correct
4 Correct 118 ms 93224 KB Output is correct
5 Correct 116 ms 93020 KB Output is correct
6 Correct 117 ms 93020 KB Output is correct
7 Correct 119 ms 93224 KB Output is correct
8 Correct 118 ms 93220 KB Output is correct
9 Correct 119 ms 93232 KB Output is correct
10 Correct 114 ms 93228 KB Output is correct
11 Correct 100 ms 93460 KB Output is correct
12 Correct 117 ms 93020 KB Output is correct
13 Correct 112 ms 93016 KB Output is correct
14 Correct 26 ms 92932 KB Output is correct
15 Correct 30 ms 93140 KB Output is correct
16 Correct 115 ms 93016 KB Output is correct
17 Correct 114 ms 93236 KB Output is correct
18 Correct 114 ms 93240 KB Output is correct
19 Correct 111 ms 93016 KB Output is correct
20 Correct 114 ms 93236 KB Output is correct
21 Correct 112 ms 93232 KB Output is correct
22 Correct 111 ms 93240 KB Output is correct
23 Correct 112 ms 93012 KB Output is correct
24 Correct 112 ms 93256 KB Output is correct
25 Correct 117 ms 93016 KB Output is correct
26 Correct 111 ms 93152 KB Output is correct
27 Correct 113 ms 93228 KB Output is correct
28 Correct 111 ms 93016 KB Output is correct
29 Correct 115 ms 93280 KB Output is correct
30 Correct 122 ms 93296 KB Output is correct
31 Correct 118 ms 93268 KB Output is correct
32 Correct 115 ms 93268 KB Output is correct
33 Correct 116 ms 93016 KB Output is correct
34 Correct 125 ms 93268 KB Output is correct
35 Correct 114 ms 93272 KB Output is correct
36 Correct 116 ms 93264 KB Output is correct
37 Incorrect 115 ms 93016 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 93016 KB Output is correct
2 Correct 20 ms 93020 KB Output is correct
3 Correct 123 ms 93020 KB Output is correct
4 Correct 118 ms 93224 KB Output is correct
5 Correct 116 ms 93020 KB Output is correct
6 Correct 117 ms 93020 KB Output is correct
7 Correct 119 ms 93224 KB Output is correct
8 Correct 118 ms 93220 KB Output is correct
9 Correct 119 ms 93232 KB Output is correct
10 Correct 114 ms 93228 KB Output is correct
11 Correct 100 ms 93460 KB Output is correct
12 Correct 117 ms 93020 KB Output is correct
13 Correct 112 ms 93016 KB Output is correct
14 Correct 26 ms 92932 KB Output is correct
15 Correct 30 ms 93140 KB Output is correct
16 Correct 115 ms 93016 KB Output is correct
17 Correct 114 ms 93236 KB Output is correct
18 Correct 114 ms 93240 KB Output is correct
19 Correct 111 ms 93016 KB Output is correct
20 Correct 114 ms 93236 KB Output is correct
21 Correct 112 ms 93232 KB Output is correct
22 Correct 111 ms 93240 KB Output is correct
23 Correct 112 ms 93012 KB Output is correct
24 Correct 112 ms 93256 KB Output is correct
25 Correct 117 ms 93016 KB Output is correct
26 Correct 111 ms 93152 KB Output is correct
27 Correct 113 ms 93228 KB Output is correct
28 Correct 111 ms 93016 KB Output is correct
29 Correct 115 ms 93280 KB Output is correct
30 Correct 122 ms 93296 KB Output is correct
31 Correct 118 ms 93268 KB Output is correct
32 Correct 115 ms 93268 KB Output is correct
33 Correct 116 ms 93016 KB Output is correct
34 Correct 125 ms 93268 KB Output is correct
35 Correct 114 ms 93272 KB Output is correct
36 Correct 116 ms 93264 KB Output is correct
37 Incorrect 115 ms 93016 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 93020 KB Output is correct
2 Correct 26 ms 93016 KB Output is correct
3 Correct 30 ms 93020 KB Output is correct
4 Correct 20 ms 93020 KB Output is correct
5 Correct 4800 ms 93448 KB Output is correct
6 Correct 113 ms 93380 KB Output is correct
7 Correct 110 ms 93212 KB Output is correct
8 Correct 111 ms 93012 KB Output is correct
9 Correct 115 ms 93016 KB Output is correct
10 Correct 114 ms 93324 KB Output is correct
11 Correct 113 ms 92920 KB Output is correct
12 Correct 114 ms 93264 KB Output is correct
13 Incorrect 4866 ms 93808 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 93020 KB Output is correct
2 Correct 32 ms 93016 KB Output is correct
3 Correct 23 ms 93020 KB Output is correct
4 Correct 2310 ms 93180 KB Output is correct
5 Correct 4974 ms 93176 KB Output is correct
6 Correct 115 ms 93016 KB Output is correct
7 Correct 114 ms 93016 KB Output is correct
8 Correct 119 ms 93240 KB Output is correct
9 Correct 162 ms 95312 KB Output is correct
10 Runtime error 219 ms 284084 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -