Submission #435915

#	Time	Username	Problem	Language	Result	Execution time	Memory
435915		frodakcin	Keys (IOI21_keys)	C++17	100 / 100	2136 ms	164904 KiB

keys

#include <cassert>
#include <cstring>
#include <stack>
#include <vector>
#include <set>

template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}

const int MN = 3e5+10;

int N, M;
struct edge
{
	public:
		int n, w;
		bool operator < (const edge& o) const {return w < o.w || !(o.w < w) && n < o.n;}
};

struct DSU
{
	public:
		std::vector<int> p, r;

		DSU(int N): p(N, -1), r(N, 0) {}
		int find(int n) {return p[n]==-1 ? n : p[n]=find(p[n]);}
		bool merge(int a, int b)
		{
			a=find(a), b=find(b);
			assert(a!=b);
			if(a==b) return 0;
			if(r[a]<r[b]) std::swap(a,b);
			p[b]=a, r[a]+=r[a]==r[b], r[b]=-1;
			return 1;
		}
};
DSU dsu(MN);

std::set<edge> a[MN];
std::set<int> col[MN];
std::vector<int> todo[MN];

int d[MN], l[MN], ctr, cc, sz[MN]; // scc
bool in_stack[MN], out[MN], good[MN];
std::stack<int> stk;
std::vector<int> g[MN];

void dfs(int n)
{
	d[n] = l[n] = ctr++;
	stk.push(n);
	in_stack[n] = 1;

	for(;!todo[n].empty();)
	{
		int x=todo[n].back(); todo[n].pop_back();
		if(d[x] == -1)
		{
			dfs(x), ckmin(l[n], l[x]);
			if(!in_stack[x])
				out[n]=1;
		}
		else if(in_stack[x])
			ckmin(l[n], d[x]);
		else
			out[n]=1;

		int u=dsu.find(n), v=dsu.find(x);
		if(u!=v)
		{
			dsu.merge(u, v);
			if(dsu.p[v] == -1) std::swap(u,v);
			//v -> u
			if(col[u].size()+a[u].size() < col[v].size()+a[v].size())
				col[u].swap(col[v]), a[u].swap(a[v]);

			for(int c:col[v])
				if(col[u].insert(c).second)
				{
					auto it=a[u].lower_bound({-1,c});
					for(;it != a[u].end() && it->w == c;it=a[u].erase(it))
						todo[n].push_back(it->n);
				}
			for(auto c:a[v])
				if(col[u].find(c.w) != col[u].end())
					todo[n].push_back(c.n);
				else a[u].insert(c);

			col[v].clear();
			a[v].clear();
		}
		/*
		printf("MERGE %d - %d\n", n, x);
		printf("COL: "); for(auto z:col[dsu.find(n)]) printf("%d ", z); printf("\n");
		printf("EDG: "); for(auto z:a[dsu.find(n)]) printf("(%d,%d) ", z.n, z.w); printf("\n");
		*/
	}

	if(l[n] == d[n])
	{
		++cc;
		good[cc]=1;
		for(;;)
		{
			int x=stk.top(); stk.pop();
			++sz[cc];
			if(out[x]) good[cc]=0;
			g[cc].push_back(x);
			in_stack[x] = 0;

			if(x == n) break;
		}
	}
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
	memset(d, -1, sizeof d);

	N = r.size();
	M = u.size();
	std::vector<int> ans(r.size(), 0);

	for(int i=0;i<M;++i)
	{
		a[u[i]].insert({v[i], c[i]});
		a[v[i]].insert({u[i], c[i]});
	}
	for(int i=0;i<N;++i)
	{
		col[i].insert(r[i]);
		auto it=a[i].lower_bound({-1,r[i]});
		for(;it != a[i].end() && it->w == r[i];it = a[i].erase(it))
			todo[i].push_back(it->n);
	}

	for(int i=0;i<N;++i)
	{
		if(d[i] == -1)
			dfs(i);
	}

	int msz=N;
	for(int i=1;i<=cc;++i)
		if(good[i])
			ckmin(msz, sz[i]);
	for(int i=1;i<=cc;++i)
		if(good[i] && sz[i] == msz)
			for(int x:g[i])
				ans[x]=1;

	return ans;
}

Compilation message (stderr)

keys.cpp: In member function 'bool edge::operator<(const edge&) const':
keys.cpp:17:71: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   17 |   bool operator < (const edge& o) const {return w < o.w || !(o.w < w) && n < o.n;}
      |                                                            ~~~~~~~~~~~^~~~~~~~~~

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