Submission #168143

#	Time	Username	Problem	Language	Result	Execution time	Memory
168143		Shafin666	Werewolf (IOI18_werewolf)	C++14	100 / 100	1069 ms	176204 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define VI vector<int>
#define nyan "(=^･ω･^=)"
#define read_input         freopen("in.txt","r", stdin)
#define print_output       freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 4e5+10;
int N, M, Q; int tym;
VI adj[2][maxn], sml[maxn], big[maxn];
int parent[2][20][maxn], tour[2][maxn];
int st[2][maxn], ed[2][maxn];

struct disjointSetUnion {
	int par[maxn];
	void init() { for(int i = 0; i <= N; i++) par[i] = i; }
	int find(int x) { return (par[x] == x)? x : par[x] = find(par[x]); }
	void join(int a, int b) { par[find(b)] = find(a); }
} dsu;

struct HolyShit {
	int ans[maxn];

	struct binarytree {
		int a[maxn];

		int add(int x, int val) {
			while(x < maxn) {
				a[x] += val;
				x += x & -x;
			}
		} 
		int sum(int x) {
			int ret = 0;
			while(x) {
				ret += a[x];
				x -= x & -x;
			} return ret;
		}
		int range(int l, int r) { return sum(r) - sum(l-1); }
	} bit;

	struct event {
		int x, y1, y2, typ, idx;
		event(int _x=0, int _y1 = 0, int _y2=0, int _t=-1, int _i=-1) :
			x(_x), y1(_y1), y2(_y2), typ(_t), idx(_i) {}

		bool operator<(const event &rhs) {
			if(x == rhs.x) return typ < rhs.typ;
			return x < rhs.x;
		}
	}; vector<event> events;

	void insert(int x, int y) { x++; y++; events.pb(event(x, y, -1, 1, -1)); }
	void query(int x1, int y1, int x2, int y2, int id) {
		x1++; y1++; x2++; y2++;
		events.pb(event(x1, y1, y2, 0, id));
		events.pb(event(x2, y1, y2, 2, id));
	}

	void process() {
		sort(events.begin(), events.end());

		//for(auto e : events) {
		//	cout << e.x << " [" << e.y1 << ", " << e.y2 << "] (" << e.typ << ") " << e.idx <<endl;  
		//}

		for(auto e : events) {
			if(e.typ == 0) ans[e.idx] -= bit.range(e.y1, e.y2);
			else if(e.typ == 1) bit.add(e.y1, 1);
			else ans[e.idx] += bit.range(e.y1, e.y2);
		}
	}
} ds;

void dfs(int u, int id) {
	tour[id][tym] = u;
	st[id][u] = tym++;

	for(auto v : adj[id][u])
		dfs(v, id);
	ed[id][u] = tym-1;
}


VI check_validity(int n, VI X, VI Y, VI S, VI E, VI L, VI R) { // 0 = small, 1 = big;
	N = n;
	M = X.size();
	Q = S.size(); VI A(Q, 0);

	for(int i = 0; i < M; i++) {
		if(X[i] > Y[i]) swap(X[i], Y[i]);
		
		sml[X[i]].pb(Y[i]);
		big[Y[i]].pb(X[i]);
	}

	dsu.init(); memset(parent, -1, sizeof parent);
	for(int u = 0; u < n; u++) {
		for(auto it : big[u]) {
			int v = dsu.find(it);
			if(v == u) continue;

			adj[1][u].pb(v);
			parent[1][0][v] = u;

			dsu.join(u, v);
		}
	}
	dsu.init();
	for(int u = n-1; u >= 0; u--) {
		for(auto it : sml[u]) {
			int v = dsu.find(it);
			if(v == u) continue;

			adj[0][u].pb(v);
			parent[0][0][v] = u;

			dsu.join(u, v);
		}
	}

	tym = 0; dfs(0, 0);
	tym = 0; dfs(n-1, 1);

	for(int i = 1; 1 << i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(parent[0][i-1][j] != -1) parent[0][i][j] = parent[0][i-1][parent[0][i-1][j]];
			if(parent[1][i-1][j] != -1) parent[1][i][j] = parent[1][i-1][parent[1][i-1][j]];
		}
	}

	int aux[maxn];
	for(int i = 0; i < n; i++) aux[tour[1][i]] = i;
	for(int i = 0; i < n; i++) ds.insert(i, aux[tour[0][i]]);  

	for(int i = 0; i < Q; i++) {
		int u = S[i], v = E[i];

		for(int j = 18; j >= 0; j--) 
			if(parent[0][j][u] != -1 && parent[0][j][u] >= L[i]) u = parent[0][j][u];
		for(int j = 18; j >= 0; j--) 
			if(parent[1][j][v] != -1 && parent[1][j][v] <= R[i]) v = parent[1][j][v];

		ds.query(st[0][u], st[1][v], ed[0][u], ed[1][v], i);

		//cout << st[0][u] << " " << ed[0][u] << "\t\t" << st[1][v] << " " << ed[1][v] << endl;

	} ds.process();

	for(int i = 0; i < Q; i++) A[i] = ds.ans[i] > 0;

  	return A;
}

Compilation message (stderr)

werewolf.cpp: In member function 'int HolyShit::binarytree::add(int, int)':
werewolf.cpp:37:3: warning: no return statement in function returning non-void [-Wreturn-type]
   } 
   ^

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