Submission #447695

#	Time	Username	Problem	Language	Result	Execution time	Memory
447695		blue	Keys (IOI21_keys)	C++17	100 / 100	1670 ms	144312 KiB

keys

#include "keys.h"
#include <set>
#include <iostream>
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(u == v) return;

	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 = scc_label[ func_parent[v] ];
	else
		new_func_parent = scc_label[ 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;

	// cerr << "after joining " << v << " and  " << u << '\n';
	// for(int i = 0; i < N; i++)
	// 	cerr << i << ' ' << scc_label[i] << ' ' << wcc_label[i] << ' ' << func_parent[ scc_label[i] ] << '\n';
	// cerr << "\n\n\n";
}

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

	if(u == v) return;

	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)
{
	// cerr << "in wcc " << v << ' ' << u << ' ' << ((wcc_label[v] == wcc_label[u]) && (scc_label[func_parent[scc_label[u]]] == scc_label[u])) << '\n';
	// cerr << wcc_label[v] << ' ' << wcc_label[u] << '\n';
	return (wcc_label[v] == wcc_label[u]) && (scc_label[func_parent[u]] == u);
}

void compress(int v) //compress the chain from v to the root (v is a scc label)
{
	// cerr << "compress " << v << '\n';
	v = scc_label[v];
	// cerr << "compressing " << v << '\n';
	if(scc_label[ func_parent[v] ] == v) return;
	while(1)
	{
		// cerr << "? " << v << ' ' << scc_label[ func_parent[v] ] << '\n';
		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);

	// cerr << "after adding " << v << " as child of " << u << '\n';
	// for(int i = 0; i < N; i++)
	// 	cerr << i << ' ' << scc_label[i] << ' ' << wcc_label[i] << ' ' << func_parent[ scc_label[i] ] << '\n';
	// cerr << "\n\n\n";
}


vector<int> find_reachable(vector<int> r1, vector<int> u1, vector<int> v1, vector<int> c1)
{
	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] );
		}
	}



	// cerr << "\n\n\n";
	// cerr << "initial state: \n";
	// for(int i = 0; i < N; i++)
	// 	cerr << i << ' ' << scc_label[i] << ' ' << wcc_label[i] << ' ' << func_parent[ scc_label[i] ] << '\n';
	// cerr << "\n\n\n";



	for(int u_temp = 0; u_temp < N; u_temp++)
	{
		int u = u_temp;

		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.

		// cerr << "\n\n\n\n\n\n\n";
		// cerr << "new value of u = " << u << '\n';

		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);
				// cerr << "breaking\n";
				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:263:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  263 |   if(scc_list[ scc_label[i] ].size() < min_reach)
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
keys.cpp:269:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  269 |   else if(scc_list[ scc_label[i] ].size() == min_reach)
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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