oj.uz

Submission #879885

# Submission time Handle Problem Language Result Execution time Memory
879885 2023-11-28T09:10:00 Z vivkostov Jail (JOI22_jail) C++14
49 / 100
 311 ms 1048576 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);
}
long long 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<long long int>v[2000005],p[20000005];
void find_child(long long int beg,long long int par,long long int lev)
{
    level[beg]=lev;
    child[beg]++;
    bin[beg][0]=par;
    long long int w=0;
    for(long long 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(long long int beg,long long int last)
{
    in++;
    up[beg]=last;
    used[beg]=in;
    long long int w,ma=0;
    for(long long int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w]&&child[w]==machild[beg])
        {
            heavylight(w,last);
            break;
        }
    }
    for(long long int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w])heavylight(w,w);
    }
}
void make_start(long long int l,long long int r,long long int h)
{
    if(l==r)return;
    long long 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(long long int l,long long int r,long long int h)
{
    if(l==r)return;
    long long 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(long long int l,long long int r,long long int ql,long long int qr,long long int h,long long int to,long long 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;
    }
    long long 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(long long int j=1;j<=30;j++)
    {
        for(long long int i=1;i<=n;i++)
        {
            bin[i][j]=bin[bin[i][j-1]][j-1];
        }
    }
}
void add_all()
{
    for(long long 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);
    }
}
long long int lca(long long int x,long long int y)
{
    if(level[x]>level[y])swap(x,y);
    for(long long int i=30;i>=0;i--)
    {
        if(level[bin[y][i]]>=level[x])y=bin[y][i];
    }
    if(x==y)return x;
    for(long long 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(long long int beg,long long int lc,long long 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(long long int i=1;i<=m;i++)
    {
        long long int g=lca(a[i],b[i]);
        go_up_heavy(a[i],g,i);
        go_up_heavy(b[i],g,i);
    }
}
long long int tin[2000005],low[2000005],tim,lamp,comp[2000005],co;
stack<long long int>s;
void conect(long long int beg,long long int par)
{
    tim++;
    tin[beg]=tim;
    low[beg]=tim;
    s.push(beg);
    long long int w;
    for(long long 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(long long int beg)
{
    if(beg<=m)brj++;
    usedl[beg]=2;
    long long int w;
    for(long long int i=0; i<p[beg].size(); i++)
    {
        w=p[beg][i];
        if(usedl[w]==1)fill_cycle(w);
    }
}
void find_cycle(long long int beg)
{
    usedl[beg]=1;
    long long int w;
    for(long long 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(long long int i=1;i<=n*10;i++)
    {
        if(!usedl[i])find_cycle(i);
    }
    /*for(long long int i=1;i<=48;i++)
    {
        cout<<i<<" | ";
        for(long long int j=0;j<p[i].size();j++)
        {
            cout<<p[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    if(brr)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    for(long long 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(long long int j=0;j<=30;j++)bin[i][j]=0;
    }
    for(long long 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(long long int z=1;z<=q;z++)
    {
        cin>>n;
        for(long long int i=1;i<n;i++)
        {
            cin>>c>>d;
            v[c].push_back(d);
            v[d].push_back(c);
        }
        cin>>m;
        for(long long 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(long long int, long long int, long long int)':
jail.cpp:18:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(long long int i=0;i<v[beg].size();i++)
      |                           ~^~~~~~~~~~~~~~
jail.cpp: In function 'void heavylight(long long int, long long int)':
jail.cpp:35:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(long long int i=0;i<v[beg].size();i++)
      |                           ~^~~~~~~~~~~~~~
jail.cpp:44:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(long long int i=0;i<v[beg].size();i++)
      |                           ~^~~~~~~~~~~~~~
jail.cpp:34:21: warning: unused variable 'ma' [-Wunused-variable]
   34 |     long long int w,ma=0;
      |                     ^~
jail.cpp: In function 'void conect(long long int, long long int)':
jail.cpp:155:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for(long long int i=0;i<p[beg].size();i++)
      |                           ~^~~~~~~~~~~~~~
jail.cpp: In function 'void fill_cycle(long long int)':
jail.cpp:188:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |     for(long long int i=0; i<p[beg].size(); i++)
      |                            ~^~~~~~~~~~~~~~
jail.cpp: In function 'void find_cycle(long long int)':
jail.cpp:198:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |     for(long long int i=0; i<p[beg].size(); i++)
      |                            ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 537936 KB Output is correct
2 Correct 113 ms 538080 KB Output is correct
3 Correct 114 ms 537956 KB Output is correct
4 Correct 138 ms 540500 KB Output is correct
5 Correct 165 ms 540896 KB Output is correct
6 Correct 114 ms 540124 KB Output is correct
7 Correct 116 ms 540108 KB Output is correct
8 Correct 116 ms 540244 KB Output is correct
9 Correct 226 ms 574012 KB Output is correct
10 Runtime error 218 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 538056 KB Output is correct
2 Correct 112 ms 537936 KB Output is correct
3 Correct 123 ms 540120 KB Output is correct
4 Correct 115 ms 540116 KB Output is correct
5 Correct 116 ms 540240 KB Output is correct
6 Correct 114 ms 540240 KB Output is correct
7 Correct 119 ms 540244 KB Output is correct
8 Correct 116 ms 540240 KB Output is correct
9 Correct 122 ms 540240 KB Output is correct
10 Correct 116 ms 540244 KB Output is correct
11 Correct 114 ms 540236 KB Output is correct
12 Correct 114 ms 540220 KB Output is correct
13 Correct 113 ms 540112 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 538056 KB Output is correct
2 Correct 112 ms 537936 KB Output is correct
3 Correct 123 ms 540120 KB Output is correct
4 Correct 115 ms 540116 KB Output is correct
5 Correct 116 ms 540240 KB Output is correct
6 Correct 114 ms 540240 KB Output is correct
7 Correct 119 ms 540244 KB Output is correct
8 Correct 116 ms 540240 KB Output is correct
9 Correct 122 ms 540240 KB Output is correct
10 Correct 116 ms 540244 KB Output is correct
11 Correct 114 ms 540236 KB Output is correct
12 Correct 114 ms 540220 KB Output is correct
13 Correct 113 ms 540112 KB Output is correct
14 Correct 114 ms 538232 KB Output is correct
15 Correct 122 ms 537940 KB Output is correct
16 Correct 123 ms 540104 KB Output is correct
17 Correct 144 ms 540240 KB Output is correct
18 Correct 118 ms 540240 KB Output is correct
19 Correct 115 ms 537940 KB Output is correct
20 Correct 126 ms 540240 KB Output is correct
21 Correct 133 ms 540196 KB Output is correct
22 Correct 121 ms 540088 KB Output is correct
23 Correct 112 ms 538080 KB Output is correct
24 Correct 113 ms 539988 KB Output is correct
25 Correct 114 ms 540244 KB Output is correct
26 Correct 115 ms 540244 KB Output is correct
27 Correct 115 ms 540248 KB Output is correct
28 Correct 114 ms 538124 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 538056 KB Output is correct
2 Correct 112 ms 537936 KB Output is correct
3 Correct 123 ms 540120 KB Output is correct
4 Correct 115 ms 540116 KB Output is correct
5 Correct 116 ms 540240 KB Output is correct
6 Correct 114 ms 540240 KB Output is correct
7 Correct 119 ms 540244 KB Output is correct
8 Correct 116 ms 540240 KB Output is correct
9 Correct 122 ms 540240 KB Output is correct
10 Correct 116 ms 540244 KB Output is correct
11 Correct 114 ms 540236 KB Output is correct
12 Correct 114 ms 540220 KB Output is correct
13 Correct 113 ms 540112 KB Output is correct
14 Correct 114 ms 538232 KB Output is correct
15 Correct 122 ms 537940 KB Output is correct
16 Correct 123 ms 540104 KB Output is correct
17 Correct 144 ms 540240 KB Output is correct
18 Correct 118 ms 540240 KB Output is correct
19 Correct 115 ms 537940 KB Output is correct
20 Correct 126 ms 540240 KB Output is correct
21 Correct 133 ms 540196 KB Output is correct
22 Correct 121 ms 540088 KB Output is correct
23 Correct 112 ms 538080 KB Output is correct
24 Correct 113 ms 539988 KB Output is correct
25 Correct 114 ms 540244 KB Output is correct
26 Correct 115 ms 540244 KB Output is correct
27 Correct 115 ms 540248 KB Output is correct
28 Correct 114 ms 538124 KB Output is correct
29 Correct 122 ms 540208 KB Output is correct
30 Correct 122 ms 540248 KB Output is correct
31 Correct 118 ms 540204 KB Output is correct
32 Correct 117 ms 540084 KB Output is correct
33 Correct 115 ms 540248 KB Output is correct
34 Correct 117 ms 540168 KB Output is correct
35 Correct 119 ms 540284 KB Output is correct
36 Correct 116 ms 540236 KB Output is correct
37 Correct 114 ms 540140 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 538056 KB Output is correct
2 Correct 112 ms 537936 KB Output is correct
3 Correct 123 ms 540120 KB Output is correct
4 Correct 115 ms 540116 KB Output is correct
5 Correct 116 ms 540240 KB Output is correct
6 Correct 114 ms 540240 KB Output is correct
7 Correct 119 ms 540244 KB Output is correct
8 Correct 116 ms 540240 KB Output is correct
9 Correct 122 ms 540240 KB Output is correct
10 Correct 116 ms 540244 KB Output is correct
11 Correct 114 ms 540236 KB Output is correct
12 Correct 114 ms 540220 KB Output is correct
13 Correct 113 ms 540112 KB Output is correct
14 Correct 114 ms 538232 KB Output is correct
15 Correct 122 ms 537940 KB Output is correct
16 Correct 123 ms 540104 KB Output is correct
17 Correct 144 ms 540240 KB Output is correct
18 Correct 118 ms 540240 KB Output is correct
19 Correct 115 ms 537940 KB Output is correct
20 Correct 126 ms 540240 KB Output is correct
21 Correct 133 ms 540196 KB Output is correct
22 Correct 121 ms 540088 KB Output is correct
23 Correct 112 ms 538080 KB Output is correct
24 Correct 113 ms 539988 KB Output is correct
25 Correct 114 ms 540244 KB Output is correct
26 Correct 115 ms 540244 KB Output is correct
27 Correct 115 ms 540248 KB Output is correct
28 Correct 114 ms 538124 KB Output is correct
29 Correct 122 ms 540208 KB Output is correct
30 Correct 122 ms 540248 KB Output is correct
31 Correct 118 ms 540204 KB Output is correct
32 Correct 117 ms 540084 KB Output is correct
33 Correct 115 ms 540248 KB Output is correct
34 Correct 117 ms 540168 KB Output is correct
35 Correct 119 ms 540284 KB Output is correct
36 Correct 116 ms 540236 KB Output is correct
37 Correct 114 ms 540140 KB Output is correct
38 Correct 238 ms 574212 KB Output is correct
39 Runtime error 311 ms 1048576 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 537940 KB Output is correct
2 Correct 113 ms 537940 KB Output is correct
3 Correct 111 ms 537936 KB Output is correct
4 Correct 114 ms 537868 KB Output is correct
5 Correct 130 ms 538240 KB Output is correct
6 Correct 114 ms 540120 KB Output is correct
7 Correct 113 ms 540240 KB Output is correct
8 Correct 112 ms 537940 KB Output is correct
9 Correct 116 ms 537928 KB Output is correct
10 Correct 124 ms 539948 KB Output is correct
11 Correct 118 ms 537876 KB Output is correct
12 Correct 116 ms 540320 KB Output is correct
13 Incorrect 177 ms 540792 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 537936 KB Output is correct
2 Correct 113 ms 538080 KB Output is correct
3 Correct 114 ms 537956 KB Output is correct
4 Correct 138 ms 540500 KB Output is correct
5 Correct 165 ms 540896 KB Output is correct
6 Correct 114 ms 540124 KB Output is correct
7 Correct 116 ms 540108 KB Output is correct
8 Correct 116 ms 540244 KB Output is correct
9 Correct 226 ms 574012 KB Output is correct
10 Runtime error 218 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -