Submission #447668

#	Time	Username	Problem	Language	Result	Execution time	Memory
447668		blue	Keys (IOI21_keys)	C++17	0 / 100	90 ms	121724 KiB

keys

#include "keys.h"
#include <set>
using namespace std;

const int maxN = 300'000;

int N;
int M;






struct edge
{
	int v;
	int c;
};

bool operator < (edge A, edge B)
{
	return A.c < B.c;
}

set<int> good_edge[maxN]; //over SCCs, does not use labels
multiset<edge> bad_edge[maxN];
set<int> keys[maxN];


vector<int> scc_label(maxN);
vector<int> scc_list[maxN];


vector<int> wcc_label(maxN);
vector<int> wcc_list[maxN];

vector<int> func_parent(maxN); //itself if this is a root.   //access only by label.


void scc_join(int u, int v)
{
	u = scc_label[u];
	v = scc_label[v];

	if(scc_list[u].size() < scc_list[v].size()) swap(u, v);


	int new_func_parent;
	if(scc_label[ func_parent[u] ] == v)
		new_func_parent = v;
	else
		new_func_parent = u;

	//also handle good edges, bad edges, keys



	for(int k: keys[v])
	{
		while(1)
		{
			multiset<edge>::iterator it = bad_edge[u].find(edge{-1, k});
			if(it == bad_edge[u].end()) break;
			good_edge[u].insert(it->v);
			bad_edge[u].erase(it);
		}

		keys[u].insert(k);
	}
	keys[v].clear();



	for(int g: good_edge[v])
	{
		good_edge[u].insert(g);
	}
	good_edge[v].clear();



	for(edge b: bad_edge[v])
	{
		if(keys[u].find(b.c) == keys[u].end())
			bad_edge[u].insert(b);
		else
			good_edge[u].insert(b.v);
	}
	bad_edge[v].clear();



	for(int x: scc_list[v])
	{
		scc_label[x] = u;
		scc_list[u].push_back(x);
	}
	scc_list[v].clear();



	func_parent[u] = new_func_parent;
}

void wcc_join(int u, int v)
{
	u = wcc_label[u];
	v = wcc_label[v];

	if(wcc_list[u].size() < wcc_list[v].size()) swap(u, v);

	for(int x: wcc_list[v])
	{
		wcc_label[x] = u;
		wcc_list[u].push_back(x);
	}
	wcc_list[v].clear();
}



bool in_wcc(int v, int u) //return whether v is in the WCC rooted at u (u and v are both scc labels)
{
	return (wcc_label[v] == wcc_label[u]) && (func_parent[u] == u);
}

void compress(int v) //compress the chain from v to the root (v is a scc label)
{
	v = scc_label[v];
	if(scc_label[ func_parent[v] ] == v) return;
	while(1)
	{
		if(scc_label[ func_parent[v] ] == v) return;
		else
		{
			scc_join(v, scc_label[ func_parent[v] ]);
			v = scc_label[v];
		}
	}
}

void addChild(int u, int v) //add v as a functional graph child of u
{
	u = scc_label[u];
	v = scc_label[v];

	func_parent[v] = u;

	wcc_join(u, v);
}


vector<int> find_reachable(vector<int> r1, vector<int> u1, vector<int> v1, vector<int> c1)
{
//PART 0: INPUT
	N = r1.size();
	M = u1.size();

	for(int i = 0; i < N; i++)
	{
		keys[i].insert(r1[i]);

		scc_label[i] = i;
		scc_list[i].push_back(i);

		wcc_label[i] = i;
		wcc_list[i].push_back(i);

		func_parent[i] = i;
	}


	for(int j = 0; j < M; j++)
	{
		if(keys[ u1[j] ].find( c1[j] ) == keys[ u1[j] ].end())
		{
			bad_edge[ u1[j] ].insert( edge{v1[j], c1[j]} );
		}
		else
		{
			good_edge[ u1[j] ].insert( v1[j] );
		}

		if(keys[ v1[j] ].find( c1[j] ) == keys[ v1[j] ].end())
		{
			bad_edge[ v1[j] ].insert( edge{u1[j], c1[j]} );
		}
		else
		{
			good_edge[ v1[j] ].insert( u1[j] );
		}
	}



	for(int u = 0; u < N; u++)
	{
		if(scc_label[u] != u) continue; //u is a scc label
		if(scc_label[ func_parent[u] ] != u) continue; //u is a functional graph root.

		while(!good_edge[u].empty())
		{
			int v = *good_edge[u].begin();
			good_edge[u].erase(v);

			v = scc_label[v];

			if(v == u) continue;

			if(in_wcc(v, u))
				compress(v);
			else
			{
				addChild(v, u);
				break;
			}

			u = scc_label[u]; //IMPORTANT!
		}
	}


	vector<int> res_list;
	int min_reach = N;
	for(int i = 0; i < N; i++)
	{
		if(scc_label[ func_parent[ scc_label[i] ] ] != scc_label[i]) continue;

		if(scc_list[ scc_label[i] ].size() < min_reach)
		{
			min_reach = scc_list[ scc_label[i] ].size();
			res_list.clear();
			res_list.push_back(i);
		}
		else if(scc_list[ scc_label[i] ].size() == min_reach)
		{
			res_list.push_back(i);
		}
	}

	vector<int> res(N, 0);
	for(int R: res_list)
		res[R] = 1;

	return res;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:230:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  230 |   if(scc_list[ scc_label[i] ].size() < min_reach)
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
keys.cpp:236:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  236 |   else if(scc_list[ scc_label[i] ].size() == min_reach)
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33