oj.uz

Submission #877433

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

using namespace std;
const int maxn=2e6;
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()
{
    for(int i=1;i<=m;i++)
    {
        if(!used1[i])dfs1(i);
    }
    int cnt1=0;
    while(st.size())
    {
        int vr=st.top();
        st.pop();
        if(vr<=m&&!used2[vr])
        {
            cnt1++;
            dfs2(vr);
        }
    }
    if(cnt1==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<maxn; i++)
        {
            o[i].clear();
            v[i].clear();
        }
        memset(maxx,0,sizeof(maxx));
        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));

        read();
        for(int i=1;i<=n;i++)
            for(int j=0;j<=20;j++)
                jump[i][j]=0;
        cnt=1;
        necessities(1,1);
        hld(1,1,1);
        cnt--;
        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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 129104 KB Output is correct
2 Correct 54 ms 129108 KB Output is correct
3 Correct 32 ms 129104 KB Output is correct
4 Correct 3261 ms 129696 KB Output is correct
5 Execution timed out 5037 ms 129880 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 129100 KB Output is correct
2 Correct 31 ms 129116 KB Output is correct
3 Correct 162 ms 129396 KB Output is correct
4 Correct 165 ms 129360 KB Output is correct
5 Correct 171 ms 129392 KB Output is correct
6 Correct 164 ms 129616 KB Output is correct
7 Correct 182 ms 129416 KB Output is correct
8 Correct 165 ms 129364 KB Output is correct
9 Correct 166 ms 129324 KB Output is correct
10 Correct 165 ms 129412 KB Output is correct
11 Correct 149 ms 129412 KB Output is correct
12 Correct 161 ms 129380 KB Output is correct
13 Correct 178 ms 129392 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 129100 KB Output is correct
2 Correct 31 ms 129116 KB Output is correct
3 Correct 162 ms 129396 KB Output is correct
4 Correct 165 ms 129360 KB Output is correct
5 Correct 171 ms 129392 KB Output is correct
6 Correct 164 ms 129616 KB Output is correct
7 Correct 182 ms 129416 KB Output is correct
8 Correct 165 ms 129364 KB Output is correct
9 Correct 166 ms 129324 KB Output is correct
10 Correct 165 ms 129412 KB Output is correct
11 Correct 149 ms 129412 KB Output is correct
12 Correct 161 ms 129380 KB Output is correct
13 Correct 178 ms 129392 KB Output is correct
14 Correct 39 ms 129116 KB Output is correct
15 Correct 48 ms 129116 KB Output is correct
16 Correct 164 ms 129368 KB Output is correct
17 Correct 168 ms 129604 KB Output is correct
18 Correct 169 ms 129368 KB Output is correct
19 Correct 174 ms 129116 KB Output is correct
20 Correct 166 ms 129420 KB Output is correct
21 Correct 174 ms 129660 KB Output is correct
22 Correct 172 ms 129428 KB Output is correct
23 Correct 193 ms 127992 KB Output is correct
24 Correct 192 ms 128212 KB Output is correct
25 Correct 197 ms 128080 KB Output is correct
26 Correct 196 ms 128080 KB Output is correct
27 Correct 184 ms 128084 KB Output is correct
28 Correct 191 ms 128004 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 129100 KB Output is correct
2 Correct 31 ms 129116 KB Output is correct
3 Correct 162 ms 129396 KB Output is correct
4 Correct 165 ms 129360 KB Output is correct
5 Correct 171 ms 129392 KB Output is correct
6 Correct 164 ms 129616 KB Output is correct
7 Correct 182 ms 129416 KB Output is correct
8 Correct 165 ms 129364 KB Output is correct
9 Correct 166 ms 129324 KB Output is correct
10 Correct 165 ms 129412 KB Output is correct
11 Correct 149 ms 129412 KB Output is correct
12 Correct 161 ms 129380 KB Output is correct
13 Correct 178 ms 129392 KB Output is correct
14 Correct 39 ms 129116 KB Output is correct
15 Correct 48 ms 129116 KB Output is correct
16 Correct 164 ms 129368 KB Output is correct
17 Correct 168 ms 129604 KB Output is correct
18 Correct 169 ms 129368 KB Output is correct
19 Correct 174 ms 129116 KB Output is correct
20 Correct 166 ms 129420 KB Output is correct
21 Correct 174 ms 129660 KB Output is correct
22 Correct 172 ms 129428 KB Output is correct
23 Correct 193 ms 127992 KB Output is correct
24 Correct 192 ms 128212 KB Output is correct
25 Correct 197 ms 128080 KB Output is correct
26 Correct 196 ms 128080 KB Output is correct
27 Correct 184 ms 128084 KB Output is correct
28 Correct 191 ms 128004 KB Output is correct
29 Correct 196 ms 128368 KB Output is correct
30 Correct 190 ms 128336 KB Output is correct
31 Correct 192 ms 128388 KB Output is correct
32 Correct 191 ms 128356 KB Output is correct
33 Correct 203 ms 128080 KB Output is correct
34 Correct 193 ms 128348 KB Output is correct
35 Correct 167 ms 129364 KB Output is correct
36 Correct 186 ms 128356 KB Output is correct
37 Incorrect 192 ms 128316 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 129100 KB Output is correct
2 Correct 31 ms 129116 KB Output is correct
3 Correct 162 ms 129396 KB Output is correct
4 Correct 165 ms 129360 KB Output is correct
5 Correct 171 ms 129392 KB Output is correct
6 Correct 164 ms 129616 KB Output is correct
7 Correct 182 ms 129416 KB Output is correct
8 Correct 165 ms 129364 KB Output is correct
9 Correct 166 ms 129324 KB Output is correct
10 Correct 165 ms 129412 KB Output is correct
11 Correct 149 ms 129412 KB Output is correct
12 Correct 161 ms 129380 KB Output is correct
13 Correct 178 ms 129392 KB Output is correct
14 Correct 39 ms 129116 KB Output is correct
15 Correct 48 ms 129116 KB Output is correct
16 Correct 164 ms 129368 KB Output is correct
17 Correct 168 ms 129604 KB Output is correct
18 Correct 169 ms 129368 KB Output is correct
19 Correct 174 ms 129116 KB Output is correct
20 Correct 166 ms 129420 KB Output is correct
21 Correct 174 ms 129660 KB Output is correct
22 Correct 172 ms 129428 KB Output is correct
23 Correct 193 ms 127992 KB Output is correct
24 Correct 192 ms 128212 KB Output is correct
25 Correct 197 ms 128080 KB Output is correct
26 Correct 196 ms 128080 KB Output is correct
27 Correct 184 ms 128084 KB Output is correct
28 Correct 191 ms 128004 KB Output is correct
29 Correct 196 ms 128368 KB Output is correct
30 Correct 190 ms 128336 KB Output is correct
31 Correct 192 ms 128388 KB Output is correct
32 Correct 191 ms 128356 KB Output is correct
33 Correct 203 ms 128080 KB Output is correct
34 Correct 193 ms 128348 KB Output is correct
35 Correct 167 ms 129364 KB Output is correct
36 Correct 186 ms 128356 KB Output is correct
37 Incorrect 192 ms 128316 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 128076 KB Output is correct
2 Correct 56 ms 128344 KB Output is correct
3 Correct 56 ms 128080 KB Output is correct
4 Correct 41 ms 128088 KB Output is correct
5 Execution timed out 5030 ms 128324 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 129104 KB Output is correct
2 Correct 54 ms 129108 KB Output is correct
3 Correct 32 ms 129104 KB Output is correct
4 Correct 3261 ms 129696 KB Output is correct
5 Execution timed out 5037 ms 129880 KB Time limit exceeded
6 Halted 0 ms 0 KB -