Submission #700956

#	Time	Username	Problem	Language	Result	Execution time	Memory
700956		mychecksedad	Werewolf (IOI18_werewolf)	C++17	15 / 100	4051 ms	22076 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;

struct Dsu{
  vector<int> p, s;
  Dsu(int n){
    s.resize(n + 1, 1);
    p.resize(n + 1);
    for(int i = 0; i <= n; ++i) p[i] = i;
  }
  int find(int v){
    if(v==p[v]) return v;
    return (p[v] = find(p[v]));
  }
  void merge(int a, int b){
    a = find(a);
    b = find(b);
    if(a != b){
      if(s[a] > s[b]) swap(a, b);
      p[a] = b;
      s[b] += s[a];
    }
  }
};
int n, m;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
  n = N, m = X.size();
  vector<int> ans(S.size());

  for(int q = 0; q < S.size(); ++q){
    Dsu small(n), large(n);
    for(int i = 0; i < m; ++i){
      if(X[i] <= R[q] && Y[i] <= R[q])
        small.merge(X[i], Y[i]);
      if(X[i] >= L[q] && Y[i] >= L[q])
        large.merge(X[i], Y[i]);
    }
    for(int mid = L[q]; mid <= R[q]; ++mid){
      if(small.find(mid) == small.find(E[q]) && large.find(mid) == large.find(S[q])){
        ans[q] = 1;
        break;
      }
    }
  }

  return ans;
}

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

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