Submission #989775

#	Time	Username	Problem	Language	Result	Execution time	Memory
989775		OAleksa	Werewolf (IOI18_werewolf)	C++14	0 / 100	4054 ms	85660 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 2e5 + 69;
const int K = 18;
/*
g++ werewolf.cpp werewolf.h grader.cpp
./a.out
*/
int p[N], sz[N];
int up[N][K], tin[N], tout[N], timer, mx[N][K], dep[N];
vector<pair<int, int>> t[N];
vector<pair<int, int>> qs[N];
vector<int> g[N];
int root(int v) {
	if (p[v] == v)
		return v;
	return p[v] = root(p[v]);
}
bool anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1;i < K;i++) {
		up[v][i] = up[up[v][i - 1]][i - 1];
		mx[v][i] = max(mx[v][i - 1], mx[up[v][i - 1]][i - 1]);
	}
	for (auto u : t[v]) {
		if (u.f == p)
			continue;
		dep[u.f] = dep[v] + 1;
		mx[u.f][0] = u.s;
		dfs(u.f, v);
	}
	tout[v] = timer;
}
int Mx(int a, int b) {
	assert(anc(b, a));
	int d = dep[a] - dep[b];
	int r = 0;
	for (int i = K - 1;i >= 0;i--) {
		if (d >> i & 1) {
			r = max(r, mx[a][i]);
			a = up[a][i];
		}
	}
	return 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);
  vector<tuple<int, int, int>> edges;
  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 <= n;i++) {
  	p[i] = i;
  	sz[i] = 1;
  }
  for (int i = 0;i < q;i++) 
  	qs[l[i]].push_back({r[i], i});
  for (int i = 0;i < m;i++) {
  	int a = u[i], b = v[i];
  	int c = min(a, b);
  	edges.push_back({c, a, b});
  }
  sort(edges.begin(), edges.end());
  int ptr = m - 1;
  for (auto u : edges) {
  	int a, b, c;
  	tie(c, a, b) = u;
  	int x = root(a);
  	int y = root(b);
  	if (x != y) {
  		t[a].push_back({b, c});
  		t[b].push_back({a, c});
  		if (sz[x] < sz[y])
  			swap(x, y);
  		p[y] = x;
  		sz[x] += sz[y];
  	}
  }
  dfs(1, 0);
  for (int i = 1;i <= n;i++) {
  	p[i] = i;
  	sz[i] = 1;
  }
  for (int i = n;i >= 1;i--) {
  	while (ptr >= 0 && get<0>(edges[ptr]) >= i) {
  		int a = get<1>(edges[ptr]), b = get<2>(edges[ptr]);
  		ptr--;
  		int x = root(a), y = root(b);
  		if (x != y) {
  			if (sz[x] < sz[y])
  				swap(x, y);
  			sz[x] += sz[y];
  			p[y] = x;
  		}
  	}
  	for (auto j : qs[i]) {
  		int r = j.f, ind = j.s;
  		int ok = 0;
  		for (int k = 1;k <= n;k++) {
  			if (root(k) == root(s[ind]) && k >= i && k <= r) {
  				int lc = lca(k, e[ind]);
  				int x = max(Mx(k, lc), Mx(e[ind], lc));
  				ok |= (x <= r);
  			}
  		}
  		ans[ind] = ok;
  	}
  }
  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