Submission #547782

#	Time	Username	Problem	Language	Result	Execution time	Memory
547782		blue	Collapse (JOI18_collapse)	C++17	5 / 100	15062 ms	4548 KiB

collapse

#include "collapse.h"
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <iostream>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const int bs = 250;





vi simulateCollapse(int N, vi T, vi X, vi Y, vi W, vi P)
{	
	int C = sz(T);

	int Q = sz(W);

	for(int i = 0; i < C; i++)
	{
		if(X[i] > Y[i])
			swap(X[i], Y[i]);
	}

	vi res(Q);

	for(int q = 0; q < Q; q++)
	{
		set<pii> edges;
		for(int i = 0; i <= W[q]; i++)
		{
			if(X[i] <= P[q] && P[q]+1 <= Y[i]) continue;

			if(T[i] == 0)
				edges.insert({X[i], Y[i]});
			else
				edges.erase({X[i], Y[i]});
		}

		vi edge[N];
		for(auto& z : edges)
		{
			edge[z.first].push_back(z.second);
			edge[z.second].push_back(z.first);
		}

		int comps = 0;

		vi vis(N, 0);

		queue<int> tbv;

		for(int i = 0; i < N; i++)
		{
			if(vis[i]) continue;

			comps++;
			vis[i] = 1;

			tbv.push(i);
			while(!tbv.empty())
			{
				int u = tbv.front();
				tbv.pop();

				for(int v : edge[u])
				{
					if(vis[v]) continue;
					tbv.push(v);
					vis[v] = 1;
				}
			}
		}

		res[q] = comps;

		// cout << comps << '\n';
	}

	return res;
}

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