Submission #484527

#	Time	Username	Problem	Language	Result	Execution time	Memory
484527		wwdd	Keys (IOI21_keys)	C++17	100 / 100	1196 ms	129440 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
class U {
	private:
		vi p,rk;
		int n;
	public:
		U(int sz) {
			n = sz;
			for(int i=0;i<n;i++) {
				p.push_back(i);
			}
			rk.assign(n,0);
		}
		int find(int a) {
			if(p[a] == a) {
				return a;
			}
			return p[a] = find(p[a]);
		}
		inline bool same(int a, int b) {
			return find(a) == find(b);
		}
		int un(int a, int b) {
			if(same(a,b)) {return -1;}
			int x = find(a);
			int y = find(b);
			if(rk[x] < rk[y]) {swap(x,y);}
			if(rk[x] == rk[y]) {rk[x]++;}
			p[y] = x;
			return x;
		}
};
struct NO {
	map<int,list<int>> eg;
	set<int> cols;
	list<int> act,reps;
	int sz;
	NO(int u) {
		sz = 1;
		reps.push_back(u);
	}
	void morg(NO& ot) {
		reps.splice(reps.end(),ot.reps);
		sz += ot.sz;
		ot.sz = -1;
		if(cols.size()+eg.size() < ot.cols.size()+ot.eg.size()) {
			swap(cols,ot.cols);
			swap(eg,ot.eg);
		}
		for(const auto& col: ot.cols) {
			if(eg.count(col)) {
				act.splice(act.end(),eg[col]);
				eg.erase(col);
			}
		}
		cols.insert(ot.cols.begin(),ot.cols.end());
		ot.cols.clear();
		for(auto& ek: ot.eg) {
			if(cols.count(ek.first)) {
				act.splice(act.end(),ek.second);
			} else {
				list<int>& cur = eg[ek.first];
				if(ek.second.size() > cur.size()) {
					swap(cur,ek.second);
				}
				cur.splice(cur.end(),ek.second);
			}
			ek.second.clear();
		}
		ot.eg.clear();
		act.splice(act.end(),ot.act);
	}
};

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {


	vector<NO> wu;
	for(int i=0;i<r.size();i++) {
		wu.emplace_back(i);
		wu[i].cols.insert(r[i]);
	}
	for(int i=0;i<u.size();i++) {
		int vu = u[i];
		int vv = v[i];
		int vc = c[i];
		if(vc == r[vu]) {
			wu[vu].act.push_back(vv);
		} else {
			wu[vu].eg[vc].push_back(vv);
		}
		if(vc == r[vv]) {
			wu[vv].act.push_back(vu);
		} else {
			wu[vv].eg[vc].push_back(vu);
		}
	}
	vi st;
	U bu(r.size());
	vector<bool> wac(r.size());
	vi vs(r.size());
	vi enb;
	for(int sti=0;sti<r.size();sti++) {
		if(vs[sti]) {continue;}
		vs[sti] = 1;
		st.push_back(sti);wac[sti] = 1;
		bool cont = true;
		int los;
		while(cont) {
			int vu = st.back();
			int nx = -1;
			while(!wu[vu].act.empty()) {
				int nu = wu[vu].act.back();
				nu = bu.find(nu);
				wu[vu].act.pop_back();
				if(nu == vu) {continue;}
				if(wac[nu]) {
					st.pop_back();wac[vu] = 0;
					while(!bu.same(nu,vu)) {
						int vv = st.back();st.pop_back();wac[vv] = 0;
						int com = bu.un(vv,vu);
						wu[com].morg(wu[vv+vu-com]);
						vu = com;
					}
					st.push_back(vu);wac[vu] = 1;
				} else if(vs[nu]) {
					cont = false;break;
				} else {
					nx = nu;break;
				}
			}
			if(nx == -1) {
				los = vu;
				break;
			} else {
				vs[nx] = 1;
				st.push_back(nx);
				wac[nx] = true;
			}
		}
		while(!st.empty()) {
			wac[st.back()] = false;
			st.pop_back();
		}
		if(cont) {
			enb.push_back(los);
		}
	}
	int ma = r.size()+1;
	for(const auto& mat: enb) {
		ma = min(ma,wu[mat].sz);
	}
	std::vector<int> ans(r.size(), 0);
	for(const auto& mat: enb) {
		if(wu[mat].sz == ma) {
			for(const auto& it: wu[mat].reps) {
				ans[it] = 1;
			}
		}
	}

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

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