Submission #363314

#	Time	Username	Problem	Language	Result	Execution time	Memory
363314		r57shell	Collapse (JOI18_collapse)	C++14	5 / 100	15091 ms	6124 KiB

collapse

#include "collapse.h"
#include <vector>
#include <set>

using namespace std;

const int MAXN = 1e5;

static int PP[MAXN][4];

int getp(int x)
{
	if (PP[x][0] == x)
		return x;
	return (PP[x][0] = getp(PP[x][0]));
}

void join(int a, int b)
{
	a = getp(a);
	b = getp(b);
	if (a == b)
		return;
	if (PP[a][1] < PP[b][1])
		swap(a, b);
	PP[b][0] = a;
	PP[a][1] += PP[b][1];
}

vector<int> simulateCollapse(
	int N,
	vector<int> T,
	vector<int> X,
	vector<int> Y,
	vector<int> W,
	vector<int> P)
{
	for (int i = 0; i < X.size(); ++i)
		if (X[i] > Y[i])
			swap(X[i], Y[i]);
	vector<int> ans(W.size());
	vector<pair<int,int>> Q(W.size());
	for (int i = 0; i < W.size(); ++i)
		Q[i] = pair<int,int>(W[i], i);
	for (int z = 0; z < W.size(); ++z)
	{
		for (int j = 0; j < N; ++j)
		{
			PP[j][0] = j;
			PP[j][1] = 1;
			PP[j][2] = 0;
		}
		int i = Q[z].second;
		int cut = P[i];
		//printf("$%d %d$\n", i, cut);
		set<pair<int,int>> edges;
		for (int j = 0; j <= W[i]; ++j)
		{
			//printf("|%d %d %d|\n", T[j], X[j], Y[j]);
			if (T[j] == 0)
				edges.insert(pair<int,int>(X[j], Y[j]));
			else
				edges.erase(pair<int,int>(X[j], Y[j]));
		}
		set<pair<int,int>>::iterator f;
		for (f = edges.begin(); f != edges.end(); ++f)
		{
			//printf("((%d %d))\n", f->first, f->second);
			if (f->first > cut || f->second <= cut)
			{
				join(f->first, f->second);
				//printf("(%d %d)", f->first, f->second);
			}
		}
		int res = 0;
		for (int j = 0; j < N; ++j)
		{
			int a = getp(j);
			if (PP[a][2] == 0)
			{
				PP[a][2] = 1;
				//printf("!%d!",a);
				++res;
			}
		}
		//printf("=(%d)%d\n", i,res);
		ans[i] = res;
	}
	return ans;
}

Compilation message (stderr)

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:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < X.size(); ++i)
      |                  ~~^~~~~~~~~~
collapse.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0; i < W.size(); ++i)
      |                  ~~^~~~~~~~~~
collapse.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int z = 0; z < W.size(); ++z)
      |                  ~~^~~~~~~~~~

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