oj.uz

Submission #879882

# Submission time Handle Problem Language Result Execution time Memory
879882 2023-11-28T09:07:24 Z vivkostov Jail (JOI22_jail) C++14
54 / 100
 1092 ms 946400 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[20000005];
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++;
        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=1;i<=n*10;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*10;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<=10*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 276 ms 519488 KB Output is correct
2 Correct 172 ms 519620 KB Output is correct
3 Correct 167 ms 519456 KB Output is correct
4 Correct 187 ms 520016 KB Output is correct
5 Correct 218 ms 520656 KB Output is correct
6 Correct 165 ms 520276 KB Output is correct
7 Correct 168 ms 520272 KB Output is correct
8 Correct 169 ms 520500 KB Output is correct
9 Correct 262 ms 538708 KB Output is correct
10 Correct 464 ms 876884 KB Output is correct
11 Correct 175 ms 519776 KB Output is correct
12 Correct 233 ms 520796 KB Output is correct
13 Correct 480 ms 893776 KB Output is correct
14 Correct 401 ms 909136 KB Output is correct
15 Correct 640 ms 915784 KB Output is correct
16 Correct 1092 ms 946400 KB Output is correct
17 Correct 453 ms 917692 KB Output is correct
18 Correct 437 ms 920876 KB Output is correct
19 Correct 401 ms 916084 KB Output is correct
20 Correct 412 ms 916008 KB Output is correct
21 Correct 427 ms 917844 KB Output is correct
22 Correct 338 ms 907664 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 537936 KB Output is correct
2 Correct 118 ms 538000 KB Output is correct
3 Correct 116 ms 540232 KB Output is correct
4 Correct 116 ms 539992 KB Output is correct
5 Correct 116 ms 540104 KB Output is correct
6 Correct 117 ms 539988 KB Output is correct
7 Correct 117 ms 540144 KB Output is correct
8 Correct 114 ms 540040 KB Output is correct
9 Correct 114 ms 540228 KB Output is correct
10 Correct 115 ms 540072 KB Output is correct
11 Correct 114 ms 540204 KB Output is correct
12 Correct 113 ms 539984 KB Output is correct
13 Correct 114 ms 539988 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 537936 KB Output is correct
2 Correct 118 ms 538000 KB Output is correct
3 Correct 116 ms 540232 KB Output is correct
4 Correct 116 ms 539992 KB Output is correct
5 Correct 116 ms 540104 KB Output is correct
6 Correct 117 ms 539988 KB Output is correct
7 Correct 117 ms 540144 KB Output is correct
8 Correct 114 ms 540040 KB Output is correct
9 Correct 114 ms 540228 KB Output is correct
10 Correct 115 ms 540072 KB Output is correct
11 Correct 114 ms 540204 KB Output is correct
12 Correct 113 ms 539984 KB Output is correct
13 Correct 114 ms 539988 KB Output is correct
14 Correct 116 ms 537936 KB Output is correct
15 Correct 115 ms 537936 KB Output is correct
16 Correct 115 ms 539988 KB Output is correct
17 Correct 115 ms 539988 KB Output is correct
18 Correct 116 ms 540200 KB Output is correct
19 Correct 114 ms 537836 KB Output is correct
20 Correct 115 ms 539984 KB Output is correct
21 Correct 121 ms 539984 KB Output is correct
22 Correct 116 ms 539988 KB Output is correct
23 Correct 114 ms 538192 KB Output is correct
24 Correct 112 ms 537940 KB Output is correct
25 Correct 116 ms 540148 KB Output is correct
26 Correct 113 ms 540100 KB Output is correct
27 Correct 115 ms 540152 KB Output is correct
28 Correct 112 ms 537936 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 537936 KB Output is correct
2 Correct 118 ms 538000 KB Output is correct
3 Correct 116 ms 540232 KB Output is correct
4 Correct 116 ms 539992 KB Output is correct
5 Correct 116 ms 540104 KB Output is correct
6 Correct 117 ms 539988 KB Output is correct
7 Correct 117 ms 540144 KB Output is correct
8 Correct 114 ms 540040 KB Output is correct
9 Correct 114 ms 540228 KB Output is correct
10 Correct 115 ms 540072 KB Output is correct
11 Correct 114 ms 540204 KB Output is correct
12 Correct 113 ms 539984 KB Output is correct
13 Correct 114 ms 539988 KB Output is correct
14 Correct 116 ms 537936 KB Output is correct
15 Correct 115 ms 537936 KB Output is correct
16 Correct 115 ms 539988 KB Output is correct
17 Correct 115 ms 539988 KB Output is correct
18 Correct 116 ms 540200 KB Output is correct
19 Correct 114 ms 537836 KB Output is correct
20 Correct 115 ms 539984 KB Output is correct
21 Correct 121 ms 539984 KB Output is correct
22 Correct 116 ms 539988 KB Output is correct
23 Correct 114 ms 538192 KB Output is correct
24 Correct 112 ms 537940 KB Output is correct
25 Correct 116 ms 540148 KB Output is correct
26 Correct 113 ms 540100 KB Output is correct
27 Correct 115 ms 540152 KB Output is correct
28 Correct 112 ms 537936 KB Output is correct
29 Correct 117 ms 540220 KB Output is correct
30 Correct 119 ms 540144 KB Output is correct
31 Correct 123 ms 540240 KB Output is correct
32 Correct 119 ms 540244 KB Output is correct
33 Correct 115 ms 539984 KB Output is correct
34 Correct 117 ms 538068 KB Output is correct
35 Correct 117 ms 538192 KB Output is correct
36 Correct 119 ms 538196 KB Output is correct
37 Correct 115 ms 538184 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 537936 KB Output is correct
2 Correct 118 ms 538000 KB Output is correct
3 Correct 116 ms 540232 KB Output is correct
4 Correct 116 ms 539992 KB Output is correct
5 Correct 116 ms 540104 KB Output is correct
6 Correct 117 ms 539988 KB Output is correct
7 Correct 117 ms 540144 KB Output is correct
8 Correct 114 ms 540040 KB Output is correct
9 Correct 114 ms 540228 KB Output is correct
10 Correct 115 ms 540072 KB Output is correct
11 Correct 114 ms 540204 KB Output is correct
12 Correct 113 ms 539984 KB Output is correct
13 Correct 114 ms 539988 KB Output is correct
14 Correct 116 ms 537936 KB Output is correct
15 Correct 115 ms 537936 KB Output is correct
16 Correct 115 ms 539988 KB Output is correct
17 Correct 115 ms 539988 KB Output is correct
18 Correct 116 ms 540200 KB Output is correct
19 Correct 114 ms 537836 KB Output is correct
20 Correct 115 ms 539984 KB Output is correct
21 Correct 121 ms 539984 KB Output is correct
22 Correct 116 ms 539988 KB Output is correct
23 Correct 114 ms 538192 KB Output is correct
24 Correct 112 ms 537940 KB Output is correct
25 Correct 116 ms 540148 KB Output is correct
26 Correct 113 ms 540100 KB Output is correct
27 Correct 115 ms 540152 KB Output is correct
28 Correct 112 ms 537936 KB Output is correct
29 Correct 117 ms 540220 KB Output is correct
30 Correct 119 ms 540144 KB Output is correct
31 Correct 123 ms 540240 KB Output is correct
32 Correct 119 ms 540244 KB Output is correct
33 Correct 115 ms 539984 KB Output is correct
34 Correct 117 ms 538068 KB Output is correct
35 Correct 117 ms 538192 KB Output is correct
36 Correct 119 ms 538196 KB Output is correct
37 Correct 115 ms 538184 KB Output is correct
38 Correct 195 ms 561488 KB Output is correct
39 Correct 250 ms 903764 KB Output is correct
40 Correct 211 ms 561424 KB Output is correct
41 Correct 215 ms 561232 KB Output is correct
42 Correct 200 ms 561540 KB Output is correct
43 Incorrect 175 ms 560976 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 537936 KB Output is correct
2 Correct 120 ms 538008 KB Output is correct
3 Correct 112 ms 537864 KB Output is correct
4 Correct 114 ms 537936 KB Output is correct
5 Correct 130 ms 538060 KB Output is correct
6 Correct 117 ms 540244 KB Output is correct
7 Correct 114 ms 540112 KB Output is correct
8 Correct 115 ms 537936 KB Output is correct
9 Correct 114 ms 538084 KB Output is correct
10 Correct 116 ms 537900 KB Output is correct
11 Correct 112 ms 537912 KB Output is correct
12 Correct 116 ms 538192 KB Output is correct
13 Incorrect 175 ms 538704 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 519488 KB Output is correct
2 Correct 172 ms 519620 KB Output is correct
3 Correct 167 ms 519456 KB Output is correct
4 Correct 187 ms 520016 KB Output is correct
5 Correct 218 ms 520656 KB Output is correct
6 Correct 165 ms 520276 KB Output is correct
7 Correct 168 ms 520272 KB Output is correct
8 Correct 169 ms 520500 KB Output is correct
9 Correct 262 ms 538708 KB Output is correct
10 Correct 464 ms 876884 KB Output is correct
11 Correct 175 ms 519776 KB Output is correct
12 Correct 233 ms 520796 KB Output is correct
13 Correct 480 ms 893776 KB Output is correct
14 Correct 401 ms 909136 KB Output is correct
15 Correct 640 ms 915784 KB Output is correct
16 Correct 1092 ms 946400 KB Output is correct
17 Correct 453 ms 917692 KB Output is correct
18 Correct 437 ms 920876 KB Output is correct
19 Correct 401 ms 916084 KB Output is correct
20 Correct 412 ms 916008 KB Output is correct
21 Correct 427 ms 917844 KB Output is correct
22 Correct 338 ms 907664 KB Output is correct
23 Correct 112 ms 537936 KB Output is correct
24 Correct 118 ms 538000 KB Output is correct
25 Correct 116 ms 540232 KB Output is correct
26 Correct 116 ms 539992 KB Output is correct
27 Correct 116 ms 540104 KB Output is correct
28 Correct 117 ms 539988 KB Output is correct
29 Correct 117 ms 540144 KB Output is correct
30 Correct 114 ms 540040 KB Output is correct
31 Correct 114 ms 540228 KB Output is correct
32 Correct 115 ms 540072 KB Output is correct
33 Correct 114 ms 540204 KB Output is correct
34 Correct 113 ms 539984 KB Output is correct
35 Correct 114 ms 539988 KB Output is correct
36 Correct 116 ms 537936 KB Output is correct
37 Correct 115 ms 537936 KB Output is correct
38 Correct 115 ms 539988 KB Output is correct
39 Correct 115 ms 539988 KB Output is correct
40 Correct 116 ms 540200 KB Output is correct
41 Correct 114 ms 537836 KB Output is correct
42 Correct 115 ms 539984 KB Output is correct
43 Correct 121 ms 539984 KB Output is correct
44 Correct 116 ms 539988 KB Output is correct
45 Correct 114 ms 538192 KB Output is correct
46 Correct 112 ms 537940 KB Output is correct
47 Correct 116 ms 540148 KB Output is correct
48 Correct 113 ms 540100 KB Output is correct
49 Correct 115 ms 540152 KB Output is correct
50 Correct 112 ms 537936 KB Output is correct
51 Correct 117 ms 540220 KB Output is correct
52 Correct 119 ms 540144 KB Output is correct
53 Correct 123 ms 540240 KB Output is correct
54 Correct 119 ms 540244 KB Output is correct
55 Correct 115 ms 539984 KB Output is correct
56 Correct 117 ms 538068 KB Output is correct
57 Correct 117 ms 538192 KB Output is correct
58 Correct 119 ms 538196 KB Output is correct
59 Correct 115 ms 538184 KB Output is correct
60 Correct 195 ms 561488 KB Output is correct
61 Correct 250 ms 903764 KB Output is correct
62 Correct 211 ms 561424 KB Output is correct
63 Correct 215 ms 561232 KB Output is correct
64 Correct 200 ms 561540 KB Output is correct
65 Incorrect 175 ms 560976 KB Output isn't correct
66 Halted 0 ms 0 KB -