Submission #560666

#	Time	Username	Problem	Language	Result	Execution time	Memory
560666		AlperenT	Keys (IOI21_keys)	C++17	0 / 100	15 ms	28500 KiB

keys

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

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++){
		if(dsu.setsize[dsu.setfind(v)] != -1){
			bool isbad = false;

			curnodes.insert(v);

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

				seenkeys.push_back(e.key);
			}

			setkey(inp_r[v]);

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

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

				if(dsu.setsize[dsu.setfind(u)] == -1){
					isbad = true;
					goto skip;
				}

				bool flag = false;

				if(curnodes.size() <= samekey[u].size()){
					for(auto w : curnodes){
						if(samekey[u].find(w) != samekey[u].end()){
							flag = true;
							break;
						}
					}
				}
				else{
					for(auto w : samekey[u]){
						if(curnodes.find(w) != curnodes.end()){
							flag = true;
							break;
						}
					}
				}

				if(flag){
					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]);
				}
				else{
					isbad = true;
					goto skip;
				}
			}

			skip:

			if(isbad) dsu.setsize[dsu.setfind(v)] = -1;

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

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

	int mn = n + 1;

	for(int v = 0; v < n; v++){
		if(dsu.setsize[dsu.setfind(v)] != -1){
			mn = min(mn, dsu.setsize[dsu.setfind(v)]);
		}
	}

	for(int v = 0; v < n; v++){
		if(dsu.setsize[dsu.setfind(v)] == mn){
			ans[v] = 1;
		}
	}

	return ans;
}

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