oj.uz

Submission #879891

# Submission time Handle Problem Language Result Execution time Memory
879891 2023-11-28T09:20:30 Z vivkostov Jail (JOI22_jail) C++14
10 / 100
 1037 ms 670208 KB 
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int q,n,m,c,d,a[2000005],b[2000005],child[2000005],machild[2000005],used[2000005],up[2000005],bin[2000005][60],level[2000005],usedl[2000005],in,brr,brj;
vector<int>v[2000005],p[2000005];
void find_child(int beg,int par,int lev)
{
    level[beg]=lev;
    child[beg]++;
    bin[beg][0]=par;
    int w=0;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!child[w])
        {
            find_child(w,beg,lev+1);
            child[beg]+=child[w];
            machild[beg]=max(machild[beg],child[w]);
        }
    }
}
void heavylight(int beg,int last)
{
    in++;
    up[beg]=last;
    used[beg]=in;
    int w,ma=0;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w]&&child[w]==machild[beg])
        {
            heavylight(w,last);
            break;
        }
    }
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w])heavylight(w,w);
    }
}
void make_start(int l,int r,int h)
{
    if(l==r)return;
    int mid=(l+r)/2;
    p[h+n].push_back(h*2+n);
    p[h+n].push_back(h*2+1+n);
    make_start(l,mid,h*2);
    make_start(mid+1,r,h*2+1);
}
void make_finish(int l,int r,int h)
{
    if(l==r)return;
    int mid=(l+r)/2;
    p[h*2+n*5].push_back(h+n*5);
    p[h*2+1+n*5].push_back(h+n*5);
    make_finish(l,mid,h*2);
    make_finish(mid+1,r,h*2+1);
}
void update(int l,int r,int ql,int qr,int h,int to,int type)
{
    if(l>qr||r<ql)return;
    if(l>=ql&&r<=qr)
    {
        if(type==1)p[h+n].push_back(to);
        if(type==2)p[to].push_back(h+n*5);
        if(type==3)p[to].push_back(h+n);
        if(type==4)p[h+n*5].push_back(to);
        return;
    }
    int mid=(l+r)/2;
    update(l,mid,ql,qr,h*2,to,type);
    update(mid+1,r,ql,qr,h*2+1,to,type);
}
void make_bin()
{
    for(int j=1;j<=30;j++)
    {
        for(int i=1;i<=n;i++)
        {
            bin[i][j]=bin[bin[i][j-1]][j-1];
        }
    }
}
void add_all()
{
    for(int i=1;i<=m;i++)
    {
        update(1,n,used[a[i]],used[a[i]],1,i,1);
        update(1,n,used[b[i]],used[b[i]],1,i,2);
    }
}
int lca(int x,int y)
{
    if(level[x]>level[y])swap(x,y);
    for(int i=30;i>=0;i--)
    {
        if(level[bin[y][i]]>=level[x])y=bin[y][i];
    }
    if(x==y)return x;
    for(int i=30;i>=0;i--)
    {
        if(bin[x][i]!=bin[y][i])
        {
            x=bin[x][i];
            y=bin[y][i];
        }
    }
    return bin[x][0];
}
void go_up_heavy(int beg,int lc,int prisoner)
{
    if(level[up[beg]]==level[lc])
    {
        update(1,n,used[up[beg]],used[beg],1,prisoner,3);
        update(1,n,used[up[beg]],used[beg],1,prisoner,4);
        return;
    }
    if(level[up[beg]]>level[lc])
    {
        update(1,n,used[up[beg]],used[beg],1,prisoner,3);
        update(1,n,used[up[beg]],used[beg],1,prisoner,4);
        go_up_heavy(bin[up[beg]][0],lc,prisoner);
        return;
    }
    update(1,n,used[lc],used[beg],1,prisoner,3);
    update(1,n,used[lc],used[beg],1,prisoner,4);
}
void add_path()
{
    for(int i=1;i<=m;i++)
    {
        int g=lca(a[i],b[i]);
        go_up_heavy(a[i],g,i);
        go_up_heavy(b[i],g,i);
    }
}
int tin[2000005],low[2000005],tim,lamp,comp[2000005],co;
stack<int>s;
void conect(int beg,int par)
{
    tim++;
    tin[beg]=tim;
    low[beg]=tim;
    s.push(beg);
    int w;
    for(int i=0;i<p[beg].size();i++)
    {
        w=p[beg][i];
        if(tin[w]==-1)continue;
        if(!tin[w])
        {
            conect(w,beg);
            low[beg]=min(low[beg],low[w]);
        }
        if(par!=w)low[beg]=min(low[beg],low[w]);
    }
    if(low[beg]==tin[beg])
    {
        co++;
        while(s.top()!=beg)
        {
            //cout<<s.top()<<" ";
            tin[s.top()]=-1;
            comp[s.top()]=co;
            s.pop();
        }
        //cout<<s.top()<<" ";
        tin[s.top()]=-1;
        comp[s.top()]=co;
        s.pop();
        //cout<<endl;
    }
}
void fill_cycle(int beg)
{
    if(beg<=m)brj++;
    usedl[beg]=2;
    int w;
    for(int i=0; i<p[beg].size(); i++)
    {
        w=p[beg][i];
        if(usedl[w]==1)fill_cycle(w);
    }
}
void find_cycle(int beg)
{
    usedl[beg]=1;
    int w;
    for(int i=0; i<p[beg].size(); i++)
    {
        w=p[beg][i];
        if(!usedl[w])find_cycle(w);
    }
    if(usedl[beg]!=2&&beg<=m)
    {
        fill_cycle(beg);
        if(brj>=2)brr=1;
        brj=0;
    }
}
void resh()
{
    find_child(1,0,1);
    heavylight(1,1);
    make_start(1,n,1);
    make_finish(1,n,1);
    add_all();
    make_bin();
    add_path();
    for(int i=10*n;i>=1;i--)
    {
        if(!usedl[i])find_cycle(i);
    }
    /*for(int i=1;i<=48;i++)
    {
        cout<<i<<" | ";
        for(int j=0;j<p[i].size();j++)
        {
            cout<<p[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    if(brr)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    for(int i=0;i<=n*15;i++)
    {
        a[i]=0;
        b[i]=0;
        child[i]=0;
        machild[i]=0;
        used[i]=0;
        up[i]=0;
        level[i]=0;
        usedl[i]=0;
        tin[i]=0;
        low[i]=0;
        comp[i]=0;
        v[i].clear();
        for(int j=0;j<=30;j++)bin[i][j]=0;
    }
    for(int i=0;i<=15*n;i++)p[i].clear();
    while(!s.empty())s.pop();
    in=0;
    brr=0;
    brj=0;
    lamp=0;
    tim=0;
    co=0;
}
void read()
{
    cin>>q;
    for(int z=1;z<=q;z++)
    {
        cin>>n;
        for(int i=1;i<n;i++)
        {
            cin>>c>>d;
            v[c].push_back(d);
            v[d].push_back(c);
        }
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>a[i]>>b[i];
        }
        resh();
    }
}
int main()
{
    speed();
    read();
    return 0;
}

Compilation message

jail.cpp: In function 'void find_child(int, int, int)':
jail.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp: In function 'void heavylight(int, int)':
jail.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp:34:11: warning: unused variable 'ma' [-Wunused-variable]
   34 |     int w,ma=0;
      |           ^~
jail.cpp: In function 'void conect(int, int)':
jail.cpp:155:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for(int i=0;i<p[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp: In function 'void fill_cycle(int)':
jail.cpp:188:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
jail.cpp: In function 'void find_cycle(int)':
jail.cpp:198:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 115292 KB Output is correct
2 Correct 25 ms 115240 KB Output is correct
3 Correct 22 ms 115292 KB Output is correct
4 Correct 46 ms 115400 KB Output is correct
5 Correct 72 ms 115408 KB Output is correct
6 Correct 25 ms 117340 KB Output is correct
7 Correct 26 ms 117340 KB Output is correct
8 Correct 28 ms 117340 KB Output is correct
9 Correct 119 ms 145916 KB Output is correct
10 Correct 188 ms 628304 KB Output is correct
11 Correct 36 ms 115288 KB Output is correct
12 Correct 113 ms 115416 KB Output is correct
13 Correct 288 ms 635016 KB Output is correct
14 Correct 293 ms 635548 KB Output is correct
15 Correct 507 ms 642160 KB Output is correct
16 Correct 1037 ms 670208 KB Output is correct
17 Correct 330 ms 642132 KB Output is correct
18 Correct 345 ms 635500 KB Output is correct
19 Correct 332 ms 640080 KB Output is correct
20 Correct 327 ms 640264 KB Output is correct
21 Correct 350 ms 642304 KB Output is correct
22 Correct 257 ms 631812 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 115292 KB Output is correct
2 Correct 23 ms 115292 KB Output is correct
3 Correct 26 ms 117340 KB Output is correct
4 Correct 25 ms 117340 KB Output is correct
5 Correct 29 ms 117340 KB Output is correct
6 Correct 25 ms 117340 KB Output is correct
7 Correct 26 ms 117340 KB Output is correct
8 Correct 25 ms 117316 KB Output is correct
9 Correct 26 ms 117336 KB Output is correct
10 Correct 25 ms 117340 KB Output is correct
11 Correct 26 ms 117504 KB Output is correct
12 Correct 24 ms 117336 KB Output is correct
13 Correct 27 ms 117596 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 115292 KB Output is correct
2 Correct 23 ms 115292 KB Output is correct
3 Correct 26 ms 117340 KB Output is correct
4 Correct 25 ms 117340 KB Output is correct
5 Correct 29 ms 117340 KB Output is correct
6 Correct 25 ms 117340 KB Output is correct
7 Correct 26 ms 117340 KB Output is correct
8 Correct 25 ms 117316 KB Output is correct
9 Correct 26 ms 117336 KB Output is correct
10 Correct 25 ms 117340 KB Output is correct
11 Correct 26 ms 117504 KB Output is correct
12 Correct 24 ms 117336 KB Output is correct
13 Correct 27 ms 117596 KB Output is correct
14 Correct 24 ms 115384 KB Output is correct
15 Correct 23 ms 115544 KB Output is correct
16 Correct 25 ms 117304 KB Output is correct
17 Correct 26 ms 117504 KB Output is correct
18 Correct 26 ms 117336 KB Output is correct
19 Correct 23 ms 115292 KB Output is correct
20 Correct 27 ms 117340 KB Output is correct
21 Correct 25 ms 117340 KB Output is correct
22 Correct 26 ms 117340 KB Output is correct
23 Incorrect 25 ms 115288 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 115292 KB Output is correct
2 Correct 23 ms 115292 KB Output is correct
3 Correct 26 ms 117340 KB Output is correct
4 Correct 25 ms 117340 KB Output is correct
5 Correct 29 ms 117340 KB Output is correct
6 Correct 25 ms 117340 KB Output is correct
7 Correct 26 ms 117340 KB Output is correct
8 Correct 25 ms 117316 KB Output is correct
9 Correct 26 ms 117336 KB Output is correct
10 Correct 25 ms 117340 KB Output is correct
11 Correct 26 ms 117504 KB Output is correct
12 Correct 24 ms 117336 KB Output is correct
13 Correct 27 ms 117596 KB Output is correct
14 Correct 24 ms 115384 KB Output is correct
15 Correct 23 ms 115544 KB Output is correct
16 Correct 25 ms 117304 KB Output is correct
17 Correct 26 ms 117504 KB Output is correct
18 Correct 26 ms 117336 KB Output is correct
19 Correct 23 ms 115292 KB Output is correct
20 Correct 27 ms 117340 KB Output is correct
21 Correct 25 ms 117340 KB Output is correct
22 Correct 26 ms 117340 KB Output is correct
23 Incorrect 25 ms 115288 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 115292 KB Output is correct
2 Correct 23 ms 115292 KB Output is correct
3 Correct 26 ms 117340 KB Output is correct
4 Correct 25 ms 117340 KB Output is correct
5 Correct 29 ms 117340 KB Output is correct
6 Correct 25 ms 117340 KB Output is correct
7 Correct 26 ms 117340 KB Output is correct
8 Correct 25 ms 117316 KB Output is correct
9 Correct 26 ms 117336 KB Output is correct
10 Correct 25 ms 117340 KB Output is correct
11 Correct 26 ms 117504 KB Output is correct
12 Correct 24 ms 117336 KB Output is correct
13 Correct 27 ms 117596 KB Output is correct
14 Correct 24 ms 115384 KB Output is correct
15 Correct 23 ms 115544 KB Output is correct
16 Correct 25 ms 117304 KB Output is correct
17 Correct 26 ms 117504 KB Output is correct
18 Correct 26 ms 117336 KB Output is correct
19 Correct 23 ms 115292 KB Output is correct
20 Correct 27 ms 117340 KB Output is correct
21 Correct 25 ms 117340 KB Output is correct
22 Correct 26 ms 117340 KB Output is correct
23 Incorrect 25 ms 115288 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 115292 KB Output is correct
2 Correct 23 ms 115292 KB Output is correct
3 Correct 30 ms 115292 KB Output is correct
4 Correct 23 ms 115288 KB Output is correct
5 Correct 36 ms 115292 KB Output is correct
6 Correct 26 ms 117492 KB Output is correct
7 Correct 24 ms 117340 KB Output is correct
8 Correct 23 ms 115292 KB Output is correct
9 Incorrect 22 ms 115292 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 115292 KB Output is correct
2 Correct 25 ms 115240 KB Output is correct
3 Correct 22 ms 115292 KB Output is correct
4 Correct 46 ms 115400 KB Output is correct
5 Correct 72 ms 115408 KB Output is correct
6 Correct 25 ms 117340 KB Output is correct
7 Correct 26 ms 117340 KB Output is correct
8 Correct 28 ms 117340 KB Output is correct
9 Correct 119 ms 145916 KB Output is correct
10 Correct 188 ms 628304 KB Output is correct
11 Correct 36 ms 115288 KB Output is correct
12 Correct 113 ms 115416 KB Output is correct
13 Correct 288 ms 635016 KB Output is correct
14 Correct 293 ms 635548 KB Output is correct
15 Correct 507 ms 642160 KB Output is correct
16 Correct 1037 ms 670208 KB Output is correct
17 Correct 330 ms 642132 KB Output is correct
18 Correct 345 ms 635500 KB Output is correct
19 Correct 332 ms 640080 KB Output is correct
20 Correct 327 ms 640264 KB Output is correct
21 Correct 350 ms 642304 KB Output is correct
22 Correct 257 ms 631812 KB Output is correct
23 Correct 25 ms 115292 KB Output is correct
24 Correct 23 ms 115292 KB Output is correct
25 Correct 26 ms 117340 KB Output is correct
26 Correct 25 ms 117340 KB Output is correct
27 Correct 29 ms 117340 KB Output is correct
28 Correct 25 ms 117340 KB Output is correct
29 Correct 26 ms 117340 KB Output is correct
30 Correct 25 ms 117316 KB Output is correct
31 Correct 26 ms 117336 KB Output is correct
32 Correct 25 ms 117340 KB Output is correct
33 Correct 26 ms 117504 KB Output is correct
34 Correct 24 ms 117336 KB Output is correct
35 Correct 27 ms 117596 KB Output is correct
36 Correct 24 ms 115384 KB Output is correct
37 Correct 23 ms 115544 KB Output is correct
38 Correct 25 ms 117304 KB Output is correct
39 Correct 26 ms 117504 KB Output is correct
40 Correct 26 ms 117336 KB Output is correct
41 Correct 23 ms 115292 KB Output is correct
42 Correct 27 ms 117340 KB Output is correct
43 Correct 25 ms 117340 KB Output is correct
44 Correct 26 ms 117340 KB Output is correct
45 Incorrect 25 ms 115288 KB Output isn't correct
46 Halted 0 ms 0 KB -