Submission #67427

#	Time	Username	Problem	Language	Result	Execution time	Memory
67427		aome	Collapse (JOI18_collapse)	C++17	100 / 100	5469 ms	79620 KiB

collapse

#include "collapse.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

struct Event {
	int T, type, x, y;

	bool operator < (const Event& rhs) const {
		return (T == rhs.T) ? type < rhs.type : T < rhs.T;
	}
};

struct Edge {
	int id, u, v;

	bool operator < (const Edge& rhs) const {
		return u < rhs.u;
	}
};

int n;
int par[N];
int res[N];
int f[2][N];
int pos[N];
bool state[N];
bool iedge[N];
bool inode[N];
vector<Event> vec, buf;
vector< pair<int, int> > dsu[2][500];
map< pair<int, int>, int > label;
vector<Edge> E1, E2;

int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }

bool join(int u, int v) {
	u = find(u), v = find(v);
	if (inode[u]) swap(u, v); // root prefer important node
	par[u] = v; return u != v; 
}

void solve() {
	vector<int> vnode;
	vector<Edge> vedge;

	int cnt = 0;
	for (auto i : buf) {
		if (i.type < 0) {
			int id = label[{i.x, i.y}];
			if (!iedge[id]) {
				iedge[id] = 1;
				vedge.push_back({id, i.x, i.y});
			}
			if (!inode[i.x]) {
				inode[i.x] = 1, vnode.push_back(i.x);
			}
			if (!inode[i.y]) {
				inode[i.y] = 1, vnode.push_back(i.y);
			}
		}
		else pos[i.type] = cnt++;
	}

	{	
		vector< pair<int, int> > vec1;
		for (auto i : buf) {
			if (i.type >= 0) vec1.push_back({i.x, i.type});
		}
		sort(vec1.begin(), vec1.end());
		for (int i = 0; i < n; ++i) par[i] = i;
		int ptr = 0, cur = 0, cnt = 0;
		for (auto i : vec1) {
			while (cur < i.first) ++cur, ++cnt;
			while (ptr < E1.size() && E1[ptr].u <= i.first) {
				if (!iedge[E1[ptr].id] && state[E1[ptr].id]) {
					cnt -= join(E1[ptr].u, E1[ptr].v);
				}
				++ptr;
			}
			f[0][i.second] = cnt;
			for (auto j : vnode) {
				dsu[0][pos[i.second]].push_back({j, find(j)});
			}
		}
	}

	{	
		vector< pair<int, int> > vec2;
		for (auto i : buf) {
			if (i.type >= 0) vec2.push_back({i.x + 1, i.type});
		}
		sort(vec2.begin(), vec2.end());
		reverse(vec2.begin(), vec2.end());
		for (int i = 0; i < n; ++i) par[i] = i;
		int ptr = 0, cur = 0, cnt = 0;
		for (auto i : vec2) {
			while (cur < n - i.first + 1) ++cur, ++cnt;
			while (ptr < E2.size() && E2[ptr].u >= i.first) {
				if (!iedge[E2[ptr].id] && state[E2[ptr].id]) {
					cnt -= join(E2[ptr].u, E2[ptr].v);
				}
				++ptr;
			}
			f[1][i.second] = cnt;
			for (auto j : vnode) {
				dsu[1][pos[i.second]].push_back({j, find(j)});
			}
		}
	}

	for (auto i : buf) {
		if (i.type < 0) {
			int id = label[{i.x, i.y}];
			state[id] ^= 1; continue;
		}
		int id = i.type;
		for (int j = 0; j < 2; ++j) {
			for (auto k : dsu[j][pos[id]]) par[k.first] = k.second;
			for (auto k : vnode) {
				if (j == 0 && k > i.x || j == 1 && k <= i.x) continue; 
				f[j][id] -= par[k] == k;
			}
			for (auto k : vedge) {
				// k.u < k.v
				if (state[k.id] && (k.v <= i.x || k.u > i.x)) join(k.u, k.v);
			}
			for (auto k : vnode) {
				if (j == 0 && k > i.x || j == 1 && k <= i.x) continue;
				f[j][id] += par[k] == k;
			}
		}
		res[id] = f[0][id] + f[1][id];
	}

	for (int i = 0; i < cnt; ++i) dsu[0][i].clear(), dsu[1][i].clear();
	for (auto i : buf) {
		if (i.type < 0) {
			iedge[label[{i.x, i.y}]] = inode[i.x] = inode[i.y] = 0;
		}
	}
	buf.clear();
}

vector<int> simulateCollapse(
	int _n,
	vector<int> T,
	vector<int> X,
	vector<int> Y,
	vector<int> W,
	vector<int> P
) {
	n = _n;
	int c = T.size();
	int q = W.size();

	for (int i = 0; i < c; ++i) {
		if (X[i] > Y[i]) swap(X[i], Y[i]);
		vec.push_back({i, -(T[i] + 1), X[i], Y[i]});
	}
	for (int i = 0; i < q; ++i) {
		vec.push_back({W[i], i, P[i], 0});
	}
	sort(vec.begin(), vec.end());

	int cnt = 0;
	for (int i = 0; i < c; ++i) {
		if (label[{X[i], Y[i]}]) continue;
		label[{X[i], Y[i]}] = ++cnt; 
		E1.push_back({cnt, Y[i], X[i]});
		E2.push_back({cnt, X[i], Y[i]});
	}

	sort(E1.begin(), E1.end());
	sort(E2.begin(), E2.end());
	reverse(E2.begin(), E2.end());

	for (int i = 0; i < vec.size(); ++i) {
		buf.push_back(vec[i]);
		if (buf.size() == 365) solve();
	}
	if (buf.size()) solve();

	vector<int> vres;
	for (int i = 0; i < q; ++i) vres.push_back(res[i]);
	return vres;
}

Compilation message (stderr)

collapse.cpp: In function 'void solve()':
collapse.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (ptr < E1.size() && E1[ptr].u <= i.first) {
           ~~~~^~~~~~~~~~~
collapse.cpp:102:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (ptr < E2.size() && E2[ptr].u >= i.first) {
           ~~~~^~~~~~~~~~~
collapse.cpp:124:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (j == 0 && k > i.x || j == 1 && k <= i.x) continue; 
         ~~~~~~~^~~~~~~~~~
collapse.cpp:132:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (j == 0 && k > i.x || j == 1 && k <= i.x) continue;
         ~~~~~~~^~~~~~~~~~
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:181:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); ++i) {
                  ~~^~~~~~~~~~~~

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