제출 #989999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989999		OAleksa	늑대인간 (IOI18_werewolf)	C++14	0 / 100	559 ms	182584 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 4e5 + 69;
const int M = 20 * N;
/*
g++ werewolf.cpp werewolf.h grader.cpp
./a.out
*/
int p[N], sz[N], par[N], vis[N];
vector<pair<int, int>> t[N];
vector<pair<int, int>> qs[N][2];
vector<int> g[N], dsu[2 * N][2];
int tin1[N], tout1[N], timer, tin2[N], tout2[N];
int rt[N], lc[M], rc[M], st[M], cs[N], node, x[N], y[N];
pair<int, int> str[N], ed[N];
int root(int v) {
	if (p[v] == v)
		return v;
	return p[v] = root(p[v]);
}
void dfs(int v, int t) {
	if (t == 0) {
		tin1[v] = ++timer;
		x[v] = tin1[v];
	}
	else {
		tin2[v] = ++timer;
		y[v] = tin2[v];
	}
	for (auto u : dsu[v][t])
		dfs(u, t);
	if (t == 0)
		tout1[v] = timer;
	else
		tout2[v] = timer;
}
void modify(int v, int v1, int tl, int tr, int p) {
	if (tl == tr) 
		st[v] = 1;
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid) {
			lc[v] = ++node;
			rc[v] = rc[v1];
			modify(lc[v], lc[v1], tl, mid, p);
		}
		else {
			rc[v] = ++node;
			lc[v] = lc[v1];
			modify(rc[v], rc[v1], mid + 1, tr, p);
		}
		st[v] = st[lc[v]] + st[rc[v]];
	}
}
int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return 0;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return get(lc[v], tl, mid, l, r) + get(rc[v], mid + 1, tr, l, r);
	}
}
vector<int> check_validity(int n, vector<int> u, vector<int> v, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
  int q = s.size();
  int m = u.size();
  vector<int> ans(q);
  for (int i = 0;i < m;i++) {
  	++u[i], ++v[i];
  	g[u[i]].push_back(v[i]);
  	g[v[i]].push_back(u[i]);
  }
  for (int i = 0;i < q;i++) {
  	l[i]++, r[i]++;
  	s[i]++, e[i]++;
  }
  for (int i = 1;i <= 2 * n;i++) {
  	p[i] = i;
  	sz[i] = 1;
  }
  for (int i = 0;i < q;i++) {
  	qs[l[i]][0].push_back({r[i], i});
  	qs[r[i]][1].push_back({l[i], i});
  }	
  node = n;
  for (int i = n;i >= 1;i--) {
  	vis[i] = 1;
  	++node;
  	p[i] = node;
  	sz[node] = 2;
  	dsu[node][0].push_back(i);
  	for (auto j : g[i]) {
  		if (vis[j]) {
  			int x = root(j);
  			int y = root(node);
  			if (x != y) {
  				dsu[node][0].push_back(x);
  				p[x] = node;
  			}
  		}
  	}
  }
  assert(node == 2 * n);
  dfs(node, 0);
  node = n;
  for (int i = 1;i <= 2 * n;i++) {
  	vis[i] = 0;
  	p[i] = i;
  	sz[i] = 1;
  }
	for (int i = 1;i <= n;i++) {
		vis[i] = 1;
		++node;
		p[i] = node;
		sz[node] = 2;
		dsu[node][1].push_back(i);
		for (auto j : g[i]) {
			if (vis[j]) {
				int x = root(j);
				int y = root(node);
				if (x != y) {
					dsu[node][1].push_back(x);
					p[x] = node;
				}
			}
		}
	}
	assert(node == 2 * n);
	timer = 0;
	dfs(node, 1);
	for (int i = 1;i <= n;i++) {
		cs[x[i]] = y[i];
	}
	node = 0;
	for (int i = 2 * n;i >= 1;i--) {
		rt[i] = rt[i + 1];
		if (cs[i] > 0) {
			int nr = ++node;
			modify(nr, rt[i + 1], 1, N, cs[i]);
			rt[i] = nr;
		}
	}
	node = n;
	for (int i = 1;i <= 2 * n;i++) {
		p[i] = i, sz[i] = 1;
		vis[i] = 0;
	}
	for (int i = n;i >= 1;i--) {
  	vis[i] = 1;
  	++node;
  	p[i] = node;
  	sz[node] = 2;
  	for (auto j : g[i]) {
  		if (vis[j]) {
  			int x = root(j);
  			int y = root(node);
  			if (x != y) 
  				p[x] = node;
  		}
  	}
  	for (auto j : qs[i][0]) {
  		int ind = j.s;
  		int x = root(s[ind]);
  		str[ind] = {tin1[x], tout1[x]};
  	}
  }
	node = n;
	for (int i = 1;i <= 2 * n;i++) {
		p[i] = i, sz[i] = 1;
		vis[i] = 0;
	}
	for (int i = 1;i <= n;i++) {
  	vis[i] = 1;
  	++node;
  	p[i] = node;
  	sz[node] = 2;
  	for (auto j : g[i]) {
  		if (vis[j]) {
  			int x = root(j);
  			int y = root(node);
  			if (x != y) 
  				p[x] = node;
  		}
  	}
  	for (auto j : qs[i][1]) {
  		int ind = j.s;
  		int x = root(e[ind]);
  		ed[ind] = {tin2[x], tout2[x]};
  	}
  }
	for (int i = 0;i < q;i++) {
		int x1 = str[i].f, y1 = str[i].s;
		int x2 = ed[i].f, y2 = ed[i].s;
		//da li se nesto pojavljuje u ovom pravougaoniku
		int r = get(rt[x1], 1, N, x2, N);
		r -= get(rt[x1], 1, N, y2 + 1, N);
		r -= get(rt[y1 + 1], 1, N, x2, N);
		r += 2 * get(rt[y1 + 1], 1, N, y2 + 1, N);
		ans[i] = (r > 0); 
	}
  return ans;	
}
/*
6 6 3
5 1
1 2
2 5
1 3
3 4
0 3
4 2 1 2
4 2 2 2
5 4 3 4
*/

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