Submission #1223921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223921		nikulid	Keys (IOI21_keys)	C++20	20 / 100	3093 ms	12364 KiB

keys

#include <vector>
#include <map>
#include <iostream>

using namespace std;

//#define dout if(1==1)cout
#define pb push_back
#define mp make_pair

/*
 
	AAARRGGHHHH

*/


vector<int> keys(2005, 0);

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n=r.size();
	int m=u.size();

	vector<int> ans(n, 1);
	if(n>2000 || m>2000)return ans;

	vector<vector<int>> adj(n);
	vector<vector<int>> keyr(n);
	for(int i=0; i<m; i++){
		adj[u[i]].pb(v[i]);
		keyr[u[i]].pb(c[i]);

		adj[v[i]].pb(u[i]);
		keyr[v[i]].pb(c[i]);

	}
	// vector<int> reach(n);
	map<int, vector<int>> keys;
	vector<bool> visitted, keys_owned;
	vector<int> p(n, -1);
	vector<int> neighbours;
	int n_visitted, prev_n_visitted;

	int curnode;
	
	for(int t=0; t<n; t++){
		cerr<<"\t\tt="<<t<<"\n";
		// init..
		keys.clear();
		visitted = vector<bool>(2005, 0);
		keys_owned = vector<bool>(2005, 0);
		
		keys_owned[r[t]]=1;
		visitted[t]=1;

		for(int i=0; i<adj[t].size(); i++){
			// cycle through initial paths
			keys[keyr[t][i]].pb(adj[t][i]);
		}

		n_visitted=1;
		prev_n_visitted=0;

		// ...
		cerr<<"keys.size() -> "<<keys.size()<<"\n";

		bool progress=true;
		while(progress){
			cerr<<"#";
			progress=false;
			//prev_n_visitted = n_visitted;
			for(auto it=keys.begin(); it!=keys.end(); it++){
				// [for every] keys that would be useful...
				if((it->second).size()==0)continue;
				if(keys_owned[it->first]){
					neighbours.clear();
					for(auto e:it->second){
						neighbours.pb(e);
					}
					(it->second).clear();
					progress=true;
					for(int v=0; v<(neighbours.size()); v++){
						if(visitted[neighbours[v]]) continue;
						// new UNVISITTED node!
						visitted[neighbours[v]]=1;
						curnode = neighbours[v];
						cerr<<"we can visit "<<curnode<<"\n";

						n_visitted++;
						keys_owned[r[curnode]]=1;
						for(int e=0; e<adj[curnode].size(); e++){
							if(!visitted[adj[curnode][e]]){
								keys[keyr[curnode][e]].pb(adj[curnode][e]);
							}
						}
					}
				}
			}
		}


		p[t] = n_visitted;
	}
	
	int smol=p[0];
	for(int i=1; i<n; i++){
		smol = min(smol, p[i]);
	}
	ans = vector<int>(n, 0);
	for(int i=0; i<n; i++){
		ans[i] = (p[i]==smol);
	}
		

	return ans;
}

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