Submission #1182494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182494		HappyCapybara	Werewolf (IOI18_werewolf)	C++17	15 / 100	4094 ms	38804 KiB

werewolf

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

int cm, cnt;
vector<int> vs, ve, sl, sr, el, er, pp, pm, pl, pr;
vector<vector<int>> g;

int find(int a){
  if (a == pp[a]) return pp[a];
  return pp[a] = find(pp[a]);
}

void merge(int a, int b, bool sht=false){
  //cout << a << " " << b << endl;
  a = find(a);
  b = find(b);
  if (a == b) return;
  pp[b] = a;
  pl[a] = min(pl[a], pl[b]);
  pr[a] = max(pr[a], pr[b]);
  if (sht) return;
  if (pm[a] == -1) g[cm].push_back(-a-1);
  else g[cm].push_back(pm[a]);
  if (pm[b] == -1) g[cm].push_back(-b-1);
  else g[cm].push_back(pm[b]);
  pm[a] = cm;
  cm++;
}

void dfs(int cur, vector<int>& v){
  if (cur < 0){
    v[-cur-1] = cnt;
    cnt++;
    return;
  }
  for (int next : g[cur]) dfs(next, v);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
  int M = X.size();
  int Q = S.size();
  vector<pair<int,pair<int,int>>> es, ee;
  for (int i=0; i<M; i++){
    es.push_back({min(X[i], Y[i]), {X[i], Y[i]}});
    ee.push_back({max(X[i], Y[i]), {X[i], Y[i]}});
  }
  vector<pair<int,pair<int,int>>> qs, qe;
  for (int i=0; i<Q; i++){
    qs.push_back({L[i], {S[i], i}});
    qe.push_back({R[i], {E[i], i}});
  }
  //cout << "a" << endl;
  sort(es.begin(), es.end());
  sort(ee.begin(), ee.end());
  sort(qs.begin(), qs.end());
  sort(qe.begin(), qe.end());
  vs.resize(N);
  ve.resize(N);
  sl.resize(Q);
  sr.resize(Q);
  el.resize(Q);
  er.resize(Q);
  pp.resize(N);
  pm.resize(N);
  pl.resize(N);
  pr.resize(N);
  //cout << "b" << endl;

  for (int i=0; i<N; i++){
    pp[i] = i;
    pm[i] = -1;
  }
  g.assign(N-1, vector<int>(0));
  cm = 0;
  for (int i=M-1; i>=0; i--) merge(es[i].second.first, es[i].second.second);
  //cout << "c" << endl;
  cnt = 0;
  dfs(N-2, vs);
  //cout << "d" << endl;
  for (int i=0; i<N; i++){
    pp[i] = i;
    pl[i] = vs[i];
    pr[i] = vs[i];
  }
  //for (int i=0; i<N; i++) cout << vs[i] << " ";
  //cout << endl;
  //cout << "e" << endl;
  int cur = Q-1;
  for (int i=M-1; i>=0; i--){
    //cout << i << endl;
    while (cur >= 0 && es[i].first < qs[cur].first){
      //cout << cur << endl;
      sl[qs[cur].second.second] = pl[find(qs[cur].second.first)];
      sr[qs[cur].second.second] = pr[find(qs[cur].second.first)];
      cur--;
    }
    //cout << "!" << endl;
    merge(es[i].second.first, es[i].second.second, true);
    //cout << "?" << endl;
  }
  //cout << "f" << endl;
  while (cur >= 0){
    sl[qs[cur].second.second] = pl[find(qs[cur].second.first)];
    sr[qs[cur].second.second] = pr[find(qs[cur].second.first)];
    cur--;
  }

  for (int i=0; i<N; i++){
    pp[i] = i;
    pm[i] = -1;
  }
  g.assign(N-1, vector<int>(0));
  cm = 0;
  for (int i=0; i<M; i++) merge(ee[i].second.first, ee[i].second.second);
  cnt = 0;
  dfs(N-2, ve);
  for (int i=0; i<N; i++){
    pp[i] = i;
    pl[i] = ve[i];
    pr[i] = ve[i];
  }
  cur = 0;
  for (int i=0; i<M; i++){
    while (cur < Q && ee[i].first > qe[cur].first){
      el[qe[cur].second.second] = pl[find(qe[cur].second.first)];
      er[qe[cur].second.second] = pr[find(qe[cur].second.first)];
      cur++;
    }
    merge(ee[i].second.first, ee[i].second.second, true);
  }
  while (cur < Q){
    el[qe[cur].second.second] = pl[find(qe[cur].second.first)];
    er[qe[cur].second.second] = pr[find(qe[cur].second.first)];
    cur++;
  }

  vector<int> A(Q);
  for (int i=0; i<Q; i++){
    A[i] = 0;
    for (int j=0; j<N; j++){
      if (sl[i] <= vs[j] && vs[j] <= sr[i] && el[i] <= ve[j] && ve[j] <= er[i]) A[i] = 1;
    }
  }
  return A;
}

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