oj.uz

답안 #877863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
877863 2023-11-23T19:26:16 Z vivkostov Jail (JOI22_jail) C++14
0 / 100
 94 ms 62100 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,in,brr,a[200005],b[200005],child[200005],machild[200005],used[200005],up[200005],bin[200005][30],level[200005],usedl[200005];
vector<int>v[200005],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++;
    used[beg]=in;
    if(!last)last=used[beg];
    up[beg]=last;
    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,used[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 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);
        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<=20; 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);
    }
}
int lca(int x,int y)
{
    if(level[x]>level[y])swap(x,y);
    for(int i=20; i>=0; i--)
    {
        if(level[bin[y][i]]>=level[x])y=bin[y][i];
    }
    if(x==y)return x;
    for(int i=20; 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_heavy1(int beg,int lc,int prisoner)
{
    if(level[up[beg]]==level[lc])
    {
        update(1,n,up[beg],beg,1,prisoner,2);
        return;
    }
    if(level[up[beg]]>level[lc])
    {
        update(1,n,up[beg],beg,1,prisoner,2);
        go_up_heavy1(bin[up[beg]][0],lc,prisoner);
        return;
    }
    update(1,n,lc,beg,1,prisoner,2);
}
void go_up_heavy2(int beg,int lc,int prisoner)
{
    if(beg==lc)return;
    if(level[up[beg]]==level[lc])
    {
        update(1,n,up[beg]+1,beg,1,prisoner,2);
        return;
    }
    if(level[up[beg]]>level[lc])
    {
        update(1,n,up[beg],beg,1,prisoner,2);
        go_up_heavy2(bin[up[beg]][0],lc,prisoner);
        return;
    }
    update(1,n,lc+1,beg,1,prisoner,2);
}
void add_path()
{
    for(int i=1; i<=m; i++)
    {
        int g=used[lca(a[i],b[i])];
        go_up_heavy1(used[a[i]],g,i);
        go_up_heavy2(used[b[i]],g,i);
    }
}
void fill_cycle(int beg)
{
    usedl[beg]=2;
    int w;
    for(int i=0; i<p[beg].size(); i++)
    {
        w=p[beg][i];
        if(usedl[w]!=2)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);
        brr++;
    }
}
void resh()
{
    find_child(1,0,1);
    heavylight(1,1);
    make_start(1,n,1);
    add_all();
    make_bin();
    add_path();
    /*for(int i=1; i<=27; i++)
    {
        cout<<i<<" : ";
        for(int j=0; j<p[i].size(); j++)
        {
            cout<<p[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    exit(0);
    */
    for(int i=1; i<=m; i++)
    {
        if(!usedl[i])find_cycle(i);
    }
    if(brr!=m)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    for(int i=0; i<=n*100; 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;
        v[i].clear();
        for(int j=0; j<=25; j++)bin[i][j]=0;
    }
    for(int i=0; i<=200*n; i++)p[i].clear();
    in=0;
    brr=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:19: 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:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0; i<v[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
jail.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0; i<v[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
jail.cpp:35:11: warning: unused variable 'ma' [-Wunused-variable]
   35 |     int w,ma=0;
      |           ^~
jail.cpp: In function 'void fill_cycle(int)':
jail.cpp:152:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
jail.cpp: In function 'void find_cycle(int)':
jail.cpp:162:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for(int i=0; i<p[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 57944 KB Output is correct
2 Correct 12 ms 58096 KB Output is correct
3 Correct 12 ms 57944 KB Output is correct
4 Incorrect 94 ms 60508 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 58092 KB Output is correct
2 Correct 12 ms 57948 KB Output is correct
3 Incorrect 21 ms 62100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 58092 KB Output is correct
2 Correct 12 ms 57948 KB Output is correct
3 Incorrect 21 ms 62100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 58092 KB Output is correct
2 Correct 12 ms 57948 KB Output is correct
3 Incorrect 21 ms 62100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 58092 KB Output is correct
2 Correct 12 ms 57948 KB Output is correct
3 Incorrect 21 ms 62100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 58092 KB Output is correct
2 Correct 13 ms 57944 KB Output is correct
3 Correct 12 ms 58200 KB Output is correct
4 Correct 12 ms 58200 KB Output is correct
5 Incorrect 44 ms 57948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 57944 KB Output is correct
2 Correct 12 ms 58096 KB Output is correct
3 Correct 12 ms 57944 KB Output is correct
4 Incorrect 94 ms 60508 KB Output isn't correct
5 Halted 0 ms 0 KB -