Submission #401107

#	Time	Username	Problem	Language	Result	Execution time	Memory
401107		idk321	Werewolf (IOI18_werewolf)	C++11	15 / 100	338 ms	26608 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


const int N = 200000;

vector<int> adj[N];
vector<int> s;
vector<int> e;
vector<int> l;
vector<int> r;
vector<int> x;
vector<int> y;
int n;
int q;

vector<int> vis[2];

void dfs(int node, int q1, int typ)
{
    if (typ == 0 && node < l[q1]) return;
    if (typ == 1 && node > r[q1]) return;
    vis[typ][node] = true;
    for (int next : adj[node])
    {
        if (vis[typ][next]) continue;
        dfs(next, q1, typ);
    }
}

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) {
    n = N;
    x =X;
    y =Y;
    s =S;
    e =E;
    l = L;
    r =R;

    for (int i = 0; i < x.size(); i++)
    {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }

  q = S.size();
  std::vector<int> res(q);
  if (n <= 3000 && q <= 3000)
  {
    for (int q1 = 0; q1 < q; q1++)
    {
        vis[0].clear();
        vis[0].resize(n);
        vis[1].clear();
        vis[1].resize(n);
        dfs(s[q1], q1, 0);
        dfs(e[q1], q1, 1);
        for (int i = 0; i < n; i++) if (vis[0][i] && vis[1][i]) res[q1] = 1;
    }
  }

  return res;
}

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

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