Submission #852877

#	Time	Username	Problem	Language	Result	Execution time	Memory
852877		12345678	Werewolf (IOI18_werewolf)	C++17	0 / 100	134 ms	30816 KiB

werewolf

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

using namespace std;

const int nx=3e3+5;
int dsu[nx];
vector<tuple<int, int, int>> dmn, dmx;

int find(int x)
{
  if (dsu[x]==x) return x;
  return dsu[x]=find(dsu[x]);
}

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) {
  for (int i=0; i<X.size(); i++) dmn.push_back({max(X[i], Y[i]), X[i], Y[i]}), dmx.push_back({min(X[i], Y[i]), X[i], Y[i]});
  sort(dmn.begin(), dmn.end());
  sort(dmx.begin(), dmx.end());
  reverse(dmx.begin(), dmx.end());
  int Q = S.size();
  vector<int> A(Q);
  for (int i=0; i<Q; i++)
  {
    for (int j=0; j<N; j++) dsu[j]=j;
    for (int j=0; j<dmx.size(); j++)
    {
      auto [w, u, v]=dmx[j];
      if (w<L[i]) break;
      int pu=find(u), pv=find(v);
      if (pu!=pv) dsu[pu]=pv;
    }
    for (int j=0; j<dmn.size(); j++)
    {
      auto [w, u, v]=dmn[j];
      if (w>R[i]) break;
      int pu=find(u), pv=find(v);
      if (pu!=pv) dsu[pu]=pv;
    }
    A[i]=find(S[i])==find(E[i]);
  }
  return A;
}

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:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for (int i=0; i<X.size(); i++) dmn.push_back({max(X[i], Y[i]), X[i], Y[i]}), dmx.push_back({min(X[i], Y[i]), X[i], Y[i]});
      |                 ~^~~~~~~~~
werewolf.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int j=0; j<dmx.size(); j++)
      |                   ~^~~~~~~~~~~
werewolf.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int j=0; j<dmn.size(); j++)
      |                   ~^~~~~~~~~~~

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