Submission #439321

#	Time	Username	Problem	Language	Result	Execution time	Memory
439321		algorithm16	Keys (IOI21_keys)	C++17	37 / 100	2581 ms	50468 KiB

keys

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int cnt[300005],bio[300005],bio2[300005],n,m;
set <pair<int,int> > s;
set <int> s1[300005],s2;
vector <int> r,ans;
vector <pair<int,int> > v[300005];
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);
		//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<int(v[x].size());i++) {
			if(!bio2[v[x][i].second]) s1[v[x][i].second].insert(v[x][i].first);
			if(bio[v[x][i].first]) {
				if(bio2[v[x][i].second] && s.find(make_pair(1,v[x][i].first))!=s.end()) {
					s.erase(make_pair(1,v[x][i].first));
					s.insert(make_pair(0,v[x][i].first));
				}
				continue;
			}
			//bio[v[x][i].first]=1;
			//if(p==1) cout << x << " " << v[x][i].first << " " << v[x][i].second << "\n";
			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<int(v[x].size());i++) {
			if(bio[v[x][i].first] && bio2[v[x][i].second]) 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();
	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]=int(s2.size());
		mini=min(mini,cnt[i]);
	}
	for(int i=0;i<n;i++) {
		ans.push_back(cnt[i]==mini);
	}
	return ans;
}

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