Submission #293735

#	Time	Username	Problem	Language	Result	Execution time	Memory
293735		TheLorax	Werewolf (IOI18_werewolf)	C++11	0 / 100	4066 ms	27092 KiB

werewolf

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

#define F first
#define S second
#define SZ(a) ((int)(a).size())
#define PB push_back
#define ALL(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;

struct UF{
  std::vector<int> p;
  UF(int n){
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
  int root(int a){
    if(a==p[a]) return a;
    return (p[a]=root(p[a]));
  }
  bool find(int a, int b) { return root(a)==root(b); }
  void connect(int a, int b) { p[root(a)]=root(b); }
};

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) {
  int q = s.size(), m = SZ(x);
  std::vector<ii> eld(m), eli(m);
  for(int i=0; i<n; i++){
    if(x[i]>y[i])
      swap(x[i],y[i]);
    eld[i]={x[i],y[i]};
    eli[i]={y[i],x[i]};
  }
  sort(ALL(eli));
  sort(ALL(eld));
  reverse(ALL(eld));
  std::vector<int> a(q,0);
  for(int t=0; t<q; t++){
    UF h(n), w(n);
    for(int i=0; i<m && eld[i].F>=l[t]; i++){
      h.connect(eld[i].F, eld[i].S);
      // fprintf(stderr, "%d ", eld[i].F);
    }
    // fprintf(stderr, "\n");
    for(int i=0; i<m && eli[i].F<=r[t]; i++){
      w.connect(eli[i].F,eli[i].S);
      // fprintf(stderr, "%d ", eli[i].F);
    }
    // fprintf(stderr, "\n");
    for(int i=l[t]; i<=r[t]; i++){
      a[t]|=(h.find(s[t],i)&&w.find(e[t],i));
      // fprintf(stderr, "%d %d\n", i, a[t]);
    }
  }
  return a;
}

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