Submission #445077

#	Time	Username	Problem	Language	Result	Execution time	Memory
445077		hhhhaura	Keys (IOI21_keys)	C++17	100 / 100	1407 ms	140844 KiB

keys

#include <vector>
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

#define INF 1000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define ll long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() {cerr << endl;}
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif 
int ii;
vector<vector<pii>> mp;
vector<int> R, instack;
set<int> avail;
namespace dsu {
	int n;
	vector<int> sz, par;
	vector<set<int>> col;
	vector<set<pii>> good, bad;
	void init_(int _n) {
		n = _n;
		sz.assign(n + 1, 1);
		par.assign(n + 1, 0);
		col.assign(n + 1, set<int>());
		good.assign(n + 1, set<pii>());
		bad.assign(n + 1, set<pii>());
		rep(i, 0, n - 1) {
			par[i] = i;
			col[i].insert(R[i]);
			for(auto j : mp[i]) {
				if(j.first == R[i]) good[i].insert(j);
				else bad[i].insert(j);
			}
		}
	}
	int find_par(int a) {
		while(a != par[a]) a = par[a];
		return par[a];
	}
	bool same(int a, int b) {
		return find_par(a) == find_par(b);
	}
	void unite(int a, int b) {
		int aa = find_par(a);
		int bb = find_par(b);
		if(aa == bb) return;
		if(sz[aa] < sz[bb]) swap(aa, bb);
		sz[aa] += sz[bb], par[bb] = aa;
		if(good[aa].size() < good[bb].size()) {
			for(auto i : good[aa]) good[bb].insert(i);
			good[aa].swap(good[bb]);
		}
		else for(auto i : good[bb]) good[aa].insert(i);
		good[bb].clear();
		
		for(auto i : col[bb]) {
			col[aa].insert(i);
			auto it = bad[aa].lower_bound(pii(i, -INF));
			while(it != bad[aa].end() && it->first == i ) {
				good[aa].insert({it->first, it->second});
				auto temp = it; it = next(it);
				bad[aa].erase(temp);
			}
		}
		// wrong
		col[bb].clear();
		for(auto i : bad[bb]) {
			if(col[aa].find(i.first) != col[aa].end()) {
				good[aa].insert(i);
			}
			else bad[aa].insert(i);
		}
		bad[bb].clear();
	}
};
int get(int x) { return dsu::find_par(x); }
void operate(int x) {
	stack<int> st; 
	st.push(x);
	instack[x] = ii;
	bool ok = 1;
	while(dsu::good[get(st.top())].size()) {
		int p = get(st.top());
		pii cur = *dsu::good[p].begin();
		dsu::good[p].erase(dsu::good[p].find(cur));
		if(dsu::same(cur.second, p)) continue;
		cur.second = get(cur.second);
		if(instack[cur.second] && instack[cur.second] != ii) {
			ok = 0;
			break;
		} 
		else if(instack[cur.second]) {
			while(get(st.top()) != get(cur.second)) {
				int k = st.top(); st.pop();
				dsu::unite(k, cur.second);
			}
		}
		else {
			instack[cur.second] = ii;
			st.push(cur.second);
		}
	}
	if(ok) avail.insert(get(st.top()));
	return;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	vector<int> ans(r.size(), 0);
	int n = r.size();
	R = r, ii = 0;
	mp.assign(n, vector<pii>());
	instack.assign(n, 0);
	rep(i, 0, signed(u.size()) - 1) {
		mp[u[i]].push_back({c[i], v[i]});
		mp[v[i]].push_back({c[i], u[i]});
	}
	dsu::init_(n);
	rep(i, 0, n - 1) {
		if(!instack[i]) ii ++, operate(i);
	}
	int mn = INF;
	rep(i, 0, n - 1) if(avail.find(get(i)) != avail.end()) {
		mn = min(mn, dsu::sz[get(i)]);
	}
	rep(i, 0, n - 1) if(avail.find(get(i)) != avail.end()) {
		if(dsu::sz[get(i)] == mn) ans[i] = 1;
	}
	return ans;
}

Compilation message (stderr)

keys.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
keys.cpp:25:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   25 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
keys.cpp:25:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   25 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~

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