Submission #1268074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268074		MateiKing80	Spy 3 (JOI24_spy3)	C++20	0 / 100	16 ms	1752 KiB

Aoi

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

using namespace std;

using ll = long long;
const ll inf = 1e16;
#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(int n, int m, int q, int k, vector<int> a, vector<int> b, vector<long long> c, vector<int> t, vector<int> 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);
	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;
				pq.push({-dist[j], j});
			}
		}
	}
	
	vector<int> contrib(n);
	for (auto i : t) {
		contrib[i] ++;
		while (i != 0) {
			i = (a[papa[i]] == i ? b[papa[i]] : a[papa[i]]);
			contrib[i] ++;
		}
	}
	for (int i = 1; i < n; i ++)
		sons[(a[papa[i]] == i ? b[i] : a[i])].push_back(i);
	
	vector<bool> inTree(n);
	
	for (int i = 0; i < n; i ++) {
		int mx = 0;
		for (auto j : sons[i])
			mx = max(mx, contrib[(a[j] == i ? b[j] : a[j])]);
		if (mx != contrib[i])
			inTree[i] = 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 = 1e16;
#define fr first
#define sc second

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(int n, int m, int q, int k, vector<int> a, vector<int> b, vector<ll> c, vector<int> t, vector<int> 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<int> 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: 0 / 100