Submission #569512

#	Time	Username	Problem	Language	Result	Execution time	Memory
569512		NemanjaSo2005	Werewolf (IOI18_werewolf)	C++14	0 / 100	4016 ms	39252 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M,Q,prosli[200005],pos[200005],pvred;
vector<int> graf[200005],ret;
struct kveri{
   int poc,kraj,id;
   ll L,R;
} upiti[200005];
void dfs(int gde,int L,int R){
  // cout<<"DFS sa "<<pvred<<" u "<<gde<<endl;
   prosli[gde]=pvred;
   pos[gde]++;
   for(int i=0;i<graf[gde].size();i++){
      if(prosli[graf[gde][i]]==pvred)
         continue;
      //cout<<graf[gde][i]<<" "<<L<<" "<<R<<endl;
      if(graf[gde][i]<L)
         continue;
      if(graf[gde][i]>R)
         continue;
     // cout<<"DALJE"<<endl;
      dfs(graf[gde][i],L,R);
   }
}
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=R[i];
      upiti[i+1].R=L[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);
        // for(int i=1;i<=N;i++)
         //   cout<<pos[i]<<" ";
         //cout<<endl;
         pvred++;
         dfs(upiti[j].kraj,1,upiti[j].R);
         //for(int i=1;i<=N;i++)
          //  cout<<pos[i]<<" ";
         //cout<<endl;
         ret[upiti[j].id]=0;
         for(int i=1;i<=N;i++)
            if(pos[i]==2)
               ret[upiti[j].id]=1;
      }
      return ret;
   }
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(int, 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 '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:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^

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