제출 #1268080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268080		MateiKing80	Spy 3 (JOI24_spy3)	C++20	85 / 100	75 ms	3500 KiB

Aoi

#include <bits/stdc++.h>
#include "Aoi.h"

using namespace std;

using ll = long long;
const ll inf = 1e17;
#define int ll
#define fr first
#define sc second

string toString(int n, int nr) {
	string ans;
	for (int i = 0; i < n; i ++) {
		ans.push_back('0' + nr % 2);
		nr /= 2;
	}
	return ans;
}

string aoi(signed n, signed m, signed q, signed k, vector<signed> a, vector<signed> b, vector<long long> c, vector<signed> t, vector<signed> x) {
	vector<vector<int>> vec(n);
	for (int i = 0; i < m; i ++) {
		vec[a[i]].push_back(i);
		vec[b[i]].push_back(i);
	}
	vector<bool> viz(n, false);
	vector<ll> dist(n, inf);
	vector<int> papa(n), depth(n);
	vector<vector<int>> sons(n);
	priority_queue<pair<ll, int>> pq;
	pq.push({0, 0});
	dist[0] = 0;
	while (!pq.empty()) {
		auto y = pq.top();
		pq.pop();
		if (viz[y.sc])
			continue;
		viz[y.sc] = true;
		for (auto i : vec[y.sc]) {
			int j = (a[i] == y.sc ? b[i] : a[i]);
			if (dist[j] > dist[y.sc] + c[i]) {
				dist[j] = dist[y.sc] + c[i];
				papa[j] = i;
				depth[j] = 1 + depth[y.sc];
				pq.push({-dist[j], j});
			}
		}
	}
	
	vector<int> realPapa(n);
	for (int i = 1; i < n; i ++)
		realPapa[i] = (a[papa[i]] == i ? b[papa[i]] : a[papa[i]]);
	
	vector<bool> inTree(n, false);
	
	for (int i = 0; i < q; i ++)
		for (int j = i; j < q; j ++) {
			int ii = t[i], jj = t[j];
			while (depth[ii] > depth[jj])
				ii = realPapa[ii];
			while (depth[ii] < depth[jj])
				jj = realPapa[jj];
			while (ii != jj) {
				ii = realPapa[ii];
				jj = realPapa[jj];
			}
			inTree[ii] = true;
		}
	
	vector<int> papaTree(n);
	vector<vector<int>> fiiTree(n);
	
	int root = 0;
	for (int i = 0; i < n; i ++) {
		if (!inTree[i])
			continue;
		int nod = i;
		while ((nod == i || !inTree[nod]) && nod != 0)
			nod = (a[papa[nod]] == nod ? b[papa[nod]] : a[papa[nod]]);
		if (i == 0 || (nod == 0 && i != 0 && !inTree[0])) {
			root = i;
			papaTree[i] = -1;
		} else {
			papaTree[i] = nod;
			fiiTree[papaTree[i]].push_back(i);
		}
	}
	
	
	string ans;
	int nr = 0;
	vector<int> ass(n);
	for (int i = 0; i < n; i ++)
		if (inTree[i])
			ass[i] = nr ++;

	for (int i = 0; i < n; i ++)
		if (inTree[i]) {
			if (i == root) {
				ans += toString(5, ass[i]);
			} else {
				ans += toString(5, ass[papaTree[i]]);
			}
		}
	for (int i = 0; i < q; i ++)
		ans += toString(5, ass[t[i]]);
	vector<int> lipsa(m, -1), raspuns(k, 31);
	for (int i = 0; i < k; i ++)
		lipsa[x[i]] = i;
	for (int i = 0; i < n; i ++) {
		if (!inTree[i])
			continue;
		int nod = i;
		while ((nod == i || !inTree[nod]) && nod != 0) {
			if (lipsa[papa[nod]] != -1)
				raspuns[lipsa[papa[nod]]] = ass[i];
			nod = (a[papa[nod]] == nod ? b[papa[nod]] : a[papa[nod]]);
		}
	}
	
	for (int i = 0; i < k; i ++)
		ans += toString(5, raspuns[i]);
	
	return ans;
}

Bitaro

#include <bits/stdc++.h>
#include "Bitaro.h"

using namespace std;

using ll = long long;
const ll inf = 1e17;
#define fr first
#define sc second
#define int ll

int toInt(int n, string s) {
	int nr = 0;
	for (int i = n - 1; i >= 0; i --) {
		nr *= 2;
		nr += s[i] - '0';
	}
	return nr;
}

int inter(int l, int r, string &t) {
	string s;
	for (int i = l; i < r; i ++)
		s += t[i];
	return toInt(r - l, s);
}

void bitaro(signed n, signed m, signed q, signed k, vector<signed> a, vector<signed> b, vector<ll> c, vector<signed> t, vector<signed> x, string s) {
	int noduri = (s.size() - 5 * k - 5 * q) / 5;
	vector<vector<int>> uses(noduri);
	for (int i = 0; i < k; i ++) {
		int g = inter(5 * i + 5 * (q + noduri), 5 * (i + 1) + 5 * (q + noduri), s);
		if (g == 31)
			continue;
		uses[g].push_back(x[i]);
	}
	vector<bool> cooked(m, false);
	for (auto i : x) {
		cooked[i] = true;
		c[i] = 0;
	}
	for (int qs = 0; qs < q; qs ++) {
		int leaf = inter(5 * (qs + noduri), 5 * (qs + noduri + 1), s);
		vector<vector<int>> vec(n);
		for (int i = 0; i < m; i ++) {
			if (!cooked[i]) {
				vec[a[i]].push_back(i);
				vec[b[i]].push_back(i);
			}
		}
		auto baga = uses[leaf];
		int j = leaf;
		while (inter(5 * j, 5 * (j + 1), s) != j) {
			j = inter(5 * j, 5 * (j + 1), s);
			for (auto l : uses[j])
				baga.push_back(l);
		}
		for (auto i : baga) {
			vec[a[i]].push_back(i);
			vec[b[i]].push_back(i);
		}
		vector<bool> viz(n, false);
		vector<ll> dist(n, inf);
		vector<int> papa(n);
		vector<vector<int>> sons(n);
		priority_queue<pair<ll, int>> pq;
		pq.push({0, 0});
		dist[0] = 0;
		while (!pq.empty()) {
			auto y = pq.top();
			pq.pop();
			if (viz[y.sc])
				continue;
			viz[y.sc] = true;
			for (auto i : vec[y.sc]) {
				int l = (a[i] == y.sc ? b[i] : a[i]);
				if (dist[l] > dist[y.sc] + c[i]) {
					dist[l] = dist[y.sc] + c[i];
					papa[l] = i;
					pq.push({-dist[l], l});
				}
			}
		}
		
		vector<signed> ans;
		int nod = t[qs];
		while (nod != 0) {
			ans.push_back(papa[nod]);
			nod = (a[papa[nod]] == nod ? b[papa[nod]] : a[papa[nod]]);
		}
		reverse(ans.begin(), ans.end());
		answer(ans);
	}
}

• Subtask 1: 85 / 100