제출 #441877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441877		Stickfish	열쇠 (IOI21_keys)	C++17	37 / 100	3070 ms	30088 KiB

keys

#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;

const int MAXN = 3e5 + 123;
vector<pair<int, int>> edg[MAXN];
int keyget[MAXN];
bitset<MAXN> used;

vector<int> solve_quad(int n){
	vector<int> ans(n);
	bitset<MAXN> used_cl;
	vector<vector<int>> reachable(n);
	for(int i = 0; i < n; ++i){
		used.reset();
		used_cl.reset();
		for(int j = 0; j < n; ++j){
			reachable[j].clear();
		}
		vector<int> stck = {i};
		while(stck.size()){
			int v = stck.back();
			stck.pop_back();
			if(used[v])
				continue;
			used[v] = used_cl[keyget[v]] = 1;
			for(auto u : reachable[keyget[v]]){
				stck.push_back(u);
			}
			reachable[keyget[v]].clear();
			for(auto [u, keyneed] : edg[v]){
				if(used[u])
					continue;
				if(used_cl[keyneed]){
					stck.push_back(u);
				} else {
					reachable[keyneed].push_back(u);
				}
			}
		}
		//for(int j = 0; j < n; ++j)
			//cout << used[j];
		//cout << '\n';
		ans[i] = used.count();
	}
	return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	int m = u.size();
	for(int i = 0; i < n; ++i){
		keyget[i] = r[i];
	}
	for(int i = 0; i < m; ++i){
		edg[u[i]].push_back({v[i], c[i]});
		edg[v[i]].push_back({u[i], c[i]});
	}
	if(n <= 2000 && m <= 2000){
		vector<int> ans = solve_quad(n);
		int mn = *min_element(ans.begin(), ans.end());
		for(int i = 0; i < n; ++i)
			ans[i] = (ans[i] == mn);
		return ans;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^

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