Submission #439305

#	Time	Username	Problem	Language	Result	Execution time	Memory
439305		algorithm16	Keys (IOI21_keys)	C++17	9 / 100	2576 ms	44128 KiB

keys

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int cnt[200005],bio[200005],bio2[200005],n,m;
set <pair<int,int> > s;
set <int> s1[200005],s2;
vector <int> r;
vector <pair<int,int> > v[200005];
void f(int p) {
	for(int i=0;i<n;i++) {
		bio[i]=0;
		bio2[i]=0;
		s1[i].clear();
	}
	bio[p]=1;
	bio2[r[p]]=1;
	s.clear();
	s2.clear();
	s.insert(make_pair(0,p));
	while(!s.empty()) {
		int a=(*s.begin()).first,x=(*s.begin()).second;
		if(a) break;
		s.erase(s.begin());
		s2.insert(x);
		//cout << a << " " << x << "\n";
		//system("pause");
		bio[x]=1;
		bio2[r[x]]=1;
		for(set <int>::iterator it=s1[r[x]].begin();it!=s1[r[x]].end();it++) {
			if(s.find(make_pair(1,(*it)))!=s.end()) s.erase(make_pair(1,(*it)));
			s.insert(make_pair(0,(*it)));
		}
		s1[r[x]].clear();
		for(int i=0;i<v[x].size();i++) {
			if(bio[v[x][i].first]) continue;
			//bio[v[x][i].first]=1;
			s.insert(make_pair(!bio2[v[x][i].second],v[x][i].first));
			if(!bio2[v[x][i].second]) s1[v[x][i].second].insert(v[x][i].first);
		}
		for(int i=0;i<v[x].size();i++) {
			if(bio[v[x][i].first]) continue;
			bio[v[x][i].first]=1;
		}
	}
	//cout << "\n\n";
}
std::vector<int> find_reachable(std::vector<int> r1, std::vector<int> u1, std::vector<int> v1, std::vector<int> c1) {
	n=r1.size();
	m=u1.size();
	std::vector<int> ans(n);
	r=r1;
	int mini=1e9;
	for(int i=0;i<m;i++) {
		v[u1[i]].push_back(make_pair(v1[i],c1[i]));
		v[v1[i]].push_back(make_pair(u1[i],c1[i]));
	}
	for(int i=0;i<n;i++) {
		f(i);
		cnt[i]=s2.size();
		mini=min(mini,cnt[i]);
	}
	for(int i=0;i<n;i++) {
		ans[i]=(cnt[i]==mini);
	}
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'void f(int)':
keys.cpp:36:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i=0;i<v[x].size();i++) {
      |               ~^~~~~~~~~~~~
keys.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0;i<v[x].size();i++) {
      |               ~^~~~~~~~~~~~

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