Submission #314499

#	Time	Username	Problem	Language	Result	Execution time	Memory
314499		juggernaut	늑대인간 (IOI18_werewolf)	C++14	49 / 100	895 ms	52344 KiB

werewolf

#include"werewolf.h"
#include<bits/stdc++.h>
//#include"grader.cpp"
#define V vector
using namespace std;
V<int>g[200005];
int pos[200005],logs[200005],spx[200005][18],spn[200005][18],used[200005];
bool flag;
int gt_mx(int l,int r){
    int lev=logs[r-l+1];
    return max(spx[l][lev],spx[r-(1<<lev)+1][lev]);
}
int gt_mn(int l,int r){
    int lev=logs[r-l+1];
    return min(spn[l][lev],spn[r-(1<<lev)+1][lev]);
}
bool check(int l,int r,int nl,int nr){
    if(l>r)swap(l,r);
    return gt_mn(l,r)>=nl&&gt_mx(l,r)<=nr;
}
void man(int v,int mx){
      if(v<mx)return;
      used[v]=1;
      for(auto to:g[v])if(!used[to]&&to>=mx)man(to,mx);
}
void wolf(int v,int mx) {
      if(v>mx)return;
      if(used[v]||flag){
          flag=1;
          return;
      }
      used[v]=2;
      for(auto to:g[v])if(used[to]!=2&&to<=mx)wolf(to,mx);
}
V<int>check_validity(int n,V<int>x,V<int>y,V<int>S,V<int>E,V<int>L,V<int>R){
    V<int>res;
    int root,i,j;
    for(i=2;i<=n;i++)logs[i]=logs[i>>1]+1;
    for(i=0;i<x.size();i++){
        x[i]++;
        y[i]++;
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }
    if(n<3001&&x.size()<6001&&S.size()<3001){
        for(i=0;i<S.size();i++){
            flag=0;
            fill(used+1,used+1+n,0);
            man(S[i]+1,L[i]+1);
            wolf(E[i]+1,R[i]+1);
            res.push_back(flag);
        }
        return res;
    }
    for(i=1;i<=n;i++)if(g[i].size()==1)root=i;
    spx[1][0]=root;
    spn[1][0]=root;
    pos[root]=1;
    int p=root;
    for(i=2;i<=n;i++){
        if(g[root][0]!=p){
            p=root;
            root=g[root][0];
        }else{
            p=root;
            root=g[root][1];
        }
        spx[i][0]=root;
        spn[i][0]=root;
        pos[root]=i;
    }
    for(j=1;j<18;j++){
        for(i=1;i+(1<<j)-1<=n;i++)spn[i][j]=min(spn[i][j-1],spn[i+(1<<(j-1))][j-1]);
        for(i=1;i+(1<<j)-1<=n;i++)spx[i][j]=max(spx[i][j-1],spx[i+(1<<(j-1))][j-1]);
    }
    for(int i=0;i<S.size();i++){
        int l=pos[S[i]+1],r=pos[E[i]+1],s=L[i]+1,e=R[i]+1;
        if(l<=r){
            int mxl=n,mnr=1;
            while(l<mxl){
                int mid=(l+mxl+1)>>1;
                if(check(pos[S[i]+1],mid,s,n))l=mid;
                else mxl=mid-1;
            }
            while(mnr<r){
                int mid=(mnr+r)>>1;
                if(check(mid,pos[E[i]+1],1,e))r=mid;
                else mnr=mid+1;
            }
            res.push_back(mxl>=mnr);
        }else{
            swap(l,r);
            int mxl=n,mnr=1;
            while(l<mxl){
                int mid=(l+mxl+1)>>1;
                if(check(pos[E[i]+1],mid,1,e))l=mid;
                else mxl=mid-1;
            }
            while(mnr<r){
                int mid=(mnr+r)>>1;
                if(check(mid,pos[S[i]+1],s,n))r=mid;
                else mnr=mid+1;
            }
            res.push_back(mxl>=mnr);
        }
    }
    return res;
}
/*
10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9

/*
1
1
1
0
1
1
0
1
0
1

*/

Compilation message (stderr)

werewolf.cpp:131:1: warning: "/*" within comment [-Wcomment]
  131 | /*
      |  
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:39:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(i=0;i<x.size();i++){
      |             ~^~~~~~~~~
werewolf.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:56:14: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |     spx[1][0]=root;
      |     ~~~~~~~~~^~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51