oj.uz

Submission #877413

# Submission time Handle Problem Language Result Execution time Memory
877413 2023-11-23T08:21:21 Z simona1230 Jail (JOI22_jail) C++17
26 / 100
 1083 ms 180560 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxn=1e6;
int q,n,m;
vector<int> f[200001];
bool test=0;
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[800001];// number of the vertex corresponding
int te[800001];// to the given tree and segment of the hld
int dw[200001];
int up[200001];

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[200001];
int jump[200001][21];
int sz[200001];
int pos[200001];// new number of vertex i in original graph
int chain[200001];// leader of the chain in which i is
int maxx[200001];
int lvl[200001];
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(r<ql||l>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,qr,pr);
    update(i*2+1,mid+1,r,ql,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;

        int br = 0;

        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];

            br++;
            //if(br >= n + 1) assert(false);

        }
        c1=y;

        br = 0;

        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];

            br++;
            //if(br >= n + 1) assert(false);


        }
    }
}
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--)
    {
        test=0;
        for(int i=1; i<=num; i++)
        {
            o[i].clear();
            v[i].clear();
        }
        memset(maxx,0,sizeof(maxx));
        memset(used,0,sizeof(used));
        memset(pos,0,sizeof(pos));
        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;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 72280 KB Output is correct
2 Correct 15 ms 72284 KB Output is correct
3 Correct 14 ms 72280 KB Output is correct
4 Correct 98 ms 72536 KB Output is correct
5 Correct 189 ms 72280 KB Output is correct
6 Correct 18 ms 72536 KB Output is correct
7 Correct 19 ms 72540 KB Output is correct
8 Correct 21 ms 72540 KB Output is correct
9 Correct 67 ms 74740 KB Output is correct
10 Correct 119 ms 121764 KB Output is correct
11 Correct 190 ms 72280 KB Output is correct
12 Correct 227 ms 72792 KB Output is correct
13 Correct 234 ms 132688 KB Output is correct
14 Correct 231 ms 133088 KB Output is correct
15 Correct 571 ms 142732 KB Output is correct
16 Correct 1083 ms 180560 KB Output is correct
17 Correct 291 ms 148308 KB Output is correct
18 Correct 243 ms 142028 KB Output is correct
19 Correct 282 ms 144592 KB Output is correct
20 Correct 300 ms 144848 KB Output is correct
21 Correct 328 ms 146820 KB Output is correct
22 Correct 189 ms 129760 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 72284 KB Output is correct
2 Correct 14 ms 72256 KB Output is correct
3 Correct 18 ms 72544 KB Output is correct
4 Correct 19 ms 72540 KB Output is correct
5 Correct 19 ms 72492 KB Output is correct
6 Correct 20 ms 72556 KB Output is correct
7 Correct 19 ms 72540 KB Output is correct
8 Correct 18 ms 72512 KB Output is correct
9 Correct 19 ms 72540 KB Output is correct
10 Correct 19 ms 72548 KB Output is correct
11 Correct 18 ms 72540 KB Output is correct
12 Correct 18 ms 72540 KB Output is correct
13 Correct 18 ms 72564 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 72284 KB Output is correct
2 Correct 14 ms 72256 KB Output is correct
3 Correct 18 ms 72544 KB Output is correct
4 Correct 19 ms 72540 KB Output is correct
5 Correct 19 ms 72492 KB Output is correct
6 Correct 20 ms 72556 KB Output is correct
7 Correct 19 ms 72540 KB Output is correct
8 Correct 18 ms 72512 KB Output is correct
9 Correct 19 ms 72540 KB Output is correct
10 Correct 19 ms 72548 KB Output is correct
11 Correct 18 ms 72540 KB Output is correct
12 Correct 18 ms 72540 KB Output is correct
13 Correct 18 ms 72564 KB Output is correct
14 Correct 14 ms 72284 KB Output is correct
15 Correct 15 ms 72284 KB Output is correct
16 Correct 18 ms 72540 KB Output is correct
17 Correct 18 ms 72564 KB Output is correct
18 Correct 18 ms 72540 KB Output is correct
19 Correct 19 ms 72536 KB Output is correct
20 Correct 19 ms 72536 KB Output is correct
21 Correct 19 ms 72540 KB Output is correct
22 Correct 19 ms 72536 KB Output is correct
23 Correct 17 ms 72280 KB Output is correct
24 Correct 18 ms 72284 KB Output is correct
25 Correct 19 ms 72540 KB Output is correct
26 Correct 18 ms 72480 KB Output is correct
27 Correct 19 ms 72540 KB Output is correct
28 Correct 18 ms 72284 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 72284 KB Output is correct
2 Correct 14 ms 72256 KB Output is correct
3 Correct 18 ms 72544 KB Output is correct
4 Correct 19 ms 72540 KB Output is correct
5 Correct 19 ms 72492 KB Output is correct
6 Correct 20 ms 72556 KB Output is correct
7 Correct 19 ms 72540 KB Output is correct
8 Correct 18 ms 72512 KB Output is correct
9 Correct 19 ms 72540 KB Output is correct
10 Correct 19 ms 72548 KB Output is correct
11 Correct 18 ms 72540 KB Output is correct
12 Correct 18 ms 72540 KB Output is correct
13 Correct 18 ms 72564 KB Output is correct
14 Correct 14 ms 72284 KB Output is correct
15 Correct 15 ms 72284 KB Output is correct
16 Correct 18 ms 72540 KB Output is correct
17 Correct 18 ms 72564 KB Output is correct
18 Correct 18 ms 72540 KB Output is correct
19 Correct 19 ms 72536 KB Output is correct
20 Correct 19 ms 72536 KB Output is correct
21 Correct 19 ms 72540 KB Output is correct
22 Correct 19 ms 72536 KB Output is correct
23 Correct 17 ms 72280 KB Output is correct
24 Correct 18 ms 72284 KB Output is correct
25 Correct 19 ms 72540 KB Output is correct
26 Correct 18 ms 72480 KB Output is correct
27 Correct 19 ms 72540 KB Output is correct
28 Correct 18 ms 72284 KB Output is correct
29 Correct 20 ms 72536 KB Output is correct
30 Correct 21 ms 72536 KB Output is correct
31 Correct 20 ms 72540 KB Output is correct
32 Correct 20 ms 72464 KB Output is correct
33 Correct 19 ms 72540 KB Output is correct
34 Correct 21 ms 72540 KB Output is correct
35 Correct 20 ms 72536 KB Output is correct
36 Correct 19 ms 72492 KB Output is correct
37 Incorrect 20 ms 72540 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 72284 KB Output is correct
2 Correct 14 ms 72256 KB Output is correct
3 Correct 18 ms 72544 KB Output is correct
4 Correct 19 ms 72540 KB Output is correct
5 Correct 19 ms 72492 KB Output is correct
6 Correct 20 ms 72556 KB Output is correct
7 Correct 19 ms 72540 KB Output is correct
8 Correct 18 ms 72512 KB Output is correct
9 Correct 19 ms 72540 KB Output is correct
10 Correct 19 ms 72548 KB Output is correct
11 Correct 18 ms 72540 KB Output is correct
12 Correct 18 ms 72540 KB Output is correct
13 Correct 18 ms 72564 KB Output is correct
14 Correct 14 ms 72284 KB Output is correct
15 Correct 15 ms 72284 KB Output is correct
16 Correct 18 ms 72540 KB Output is correct
17 Correct 18 ms 72564 KB Output is correct
18 Correct 18 ms 72540 KB Output is correct
19 Correct 19 ms 72536 KB Output is correct
20 Correct 19 ms 72536 KB Output is correct
21 Correct 19 ms 72540 KB Output is correct
22 Correct 19 ms 72536 KB Output is correct
23 Correct 17 ms 72280 KB Output is correct
24 Correct 18 ms 72284 KB Output is correct
25 Correct 19 ms 72540 KB Output is correct
26 Correct 18 ms 72480 KB Output is correct
27 Correct 19 ms 72540 KB Output is correct
28 Correct 18 ms 72284 KB Output is correct
29 Correct 20 ms 72536 KB Output is correct
30 Correct 21 ms 72536 KB Output is correct
31 Correct 20 ms 72540 KB Output is correct
32 Correct 20 ms 72464 KB Output is correct
33 Correct 19 ms 72540 KB Output is correct
34 Correct 21 ms 72540 KB Output is correct
35 Correct 20 ms 72536 KB Output is correct
36 Correct 19 ms 72492 KB Output is correct
37 Incorrect 20 ms 72540 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 72284 KB Output is correct
2 Correct 15 ms 72284 KB Output is correct
3 Correct 15 ms 72284 KB Output is correct
4 Correct 14 ms 72284 KB Output is correct
5 Correct 190 ms 72488 KB Output is correct
6 Correct 18 ms 72540 KB Output is correct
7 Correct 18 ms 72536 KB Output is correct
8 Correct 17 ms 72280 KB Output is correct
9 Correct 18 ms 72284 KB Output is correct
10 Correct 18 ms 72280 KB Output is correct
11 Correct 18 ms 72284 KB Output is correct
12 Correct 20 ms 72628 KB Output is correct
13 Incorrect 209 ms 73012 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 72280 KB Output is correct
2 Correct 15 ms 72284 KB Output is correct
3 Correct 14 ms 72280 KB Output is correct
4 Correct 98 ms 72536 KB Output is correct
5 Correct 189 ms 72280 KB Output is correct
6 Correct 18 ms 72536 KB Output is correct
7 Correct 19 ms 72540 KB Output is correct
8 Correct 21 ms 72540 KB Output is correct
9 Correct 67 ms 74740 KB Output is correct
10 Correct 119 ms 121764 KB Output is correct
11 Correct 190 ms 72280 KB Output is correct
12 Correct 227 ms 72792 KB Output is correct
13 Correct 234 ms 132688 KB Output is correct
14 Correct 231 ms 133088 KB Output is correct
15 Correct 571 ms 142732 KB Output is correct
16 Correct 1083 ms 180560 KB Output is correct
17 Correct 291 ms 148308 KB Output is correct
18 Correct 243 ms 142028 KB Output is correct
19 Correct 282 ms 144592 KB Output is correct
20 Correct 300 ms 144848 KB Output is correct
21 Correct 328 ms 146820 KB Output is correct
22 Correct 189 ms 129760 KB Output is correct
23 Correct 14 ms 72284 KB Output is correct
24 Correct 14 ms 72256 KB Output is correct
25 Correct 18 ms 72544 KB Output is correct
26 Correct 19 ms 72540 KB Output is correct
27 Correct 19 ms 72492 KB Output is correct
28 Correct 20 ms 72556 KB Output is correct
29 Correct 19 ms 72540 KB Output is correct
30 Correct 18 ms 72512 KB Output is correct
31 Correct 19 ms 72540 KB Output is correct
32 Correct 19 ms 72548 KB Output is correct
33 Correct 18 ms 72540 KB Output is correct
34 Correct 18 ms 72540 KB Output is correct
35 Correct 18 ms 72564 KB Output is correct
36 Correct 14 ms 72284 KB Output is correct
37 Correct 15 ms 72284 KB Output is correct
38 Correct 18 ms 72540 KB Output is correct
39 Correct 18 ms 72564 KB Output is correct
40 Correct 18 ms 72540 KB Output is correct
41 Correct 19 ms 72536 KB Output is correct
42 Correct 19 ms 72536 KB Output is correct
43 Correct 19 ms 72540 KB Output is correct
44 Correct 19 ms 72536 KB Output is correct
45 Correct 17 ms 72280 KB Output is correct
46 Correct 18 ms 72284 KB Output is correct
47 Correct 19 ms 72540 KB Output is correct
48 Correct 18 ms 72480 KB Output is correct
49 Correct 19 ms 72540 KB Output is correct
50 Correct 18 ms 72284 KB Output is correct
51 Correct 20 ms 72536 KB Output is correct
52 Correct 21 ms 72536 KB Output is correct
53 Correct 20 ms 72540 KB Output is correct
54 Correct 20 ms 72464 KB Output is correct
55 Correct 19 ms 72540 KB Output is correct
56 Correct 21 ms 72540 KB Output is correct
57 Correct 20 ms 72536 KB Output is correct
58 Correct 19 ms 72492 KB Output is correct
59 Incorrect 20 ms 72540 KB Output isn't correct
60 Halted 0 ms 0 KB -