Submission #1268485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268485		Noname_1900	Werewolf (IOI18_werewolf)	C++17	15 / 100	4091 ms	32104 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 200000;
vector<int> chemins[NMAX];
int dejaVu[2][NMAX];
int iDejaVu;
bool possible(int noeud, int fin, int interditHomme, int interditLoup, bool etat)
{
  if(dejaVu[etat][noeud] == iDejaVu)
    return false;
  dejaVu[etat][noeud] = iDejaVu;
  if(etat == 0)
  {
    if(noeud < interditHomme)  {
      //cout << noeud << " " << etat << " : " << false << endl;
      return false;
    }
    if(possible(noeud, fin, interditHomme, interditLoup, 1))  
    {
      //cout << noeud << " " << etat << " : " << true << endl;
      return true;
    }
  }
  else if(noeud > interditLoup)  {
    //cout << noeud << " " << etat << " : " << false << endl;
    return false;
  }
  if((noeud == fin) && (etat == 1))  {
    //cout << noeud << " " << etat << " : " << true << endl;
    return true;
  }
  for(auto pro : chemins[noeud])
  {
    if(possible(pro, fin, interditHomme, interditLoup, etat)) {
      //cout << noeud << " " << etat << " : " << true << endl;
      return true;
    }
  }
  //cout << noeud << " " << etat << " : " << false << endl;
  return false;
  
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  int nbNoeuds = N, nbChemins = X.size();
  iDejaVu = 1;
  for(int i = 0; i < nbChemins; i++)
  {
    chemins[X[i]].push_back(Y[i]);
    chemins[Y[i]].push_back(X[i]);
  }
  int Q = S.size();
  std::vector<int> A(Q);
  for (int i = 0; i < Q; ++i) {
    //cout << "deb " << S[i] << " " << E[i] << " " << L[i] << " " << R[i] << endl;
    A[i] = possible(S[i], E[i], L[i], R[i], 0);
    iDejaVu++;
  }
  return A;
}

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