제출 #569550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569550		NemanjaSo2005	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4073 ms	35448 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M,K,Q,prosli[200005],pos[200005],pvred,mesto[200005],niz[200005],stmax[525000],stmin[525000];
vector<int> graf[200005],ret;
struct kveri{
   int poc,kraj,id;
   ll L,R;
} upiti[200005];
void dfs2(int gde,int dub){
   prosli[gde]=pvred;
   mesto[gde]=dub;
   niz[dub]=gde;
   for(int i=0;i<graf[gde].size();i++)
      if(prosli[graf[gde][i]]!=pvred)
         dfs2(graf[gde][i],dub+1);
   return;
}
void dfs(int gde,int L,int R){
   prosli[gde]=pvred;
   pos[gde]++;
   for(int i=0;i<graf[gde].size();i++){
      if(prosli[graf[gde][i]]==pvred)
         continue;
      if(graf[gde][i]<L)
         continue;
      if(graf[gde][i]>R)
         continue;
      dfs(graf[gde][i],L,R);
   }
}
ll getmax(int gde,int lg,int dg,int lc,int dc){
   if(lg>dg)
      swap(lg,dg);
   if(lg==lc and dg==dc)
      return stmax[gde];
   int sred=(lc+dc)/2;
   if(dg<=sred)
      return getmax(gde*2,lg,dg,lc,sred);
   if(lg>sred)
      return getmax(gde*2+1,lg,dg,sred+1,dc);
   return max(getmax(gde*2,lg,sred,lc,sred),getmax(gde*2+1,sred+1,dg,sred+1,dc));
}
ll getmin(int gde,int lg,int dg,int lc,int dc){
   if(lg>dg)
      swap(lg,dg);
   if(lg==lc and dg==dc)
      return stmin[gde];
   int sred=(lc+dc)/2;
   if(dg<=sred)
      return getmin(gde*2,lg,dg,lc,sred);
   if(lg>sred)
      return getmin(gde*2+1,lg,dg,sred+1,dc);
   return min(getmin(gde*2,lg,sred,lc,sred),getmin(gde*2+1,sred+1,dg,sred+1,dc));
}
vector<int> check_validity(int NN, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
   N=NN;
   M=X.size();
   Q=L.size();
   ret.resize(Q);
   for(int i=0;i<M;i++){
      X[i]++;
      Y[i]++;
      graf[X[i]].push_back(Y[i]);
      graf[Y[i]].push_back(X[i]);
   }
   for(int i=0;i<Q;i++){
      S[i]++;
      E[i]++;
      L[i]++;
      R[i]++;
      upiti[i+1].id=i;
      upiti[i+1].poc=S[i];
      upiti[i+1].kraj=E[i];
      upiti[i+1].L=L[i];
      upiti[i+1].R=R[i];
   }
   if(N*Q<=10000000){
      for(int j=1;j<=Q;j++){
         for(int i=1;i<=N;i++)
            pos[i]=0;
         pvred++;
         dfs(upiti[j].poc,upiti[j].L,N);
         pvred++;
         dfs(upiti[j].kraj,1,upiti[j].R);
         ret[upiti[j].id]=0;
         for(int i=1;i<=N;i++)
            if(pos[i]==2)
               ret[upiti[j].id]=1;
      }
      return ret;
   }
   if(N==M+1){
      for(int i=1;i<=N;i++)
         if(graf[i].size()==1){
            dfs2(i,1);
            break;
         }
      K=1;
      while(K<N)
         K<<=1;
      for(int i=1;i<=N;i++)
         stmin[i+K-1]=stmax[i+K-1]=niz[i];
      for(int i=N+K;i<=K+K;i++)
         stmin[i]=1e9;
      for(int i=K-1;i>=1;i--){
         stmax[i]=max(stmax[i*2],stmax[i*2+1]);
         stmin[i]=min(stmin[i*2],stmin[i*2+1]);
      }
      ll lg,dg,sred,v,m;
      for(int j=1;j<=Q;j++){
         lg=mesto[upiti[j].poc];
         dg=mesto[upiti[j].kraj];
         if(lg==dg){
            ret[upiti[j].id]=1;
            continue;
         }
         if(lg<dg){
            while(lg<=dg){
               sred=(lg+dg)/2;
               v=getmax(1,mesto[upiti[j].poc],sred,1,K);
               m=getmin(1,sred,mesto[upiti[j].kraj],1,K);
               if(v>=upiti[j].L and m<=upiti[j].R){
                  ret[upiti[j].id]=1;
                  break;
               }
               if(v<upiti[j].L and m>upiti[j].R)
                  break;
               if(v>=upiti[j].L)
                  lg=sred+1;
               else
                  dg=sred-1;
            }
            continue;
         }
         swap(lg,dg);
         while(lg<=dg){
            sred=(lg+dg)/2;
            v=getmax(1,sred,mesto[upiti[j].poc],1,K);
            m=getmin(1,mesto[upiti[j].kraj],sred,1,K);
            if(v>=upiti[j].L and m<=upiti[j].R){
               ret[upiti[j].id]=1;
               break;
            }
            if(v<upiti[j].L and m>upiti[j].R)
               break;
            if(v>=upiti[j].L)
               lg=sred+1;
            else
               dg=sred-1;
         }
      }
      return ret;
   }
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |    for(int i=0;i<graf[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs(int, int, int)':
werewolf.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    for(int i=0;i<graf[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~
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:156:1: warning: control reaches end of non-void function [-Wreturn-type]
  156 | }
      | ^

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