Submission #1229149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229149		Captain_Georgia	Werewolf (IOI18_werewolf)	C++20	100 / 100	665 ms	95788 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct DSU {
	vector<int> par, sz, tin, tout;
	vector<vector<int>> g;
	int typ;
    void init (int x, int y) {
        typ = y;
        par.assign(x + 2, -1);
        sz.assign(x + 2, 1);
        g.assign(x + 2, {});
        tin.assign(x + 2, 0);
        tout.assign(x + 2, 0);
    }
	int get_par (int x) {
        if (par[x] == -1) return x;
        return par[x] = get_par(par[x]);
	}
	bool add (int a, int b) {
		a = get_par(a);
        b = get_par(b);
		if (a == b) return false;
		
		if ((typ == 0 && a >= b) || (typ == 1 && a <= b)) swap(a, b);
		par[b] = a; 
		g[a].push_back(b);
		return true;
	}
};

vector<int> check_validity (int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int M = X.size(), Q = S.size();

	vector<int> g[N];
	for (int i = 0;i < M;i ++) {
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}
	DSU DS[2];
    DS[0].init(N, 0);
    DS[1].init(N, 1);
	
	vector<array<int, 2>> ind(Q, {0, 0});
	{
		vector<int> _g1[N], _g2[N];
		for (int i = 0;i < Q;i ++) {
			_g1[L[i]].push_back(i);
            _g2[R[i]].push_back(i);
		}
		for (int i = N - 1;i >= 0;i --) {
			for (auto j : g[i]) {
				if (j > i) {
					DS[0].add(i, j);
				}
			}
			for (auto j : _g1[i]) {
				ind[j][0] = DS[0].get_par(S[j]);
			}
		}
		for (int i = 0;i < N;i ++) {
			for (auto j : g[i]) {
				if (j < i) {
					DS[1].add(i, j);
				}
			}
			for (auto j : _g2[i]) {
			    ind[j][1] = DS[1].get_par(E[j]);
			}
		}
	}
	
    int _time;
    function<void(int, int)> dfs_init = [&](int si, int typ) -> void {
        DS[typ].tin[si] = ++ _time;
        for (auto ti : DS[typ].g[si]) {
            dfs_init(ti, typ);
        }
        DS[typ].tout[si] = _time;
    };
    for (int i = 0;i < 2;i ++) {
        _time = -1;
        dfs_init(DS[i].get_par(0), i);
    }
	
	vector<int> _g[N];
	for (int i = 0;i < Q;i ++) {
		_g[ind[i][0]].push_back(i);
	}
	
	set<int> sl[N];
	vector<int> res(Q);
	function<void(int)> dfs = [&](int si) -> void {
		sl[si].insert(DS[1].tin[si]);
		for (auto ti : DS[0].g[si]) {
			dfs(ti);
			
			if (sl[si].size() < sl[ti].size()) {
				swap(sl[si], sl[ti]);
			}
			for (auto x : sl[ti]) {
				sl[si].insert(x);
			}
            sl[ti].clear();
		}
		
		for (auto ti : _g[si]) { 
			int l = DS[1].tin[ind[ti][1]], r = DS[1].tout[ind[ti][1]];
			res[ti] = (sl[si].lower_bound(l) != sl[si].upper_bound(r));
		}
	};
	dfs(0);
	
	return res;
}

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