Submission #776805

#	Time	Username	Problem	Language	Result	Execution time	Memory
776805		ymm	Collapse (JOI18_collapse)	C++17	100 / 100	1225 ms	23208 KiB

collapse

#include "collapse.h"

#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 100'010;

namespace dsu {
	int par[N];
	int sz[N];
	vector<pii> his;
	int cnt;
	bool rec;

	void init() {
		fill(par, par+N, -1);
		fill(sz, sz+N, 1);
		his.clear();
		cnt = 0;
		rec = 0;
	}

	int rt(int v) { return par[v] == -1? v: rt(par[v]); }

	void unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		if (v == u)
			return;
		if (sz[v] < sz[u])
			swap(v, u);
		par[u] = v;
		sz[v] += sz[u];
		++cnt;
		if (rec)
			his.emplace_back(v, u);
	}

	void rollback() {
		while (his.size()) {
			auto [v, u] = his.back();
			his.pop_back();
			--cnt;
			sz[v] -= sz[u];
			par[u] = -1;
		}
		rec = 0;
	}
}

vector<pair<int,pii>> A[N], T[N];

void make_graph(vector<int> t, vector<int> V, vector<int> U)
{
	set<pair<pii,int>> e;
	Loop (i,0,t.size()) {
		int v = V[i], u = U[i];
		if (v > u)
			swap(v, u);
		if (t[i]) {
			auto it = e.lower_bound({{v, u}, -1});
			int l = it->second, r = i;
			A[v].push_back({u, {l,r}});
			T[u].push_back({v, {l,r}});
			e.erase(it);
		} else {
			e.insert({{v, u}, i});
		}
	}
	for (auto [dard, l] : e) {
		auto [v, u] = dard;
		int r = t.size();
		A[v].push_back({u, {l,r}});
		T[u].push_back({v, {l,r}});
	}
}

const int S = 1000;
int ans[N];

std::vector<int> simulateCollapse(
	int n,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
	make_graph(T, X, Y);
	vector<int> Q(W.size());
	iota(Q.begin(), Q.end(), 0);
	sort(Q.begin(), Q.end(), [&](int i, int j) { return W[i] < W[j]; });
	for (int l = 0, r = 0; l < W.size(); l = r) {
		while (r < W.size() && W[Q[r]] - W[Q[l]] <= S)
			++r;
		vector<int> Q2;
		Loop (i,l,r)
			Q2.push_back(Q[i]);
		sort(Q2.begin(), Q2.end(), [&](int i, int j) { return P[i] < P[j]; });
		Loop (phase,0,2) {
			dsu::init();
			vector<pair<pii,pii>> E;
			int p = phase == 0? 0: n-1;
			for (int q : Q2) {
				while (phase == 0? p <= P[q]: p > P[q]) {
					for (auto [u, t] : (phase == 0? ::T[p]: ::A[p])) {
						if (t.first <= W[Q[l]] && W[Q[r-1]] < t.second) {
							dsu::unite(p, u);
							continue;
						}
						if (W[Q[r-1]] < t.first || t.second <= W[Q[l]])
							continue;
						E.push_back({{p,u},t});
					}
					p += phase == 0? 1: -1;
				}
				dsu::rec = 1;
				for (auto [e, t] : E) {
					if (t.first <= W[q] && W[q] < t.second)
						dsu::unite(e.first, e.second);
				}
				ans[q] += dsu::cnt;
				dsu::rollback();
			}
			reverse(Q2.begin(), Q2.end());
		}
	}
	Loop (i,0,Q.size())
		ans[i] = n - ans[i];
	return vector<int>(ans, ans+Q.size());
}

Compilation message (stderr)

collapse.cpp: In function 'void make_graph(std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:4:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
      |                                          ^
collapse.cpp:59:2: note: in expansion of macro 'Loop'
   59 |  Loop (i,0,t.size()) {
      |  ^~~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for (int l = 0, r = 0; l < W.size(); l = r) {
      |                         ~~^~~~~~~~~~
collapse.cpp:97:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   while (r < W.size() && W[Q[r]] - W[Q[l]] <= S)
      |          ~~^~~~~~~~~~
collapse.cpp:4:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
      |                                          ^
collapse.cpp:131:2: note: in expansion of macro 'Loop'
  131 |  Loop (i,0,Q.size())
      |  ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35