Submission #1043550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043550		parsadox2	Keys (IOI21_keys)	C++17	100 / 100	471 ms	62724 KiB

keys

#include <vector>
#include "keys.h"
#include <bits/stdc++.h>

#define F first
#define S second
using namespace std;
 
const int N = 3e5 + 10;
int n , m , col[N] , root[N] , nex[N] , p[N] , mn;
bool solved[N] , marked[N] , key[N] , vis[N];
vector <int> all_roots;
vector <int> can , cand , ans;
vector <int> to[N];
vector <pair<int ,int>> adj[N];
 
void Add_vert(int v)
{
	for(auto u : adj[v])
	{
		if(key[u.F])
			can.push_back(u.S);
		else
			to[u.F].push_back(u.S);
	}
}
 
void Add_col(int v)
{
	for(auto u : to[v])
		can.push_back(u);
	to[v].clear();
}

int Root(int v)
{
	return ((root[v] == v || root[v] == -1) ? v : root[v] = Root(root[v]));
}

void Find_nex(int star)
{
	nex[star] = -1;
	vector <int> all;
	vector <int> tmp;
	all.push_back(star);	
	marked[star] = true;
	while(!all.empty())
	{
		int v = all.back();  all.pop_back();
		if(Root(v) != root[star])
		{
			nex[star] = root[v];
			if(root[v] == -1)
				nex[star] = -2;
			marked[v] = false;
			break;
		}
		tmp.push_back(v);
		key[col[v]] = true;
		Add_vert(v);
		Add_col(col[v]);
		while(!can.empty())
		{
			int u = can.back();  can.pop_back();
			if(marked[u])
				continue;
			marked[u] = true;
			all.push_back(u);
		}
	}
	can.clear();
	for(auto u : tmp)
	{
		key[col[u]] = false;
		marked[u] = false;
		for(auto v : adj[u])
			to[v.F].clear();
	}
	for(auto u : all)
		marked[u] = false;
}
 
void Solve(int star , bool keep = false)
{
	vector <int> all , tmp;
	all.push_back(star);
	marked[star] = true;
	while(!all.empty())
	{
		int v = all.back();  all.pop_back();
		key[col[v]] = true;
		tmp.push_back(v);
		Add_vert(v);
		Add_col(col[v]);
		while(!can.empty())
		{
			int u = can.back();  can.pop_back();
			if(!marked[u])
			{
				marked[u] = true;
				all.push_back(u);
			}
		}
	}
	can.clear();
	for(auto u : tmp)
	{
		key[col[u]] = false;
		marked[u] = false;
		for(auto v : adj[u])
			to[v.F].clear();
		if(keep)
			ans[u] = 1;
	}
	p[star] = tmp.size();
}
 
void Find_root(int v)
{
	vis[v] = true;
	if(nex[v] < 0)
	{
		root[v] = -1;
		return;
	}
	if(vis[nex[v]] == true)
	{
		root[v] = root[nex[v]];
		return;
	}
	Find_root(nex[v]);
	root[v] = root[nex[v]];
}
 
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n = r.size();
	m = u.size();
	ans.resize(n , 0);
	mn = N;
	for(int i = 0 ; i < n ; i++)
	{
		all_roots.push_back(i);
		col[i] = r[i];
		root[i] = i;
	}
	for(int i = 0 ; i < m ; i++)
	{
		adj[u[i]].push_back(make_pair(c[i] , v[i]));
		adj[v[i]].push_back(make_pair(c[i] , u[i]));
	}
	int prv = N;
	while(!all_roots.empty())
	{
		for(auto u : all_roots)
		{
			Find_nex(u);
			assert(nex[u] != u);
		}
		for(auto u : all_roots)
		{
			//cout << u << " nex: " << nex[u] << endl;
			if(nex[u] == -1)
			{
				Solve(u);
				if(p[u] == mn)
					cand.push_back(u);
				if(p[u] < mn)
				{
					cand.clear();
					cand.push_back(u);
					mn = p[u];
				}
				solved[u] = true;
			}
		}
		for(auto u : all_roots)  if(!vis[u])
		{
			Find_root(u);
		}
		for(auto u : all_roots)
			vis[u] = marked[u] = false;
		vector <int> tmp;
		for(auto u : all_roots)  if(root[u] == u)
			tmp.push_back(u);
		prv = all_roots.size();
		all_roots = tmp;
	}
	for(auto u : cand)
		Solve(u , 1);
	return ans;
}

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:151:6: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
  151 |  int prv = N;
      |      ^~~

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