Submission #1245648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245648		matisito	Werewolf (IOI18_werewolf)	C++20	15 / 100	4091 ms	21584 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";

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) {
  vector<vector<int>>g(N);
  for(int i=0 ; i<(int)X.size() ; i++){
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  vector<int>ans((int)L.size());
  for(int i=0 ; i<(int)L.size() ; i++){
    queue<int>bfs;
    vector<bool>vis(N);
    bfs.push(S[i]);
    vis[S[i]]=1;
    while(!bfs.empty()){
      int u=bfs.front();
      bfs.pop();
      for(int v:g[u]){
        if(v>=L[i] && !vis[v]){
          vis[v]=1;
          bfs.push(v);
        }
      }
    }
    // for(bool x:vis) dbg(x)
    bfs.push(E[i]);
    vector<bool>vis1(N);
    vis1[E[i]]=1;
    bool ok=0;
    if(vis[E[i]]) ok=1;
    while(!bfs.empty()){
      int u=bfs.front();
      bfs.pop();
      for(int v:g[u]){
        if(v<=R[i]){
          if(v>=L[i] && vis[v]==1) ok=1;
          if(vis1[v]==1) continue;
          vis1[v]=1;
          bfs.push(v);
        }
        if(ok) break;
      }
      if(ok) break;
    }
    ans[i]=(ok?1:0);
  }
  return ans;
}

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