Submission #560678

#	Time	Username	Problem	Language	Result	Execution time	Memory
560678		AlperenT	Keys (IOI21_keys)	C++17	37 / 100	3076 ms	65352 KiB

keys

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

int cnt[N];

struct DSU{
	int par[N], setsize[N];

	void reset(int n){
		for(int i = 0; i < n; i++) par[i] = i, setsize[i] = 1;
	}

	int setfind(int a){
		if(a == par[a]) return a;
		else return par[a] = setfind(par[a]);
	}

	void setunion(int a, int b){
		a = setfind(a), b = setfind(b);

		if(a != b){
			if(setsize[b] > setsize[a]) swap(a, b);
			par[b] = par[a];
			setsize[a] += setsize[b];
		}
	}
};

DSU dsu;

struct Edge{
	int b, key;
};

vector<Edge> graph[N];

set<int> samekey[N], curnodes;

vector<int> curedges[N], nodestocheck, seenkeys;

bool keyflag[N];

void setkey(int key){
	if(keyflag[key] == false){
		keyflag[key] = true;
		for(auto v : curedges[key]) nodestocheck.push_back(v);
		curedges[key].clear();
	}
}

vector<int> find_reachable(vector<int> inp_r, vector<int> inp_u, vector<int> inp_v, vector<int> inp_c){
	int n = inp_r.size(), m = inp_u.size();

	vector<int> ans(n, 0);

	dsu.reset(n);

	for(int i = 0; i < m; i++){
		graph[inp_u[i]].push_back({inp_v[i], inp_c[i]});

		if(inp_c[i] == inp_r[inp_u[i]]) samekey[inp_u[i]].insert(inp_v[i]);

		graph[inp_v[i]].push_back({inp_u[i], inp_c[i]});

		if(inp_c[i] == inp_r[inp_v[i]]) samekey[inp_v[i]].insert(inp_u[i]);
	}

	for(int v = 0; v < n; v++){
		dsu.reset(n);

		curnodes.insert(v);

		for(auto e : graph[v]){
			curedges[e.key].push_back(e.b);

			seenkeys.push_back(e.key);
		}

		seenkeys.push_back(inp_r[v]);

		setkey(inp_r[v]);

		while(!nodestocheck.empty()){
			int u = nodestocheck.back();
			nodestocheck.pop_back();

			if(dsu.setfind(v) == dsu.setfind(u)) continue;

			curnodes.insert(u);
			dsu.setunion(v, u);

			for(auto e : graph[u]){
				if(keyflag[e.key]) nodestocheck.push_back(e.b);
				else curedges[e.key].push_back(e.b);

				seenkeys.push_back(e.key);
			}

			setkey(inp_r[u]);

			seenkeys.push_back(inp_r[u]);
		}

		skip:

		cnt[v] = dsu.setsize[dsu.setfind(v)];

		for(auto key : seenkeys){
			curedges[key].clear();
			keyflag[key] = false;
		}

		curnodes.clear(), nodestocheck.clear(), seenkeys.clear();
	}

	int mn = *min_element(cnt, cnt + n);

	for(int i = 0; i < n; i++) ans[i] = cnt[i] == mn;

	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:107:3: warning: label 'skip' defined but not used [-Wunused-label]
  107 |   skip:
      |   ^~~~

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