Submission #1159913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159913		Der_Vlapos	Collapse (JOI18_collapse)	C++20	0 / 100	80 ms	2512 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end() s

struct DSU
{
	vector<int> p;
	int cnt = 0;

	void init(int n)
	{
		cnt = n;
		p.resize(n);
		for (int i = 0; i < n; ++i)
		{
			p[i] = i;
		}
	}

	int getR(int v)
	{
		return p[v] == v ? v : p[v] = getR(p[v]);
	}

	void merge(int a, int b)
	{
		a = getR(a);
		b = getR(b);
		if (a == b)
			return;
		cnt--;
		p[a] = b;
	}
};

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)
{
	int q = w.size();
	vector<int> ans(q);

	for (int i = 0; i < n; ++i)
		if (x[i] > y[i])
			swap(x[i], y[i]);

	for (int cq = 0; cq < q; ++cq)
	{
		set<pii> edges;
		for (int i = 0; i < w[cq]; ++i)
			if (y[i] <= p[cq] or p[cq] + 1 <= x[i])
				if (t[i])
					edges.erase({x[i], y[i]});
				else
					edges.insert({x[i], y[i]});
		DSU dsu;
		dsu.init(n);
		for (auto [x, y] : edges)
		{
			dsu.merge(x, y);
		}
		ans[cq] = dsu.cnt;
	}

	return ans;
}

// #include "collapse.h"
// #include <cstdio>
// #include <cstdlib>

// int main(int argc, char *argv[])
// {
// 	int N, C, Q;
// 	scanf("%d%d%d", &N, &C, &Q);
// 	std::vector<int> T(C), X(C), Y(C);
// 	for (int i = 0; i < C; i++)
// 	{
// 		scanf("%d%d%d", &T[i], &X[i], &Y[i]);
// 	}
// 	std::vector<int> W(Q), P(Q);
// 	for (int i = 0; i < Q; i++)
// 	{
// 		scanf("%d%d", &W[i], &P[i]);
// 	}
// 	auto res = simulateCollapse(N, T, X, Y, W, P);
// 	for (auto i : res)
// 	{
// 		printf("%d\n", i);
// 	}
// }

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