Submission #1035286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035286		lovrot	Werewolf (IOI18_werewolf)	C++17	100 / 100	575 ms	129188 KiB

werewolf

#include "werewolf.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;

const int LOG = 19;
const int N = 1 << LOG;

struct quest {
	int l, r, a, b;
	quest() {}
	quest(int l, int r, int a, int b) : l(l), r(r), a(a), b(b) {}
};

quest q[N];
vector<int> g[N], h[N];

int un[N], iv[N], ma[N];

int trazi(int u) { 
	if(un[u] == -1) { 
		return u;
	}
	return un[u] = trazi(un[u]);
}

void unija(int u, int v) { 
	u = trazi(u);
	if(u == v) { return; }
	un[u] = v;
	h[v].PB(u);
}

int up[N][LOG], val[N];

void dfs(int u, vector<int> &p) { 
	iv[u] = p.size();
	for(int v : h[u]) { 
		up[v][0] = u;
//		printf("%d %d\n", u, v);
		dfs(v, p);
	}
	if(h[u].empty()) { 
		p.PB(u);
	}
	ma[u] = p.size();
}

int climb(int u, int x, bool f) { 
	for(int i = LOG - 1; i >= 0; --i) { 
		if((val[up[u][i]] >= x) == f) { 
			u = up[u][i];
		}
	}
	return u;
}

int t[2 * N]; // memset -1

void update(int u, int x) { 
	u += N;
	t[u] = x;
	for(u >>= 1; u; u >>= 1) { 
		t[u] = max(t[2 * u], t[2 * u + 1]);
	}
}

int query(int l, int r, int u = 1, int lo = 0, int hi = N) { 
	if(r <= lo || hi <= l) { return -1; }
	if(l <= lo && hi <= r) { return t[u]; }
	int mi = (lo + hi) / 2;
	return max(query(l, r, 2 * u, lo, mi), query(l, r, 2 * u + 1, mi, hi));
}

vector<int> qi[N];

vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
	int m = S.size();
	vector<int> ans(m);	
	
	for(int i = 0; i < X.size(); ++i) { 
		g[X[i]].PB(Y[i]);
		g[Y[i]].PB(X[i]);
	}
	
	// n - 1, n - 2, ... 0
	memset(un, -1, sizeof(un));
	for(int i = n - 2, j = n; i >= 0; --i, ++j) { 
		unija(i, j);
		val[j] = i;
		up[j][0] = j;
		for(int v : g[i]) { 
			if(v > i) {
				unija(v, j);
			}
		}
	}

	vector<int> a;
	dfs(2 * n - 2, a);
	for(int i = 1; i < LOG; ++i) { for(int j = 0; j < 2 * n - 1; ++j) { up[j][i] = up[up[j][i - 1]][i - 1]; } }
	for(int i = 0; i < m; ++i) { 
		int res = climb(S[i], L[i], 1);
		q[i].l = iv[res];
		q[i].r = ma[res];
		qi[q[i].r - 1].PB(i);
//		printf("%d %d lr %d %d\n", i, res, q[i].l, q[i].r);
	}

	// 0, 1, ... n - 1
	memset(un, -1, sizeof(un));
	for(int i = 1, j = n; i < n; ++i, ++j) {
		h[j].clear();
		unija(i, j);
		val[j] = i;
		up[j][0] = j;
		for(int v : g[i]) { 
			if(v < i) {
				unija(v, j);
			}
		}
	}

	vector<int> b;
	dfs(2 * n - 2, b);
	for(int i = 1; i < LOG; ++i) { for(int j = 0; j < 2 * n - 1; ++j) { 
		up[j][i] = up[up[j][i - 1]][i - 1]; } }
	for(int i = 0; i < m; ++i) { 
		int res = climb(E[i], R[i] + 1, 0);
		q[i].a = iv[res];
		q[i].b = ma[res];
//		printf("%d %d ab %d %d\n", i, res, q[i].a, q[i].b);
	}

//	for(int i = 0; i < n; ++i) { printf("(%d, %d)%c", i, a[i], " \n"[i == n - 1]); }
//	for(int i = 0; i < n; ++i) { printf("(%d, %d)%c", i, b[i], " \n"[i == n - 1]); }

	for(int i = 0; i < n; ++i) { 
		val[b[i]] = i;
	}

	memset(t, -1, sizeof(t));
	for(int i = 0; i < n; ++i) { 
		update(val[a[i]], i);
		for(int j : qi[i]) { 
//			printf("%d %d : %d %d %d %d\n", i, j, q[j].a, q[j].b, q[j].l, query(q[j].a, q[j].b + 1));
			if(query(q[j].a, q[j].b) >= q[j].l) { 
				ans[j] = 1;
			}
		}
	}
	
	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i = 0; i < X.size(); ++i) {
      |                 ~~^~~~~~~~~~

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