Submission #340945

#	Time	Username	Problem	Language	Result	Execution time	Memory
340945		a_player	Werewolf (IOI18_werewolf)	C++14	15 / 100	2032 ms	21356 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#ifdef ALE
#include "grader.cpp"
#endif
#define f first
#define s second

using namespace std;

const int nax=3e3+3;

vector<int> grafo[nax];
int dp[nax][2];
queue<pair<int,bool> > q;
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
  int Q = S.size();
  vector<int> A(Q);
  for(int i=0;i<X.size();i++){
    grafo[X[i]].push_back(Y[i]);
    grafo[Y[i]].push_back(X[i]);
  }
  for(int i=0;i<Q;i++){
    memset(dp,-1,sizeof(dp));
    q.emplace(S[i],0);
    while(!q.empty()){
      auto co=q.front();
      q.pop();
      if(!co.s&&co.f<L[i]){
        dp[co.f][co.s]=0;
        continue;
      }
      if(co.s&&co.f>R[i]){
        dp[co.f][co.s]=0;
        continue;
      }
      dp[co.f][co.s]=1;
      if(co.s==0&&dp[co.f][1]==-1)q.emplace(co.f,1);
      for(int x:grafo[co.f]){
        if(co.s==0&&dp[x][0]==-1)q.emplace(x,0);
        if(co.s==1&&dp[x][1]==-1)q.emplace(x,1);
      }
    }
    A[i]=(dp[E[i]][1]==1);
  }
  return A;
}

Compilation message (stderr)

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:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i=0;i<X.size();i++){
      |               ~^~~~~~~~~

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