Submission #299615

#	Time	Username	Problem	Language	Result	Execution time	Memory
299615		square1001	Werewolf (IOI18_werewolf)	C++14	100 / 100	2764 ms	159596 KiB

werewolf

#include "werewolf.h"
#include <queue>
#include <string>
#include <vector>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
class history {
public:
	int tl, tr, x;
	history() : tl(0), tr(0), x(-1) {};
	history(int tl_, int tr_, int x_) : tl(tl_), tr(tr_), x(x_) {};
};
class rectangle {
public:
	int xl, yl, xr, yr;
	rectangle() : xl(0), yl(0), xr(0), yr(0) {};
	rectangle(int xl_, int yl_, int xr_, int yr_) : xl(xl_), yl(yl_), xr(xr_), yr(yr_) {};
};
class query {
public:
	int y, x, tp;
	query() : y(0), x(0), tp(-1) {};
	query(int y_, int x_, int tp_) : y(y_), x(x_), tp(tp_) {};
};
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
	// step #1. setup
	int M = X.size(), Q = S.size();
	vector<vector<int> > GU(N), GD(N);
	for(int i = 0; i < M; ++i) {
		if(X[i] > Y[i]) {
			swap(X[i], Y[i]);
		}
		GU[X[i]].push_back(Y[i]);
		GD[Y[i]].push_back(X[i]);
	}
	// step #2. minimum-condition merge-tech
	vector<int> scomp(N, -1), slast(N, N - 1);
	vector<vector<int> > sgroup(N);
	vector<vector<history> > shistory(N);
	for(int i = 0; i < N; ++i) {
		scomp[i] = i;
		sgroup[i] = { i };
	}
	for(int i = N - 1; i >= 0; --i) {
		vector<int> g = { i };
		for(int j : GU[i]) {
			g.push_back(scomp[j]);
		}
		sort(g.begin(), g.end(), [&](int j, int k) { return sgroup[j].size() > sgroup[k].size(); });
		g.erase(unique(g.begin(), g.end()), g.end());
		for(int j : g) {
			if(j == g[0]) continue;
			for(int k : sgroup[j]) {
				shistory[k].push_back(history(i + 1, slast[k] + 1, j));
				scomp[k] = g[0];
				slast[k] = i;
			}
			sgroup[g[0]].insert(sgroup[g[0]].end(), sgroup[j].begin(), sgroup[j].end());
			sgroup[j].clear();
		}
	}
	for(int i = 0; i < N; ++i) {
		shistory[i].push_back(history(0, slast[i] + 1, scomp[i]));
		reverse(shistory[i].begin(), shistory[i].end());
	}
	// step #3. maximum-condition merge-tech
	vector<int> ecomp(N, -1), elast(N, 0);
	vector<vector<int> > egroup(N);
	vector<vector<history> > ehistory(N);
	for(int i = 0; i < N; ++i) {
		ecomp[i] = i;
		egroup[i] = { i };
	}
	for(int i = 0; i < N; ++i) {
		vector<int> g = { i };
		for(int j : GD[i]) {
			g.push_back(ecomp[j]);
		}
		sort(g.begin(), g.end(), [&](int j, int k) { return egroup[j].size() > egroup[k].size(); });
		g.erase(unique(g.begin(), g.end()), g.end());
		for(int j : g) {
			if(j == g[0]) continue;
			for(int k : egroup[j]) {
				ehistory[k].push_back(history(elast[k], i, j));
				ecomp[k] = g[0];
				elast[k] = i;
			}
			egroup[g[0]].insert(egroup[g[0]].end(), egroup[j].begin(), egroup[j].end());
			egroup[j].clear();
		}
	}
	for(int i = 0; i < N; ++i) {
		ehistory[i].push_back(history(elast[i], N, ecomp[i]));
	}
	// step #4. find component ID of S[i] and E[i]
	vector<int> sid(Q), eid(Q);
	for(int i = 0; i < Q; ++i) {
		for(history j : shistory[S[i]]) {
			if(j.tl <= L[i] && L[i] < j.tr) {
				sid[i] = j.x;
			}
		}
		for(history j : ehistory[E[i]]) {
			if(j.tl <= R[i] && R[i] < j.tr) {
				eid[i] = j.x;
			}
		}
	}
	// step #5. coordinate compression of (sid, eid)-pair
	vector<pair<int, int> > sepair(Q);
	for(int i = 0; i < Q; ++i) {
		sepair[i] = make_pair(sid[i], eid[i]);
	}
	sort(sepair.begin(), sepair.end());
	sepair.erase(unique(sepair.begin(), sepair.end()), sepair.end());
	int V = sepair.size();
	// step #6. calculate index list of (S[i], E[i])-pair
	vector<vector<int> > VI(V);
	for(int i = 0; i < Q; ++i) {
		int ptr = lower_bound(sepair.begin(), sepair.end(), make_pair(sid[i], eid[i])) - sepair.begin();
		VI[ptr].push_back(i);
	}
	// step #7. enumerate "valid (L, R)-range" for each (sid, eid)-pair
	vector<vector<rectangle> > VR(V);
	for(int i = 0; i < N; ++i) {
		for(history j : shistory[i]) {
			for(history k : ehistory[i]) {
				int ptr = lower_bound(sepair.begin(), sepair.end(), make_pair(j.x, k.x)) - sepair.begin();
				if(ptr != sepair.size() && sepair[ptr] == make_pair(j.x, k.x)) {
					VR[ptr].push_back(rectangle(j.tl, k.tl, j.tr, k.tr));
				}
			}
		}
	}
	// step #8. answer for each query!
	vector<int> ans(Q);
	for(int i = 0; i < V; ++i) {
		vector<int> cx;
		for(int j : VI[i]) {
			cx.push_back(L[j]);
		}
		sort(cx.begin(), cx.end());
		cx.erase(unique(cx.begin(), cx.end()), cx.end());
		vector<query> qs;
		for(int j : VI[i]) {
			int ptr = lower_bound(cx.begin(), cx.end(), L[j]) - cx.begin();
			qs.push_back(query(R[j], ptr, j));
		}
		for(rectangle j : VR[i]) {
			int pl = lower_bound(cx.begin(), cx.end(), j.xl) - cx.begin();
			int pr = lower_bound(cx.begin(), cx.end(), j.xr) - cx.begin();
			qs.push_back(query(j.yl, pl, -1));
			qs.push_back(query(j.yl, pr, -2));
			qs.push_back(query(j.yr, pl, -2));
			qs.push_back(query(j.yr, pr, -1));
		}
		sort(qs.begin(), qs.end(), [](const query& q1, const query& q2) {
			return q1.y != q2.y ? q1.y < q2.y : q1.tp < q2.tp;
		});
		int CS = cx.size();
		vector<int> bit(CS + 1);
		for(query j : qs) {
			if(j.tp == -1) {
				for(int k = j.x + 1; k <= CS; k += k & (-k)) {
					++bit[k];
				}
			}
			else if(j.tp == -2) {
				for(int k = j.x + 1; k <= CS; k += k & (-k)) {
					--bit[k];
				}
			}
			else {
				int sum = 0;
				for(int k = j.x + 1; k >= 1; k -= k & (-k)) {
					sum += bit[k];
				}
				if(sum > 0) {
					ans[j.tp] = 1;
				}
			}
		}
	}
	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:131:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     if(ptr != sepair.size() && sepair[ptr] == make_pair(j.x, k.x)) {
      |        ~~~~^~~~~~~~~~~~~~~~

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