Submission #826915

#	Time	Username	Problem	Language	Result	Execution time	Memory
826915		ymm	Keys (IOI21_keys)	C++17	100 / 100	2552 ms	158856 KiB

keys

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 300'010;
vector<pii> A[N];
int key[N];

template<class T>
void clear_and_free(T &x) { T tmp; tmp.swap(x); }

namespace dsu {
	struct cmp_t {
		int vis;
		cmp_t *par;
		vector<int> nds;
		vector<int> adj;
		map<int,vector<int>> if_had_key;
		set<int> keys;
		bool sink;
		int cost;
	} cmp[N];

	void init(int n)
	{
		Loop (i,0,n) {
			auto *c = &cmp[i];
			c->vis = 0;
			c->par = 0;
			c->nds = {(int)i};
			for (auto [v, k] : A[i]) {
				if (k == key[i])
					c->adj.push_back(v);
				else
					c->if_had_key[k].push_back(v);
			}
			c->keys = {key[i]};
			c->sink = 0;
			c->cost = 5 + A[i].size();
		}
	}

	cmp_t *rt(cmp_t *c) { return c->par? (c->par = rt(c->par)): c; }
	cmp_t *rt(int v) { return rt(&cmp[v]); }
	void merge(cmp_t *c, cmp_t *d) {
		c = rt(c);
		d = rt(d);
		if (c == d)
			return;
		//cerr << "merge(" << c-cmp << ", " << d-cmp << ")\n";
		if (c->cost < d->cost)
			swap(c, d);
		c->cost += d->cost;
		c->nds.insert(c->nds.end(), d->nds.begin(), d->nds.end());
		c->adj.insert(c->adj.end(), d->adj.begin(), d->adj.end());
		for (auto k : d->keys)
			c->cost -= 4*!c->keys.insert(k).second;
		for (auto &[k, vec] : d->if_had_key) {
			if (c->keys.count(k)) {
				c->adj.insert(c->adj.end(), vec.begin(), vec.end());
			} else {
				auto &tmp = c->if_had_key[k];
				tmp.insert(tmp.end(), vec.begin(), vec.end());
			}
		}
		for (auto k : d->keys) {
			auto &vec = c->if_had_key[k];
			c->adj.insert(c->adj.end(), vec.begin(), vec.end());
			clear_and_free(vec);
		}
		d->par = c;
		clear_and_free(d->nds);
		clear_and_free(d->adj);
		clear_and_free(d->if_had_key);
		clear_and_free(d->keys);
	}
}
typedef dsu::cmp_t *cmp;

void dfs(cmp v, int t)
{
	vector<cmp> anc;
	anc.push_back(v);
	v->vis = t;
	for (;;) {
		cmp v = anc.back();
		//cerr << v-dsu::cmp << '\n';
		if (v->adj.size()) {
			auto u = dsu::rt(v->adj.back());
			v->adj.pop_back();
			v->cost--;
			if (u == v)
				continue;
			cerr << v-dsu::cmp << " -> " << u-dsu::cmp << '\n';
			if (u->vis == t) {
				while (dsu::rt(v) != dsu::rt(u)) {
					auto x = anc.back(); anc.pop_back();
					auto y = anc.back(); anc.pop_back();
					dsu::merge(x, y);
					anc.push_back(dsu::rt(x));
				}
			} else if (u->vis) {
				return;
			} else {
				u->vis = t;
				anc.push_back(u);
			}
		} else {
			v->sink = 1;
			return;
		}
	}
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = r.size();
	int m = u.size();
	Loop (i,0,n)
		key[i] = r[i];
	Loop (i,0,m) {
		int x = v[i], y = u[i], z = c[i];
		A[x].emplace_back(y, z);
		A[y].emplace_back(x, z);
	}
	dsu::init(n);
	int nxt = 1;
	Loop (i,0,n) {
		cmp c = &dsu::cmp[i];
		if (c->par || c->vis)
			continue;
		dfs(c, nxt++);
	}
	int mn = N;
	Loop (i,0,n) {
		cmp c = &dsu::cmp[i];
		if (c->sink) {
			//cerr << c-dsu::cmp << ": " << c->nds.size() << '\n';
			mn = min<int>(mn, c->nds.size());
		}
	}
	vector<int> ans(n);
	Loop (i,0,n) {
		cmp c = &dsu::cmp[i];
		if (c->sink && c->nds.size() == mn) {
			for (auto x : c->nds)
				ans[x] = 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:146:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  146 |   if (c->sink && c->nds.size() == mn) {
      |                  ~~~~~~~~~~~~~~^~~~~

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