Submission #968957

#	Time	Username	Problem	Language	Result	Execution time	Memory
968957		duckindog	Werewolf (IOI18_werewolf)	C++17	15 / 100	636 ms	19800 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int N = 3'000 + 10;
vector<int> ad[N];
bool f[N][2];
int mk[N];

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 m = x.size(), q = s.size();
  for (int i = 0; i < m; ++i) { 
    int u = x[i], v = y[i];
    ad[u].push_back(v);
    ad[v].push_back(u);
  }
  
  if (n <= 3000 && m <= 6000 && q <= 3000) { 
    vector<int> answer;
    for (int i = 0; i < q; ++i) { 
      vector<vector<int>> f(n, vector<int>(2));
      vector<int> mk(n);
      
      for (int j = 0; j < n; ++j) mk[j] = (j < l[i] ? 0 : j <= r[i] ? 1 : 2);

      queue<int> que;
      f[s[i]][0] = f[s[i]][mk[s[i]] == 1] = true;
      que.push(s[i]);
      while (que.size()) { 
        auto u = que.front(); que.pop();
        for (const auto& v : ad[u]) { 
          if (f[v][0] && f[v][1]) continue;
          pair<int, int> pre = {f[v][0], f[v][1]};
          if (mk[v] >= 1) f[v][0] |= f[u][0];
          if (mk[v] <= 1) f[v][1] |= (f[u][1] || mk[v] == 1);
          if (make_pair(f[v][0], f[v][1]) != pre) que.push(v);
        }
      }
      
      answer.push_back(f[e[i]][1]);
    }
    return answer;
  }
}

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:47:1: warning: control reaches end of non-void function [-Wreturn-type]
   47 | }
      | ^

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