제출 #1038811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038811		Mr_Husanboy	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4061 ms	22400 KiB

werewolf

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

using namespace std;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long

template<typename T>
int len(T &a){return a.size();}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

struct DSU{
  vector<int> par, sz; int n;
  DSU (int _n){
    n = _n;
    par.resize(n);
    iota(all(par), 0);
    sz.assign(n, 1);
  }
  DSU (){}
  int get(int a){
    return (par[a] == a ? a : par[a] = get(par[a]));
  }

  void init(int _n){
    n = _n;
    par.resize(n);
    iota(all(par), 0);
    sz.assign(n, 1);
  }

  void unite(int a, int b){
    a = get(a);
    b = get(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a,b);
    sz[a] += sz[b];
    par[b] = a;
  }

  void link(int a, int b){
    a = get(a); b = get(b);
    if(a == b) return;
    sz[b] += sz[a];
    par[a] = b;
  }
};

int n, m, q;
vector<vector<int>> g;

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) {
  n = N;
  q = len(s);
  m = len(x);
  vector<int> res(q);
  for(int i = 0; i < m; i ++) if(x[i] > y[i]) swap(x[i], y[i]);

  for(int i = 0; i < q; i ++){
    DSU hum(n), wolf(n);
    for(int j = 0; j < m; j ++){
      if(x[j] >= l[i]){
        hum.unite(y[j], x[j]);
       // cout << x[j] << ' ' << y[j];
      }
      if(y[j] <= r[i]){
        wolf.unite(x[j], y[j]);
      }
    }
    //cout << endl;
    bool ok = 0;
    for(int j = l[i]; j <= r[i]; j ++){
      if(hum.get(j) != hum.get(s[i])) continue;
      if(wolf.get(j) != wolf.get(e[i])) continue;
      ok = 1;
      break;
    }
    res[i] = ok;
  }
  return res; 
}

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