Submission #1245705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245705		adriines06	Werewolf (IOI18_werewolf)	C++20	15 / 100	4093 ms	31108 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>adj;
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 Q = S.size();
  vector<int> A(Q,0);
  adj.resize(N);
  for(int i=0;i<X.size();i++){
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  for(int i=0;i<Q;i++){
    //humano
    unordered_set<int>h;
    queue<int>q;
    q.push(S[i]);
    int f=E[i];
    while(!q.empty()){
      int u=q.front();
      q.pop();
      if(u>=L[i]){
        //cout<<u<<" ";
        h.insert(u);
        for(int v: adj[u]){
          if(h.count(v)!=1){
            q.push(v);
          }
        }
      }
    }
    //cout<<"L"<<L[i]<<"\n";
    //for(int x: h) cout<<x<<" ";
    //cout<<"\n";
    //lobo
    queue<int>qr;
    unordered_set<int>l;
    qr.push(E[i]);
    f=S[i];
    while(!qr.empty()){
      int u=qr.front();
      qr.pop();
      if(u<=R[i]){
        l.insert(u);
        for(int v: adj[u]){
          if(l.count(v)!=1){
            qr.push(v);
          }
        }
      }
    }
    for(int x: h){
      if(l.count(x)){
        //cout<<"P:"<<x<<"\n";
        A[i]=1;
        break;
      }
    }

  }
  //cout<<"\n";
  return A;
}

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