Submission #598609

#	Time	Username	Problem	Language	Result	Execution time	Memory
598609		definitelynotmee	Keys (IOI21_keys)	C++17	67 / 100	1551 ms	51508 KiB

keys

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename t>
using matrix = vector<vector<t>>;


std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	vector<int> ans(r.size(), 1);
	int n = r.size();

	matrix<pii> g(n);
	for(int i = 0; i < u.size(); i++){
		g[u[i]].push_back({v[i],c[i]});
		g[v[i]].push_back({u[i],c[i]});
	}
	if(n <= 2000){
		for(int root = 0; root < n; root++){
			vector<int> check(n), got(n);
			matrix<int> whenget(n);

			vector<int> st = {root};

			while(!st.empty()){
				int cur = st.back();
				st.pop_back();
				if(check[cur])
					continue;
				check[cur] = 1;
				got[r[cur]] = 1;
				while(!whenget[r[cur]].empty()){
					st.push_back(whenget[r[cur]].back());
					whenget[r[cur]].pop_back();
				}
				for(pii i : g[cur]){
					if(got[i.ss])
						st.push_back(i.ff);
					else whenget[i.ss].push_back(i.ff);
				}
			}
			ans[root] = accumulate(all(check),0);
		}

		int mini = *min_element(all(ans));
		for(int i = 0; i < n; i++)
			ans[i] = ans[i] == mini;
	} else {
		vector<int> color(n);
		for(int i = 0; i < n; i++)
			color[i] = 1<<r[i];

		int it = 30;
		vector<int> scc(n);
		int timer = -1;

		while(it--){
			fill(all(scc),0);

			vector<int> check(n), combcolor(n);
			vector<int> out;
			auto dfs =[&](int id, auto dfs)->void{
				check[id] = 1;
				for(pii i : g[id]){
					if(((1<<i.ss)&color[id])&&!check[i.ff])
						dfs(i.ff,dfs);
				}
				out.push_back(id);
			};

			for(int i = 0; i < n; i++){
				if(!check[i])
					dfs(i,dfs);
			}
			timer = -1;
			auto rdfs =[&](int id, auto dfs)->void{
				check[id] = 2;
				scc[id] = timer;
				combcolor[scc[id]]|=color[id];

				for(pii i : g[id]){
					if(((1<<i.ss)&color[i.ff])&&check[i.ff]!=2)
						dfs(i.ff,dfs);
				}
			};
			reverse(all(out));

			for(int i = 0; i < n; i++){
				if(check[out[i]]!=2)
					timer++,rdfs(out[i],rdfs);
			}
			for(int i = 0; i < n; i++){
				color[i] = combcolor[scc[i]];
			}
			// for(int i : scc)
			// 	cout << i << ' ';
			// cout << '\n';
		}
		vector<int> isvalid(n,1), sz(n,0);
		for(int v = 0; v < n; v++){
			for(pii i : g[v]){
				if(((1<<i.ss)&color[v])&&scc[i.ff]!=scc[v])
					isvalid[scc[v]] = 0;
			}
			sz[scc[v]]++;
		}
		int mini = 1<<30;

		for(int i = 0; i <= timer; i++){
			if(isvalid[i]) mini = min(mini,sz[i]);
			//cout << sz[i] << ' ' << isvalid[i] << '\n';
		}
		for(int i = 0; i < n; i++){
			ans[i] = sz[scc[i]] == mini && isvalid[scc[i]];
		}
	}


	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:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~

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