Submission #835944

#	Time	Username	Problem	Language	Result	Execution time	Memory
835944		thimote75	Werewolf (IOI18_werewolf)	C++14	0 / 100	244 ms	40756 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

igrid roads;

struct UFD {
  idata parents;

  UFD (int size) {
    parents.resize(size);
    iota(parents.begin(), parents.end(), 0);
  }

  int boss (int x) {
    if (parents[x] != x)
      parents[x] = boss(parents[x]);
    return parents[x];
  }
  void merge (int a, int b) {
    a = boss(a); b = boss(b);

    parents[b] = a;
  }
};

struct Query {
  int id, date, node;

  Query (int id, int date, int node) : id(id), date(date), node(node) {}

  bool operator< (const Query &other) {
    return date < other.date;
  }
};

using vQuery = vector<Query>;

idata check_validity(int N, idata X, idata Y,
                            idata S, idata E,
                            idata L, idata R) {
  int M = X.size(); int Q = S.size();

  roads.resize(N);
  for (int i = 0; i < M; i ++) {
    roads[X[i]].push_back(Y[i]);
    roads[Y[i]].push_back(X[i]);
  }

  vQuery query_array;
  for (int i = 0; i < Q; i ++)
    query_array.push_back(Query(i, L[i], S[i]));
  
  sort (query_array.begin(), query_array.end());
  int iQ = Q - 1;
  idata answers0(Q);

  UFD ufd(N);
  for (int i = N - 1; i >= 0; i --) {
    for (int next : roads[i]) if (next > i)
      ufd.merge(i, next);
    
    while (iQ != -1 && query_array[iQ].date == i) {
      answers0[query_array[iQ].id] = ufd.boss(query_array[iQ].node);
      iQ --;
    }
  }

  vQuery query_array2;
  for (int i = 0; i < Q; i ++) {
    query_array2.push_back(Query(i * 2,     R[i], E[i]));
    query_array2.push_back(Query(i * 2 + 1, R[i], answers0[i]));
  }

  sort (query_array2.begin(), query_array2.end());
  int iQ2 = 0;
  idata answers1(2 * Q);

  ufd = UFD(N);

  for (int i = 0; i < N; i ++) {
    for (int next : roads[i]) if (next < i)
      ufd.merge(i, next);
    
    while (iQ2 != answers1.size() && query_array2[iQ2].date == i) {
      answers1[query_array2[iQ2].id] = ufd.boss(query_array2[iQ2].node);
      iQ2 ++;
    }
  }

  idata A(Q);

  for (int i = 0; i < Q; i ++)
    A[i] = answers1 [i * 2] == answers1[i * 2 + 1] ? 1 : 0;

  return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'idata check_validity(int, idata, idata, idata, idata, idata, idata)':
werewolf.cpp:90:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     while (iQ2 != answers1.size() && query_array2[iQ2].date == i) {
      |            ~~~~^~~~~~~~~~~~~~~~~~

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