Submission #836533

#	Time	Username	Problem	Language	Result	Execution time	Memory
836533		ma_moutahid	Keys (IOI21_keys)	C++17	20 / 100	3066 ms	32376 KiB

keys

#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vii vector<vi>
#define pi pair<int,int>
#define vp vector<pi>

vector<vp> g;

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u,
 std::vector<int> v, std::vector<int> c) {
	int n=r.size();
	g.resize(n);
	int m=u.size();
	for(int i=0;i<m;i++){
		g[u[i]].push_back(make_pair(c[i],v[i]));
		g[v[i]].push_back(make_pair(c[i],u[i]));
	}
	vi result(n);
	for(int root=0;root<n;root++){
		vi traversed(n);
		traversed[root]=1;
		set<int>keys;
		keys.insert(r[root]);
		int nk=1;
		multimap<int,int>bridges;
		for(pi p:g[root]){
			if(traversed[p.second])continue;
			bridges.insert(p);
		}
		while(nk){
			nk=0;
			for(int key:keys){
				auto itr=bridges.find(key);
				while(itr!=bridges.end()){
					if(!traversed[itr->second]){
						traversed[itr->second]=true;
						int old=keys.size();
						keys.insert(r[itr->second]);
						if(old!=keys.size())nk++;
						result[root]++;
						for(pi p:g[itr->second]){
							if(traversed[p.second])continue;
							bridges.insert(p);
						}
					}
					bridges.erase(itr);
					itr=bridges.find(key);
				}

			}
		}

	}
	int mn=*min_element(result.begin(),result.end());
	for(int i=0;i<n;i++){
		result[i]=(result[i]==mn);
	}

	

	return result;
}

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:41:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |       if(old!=keys.size())nk++;
      |          ~~~^~~~~~~~~~~~~

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