제출 #1268012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268012		MateiKing80	Spy 3 (JOI24_spy3)	C++20	0 / 100	4 ms	1748 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});
			}
		}
	}
	for (int i = 0; i < n; i ++)
		cout << papa[i] << " ";
	cout << "SKIBIDI\n";
	vector<int> contrib(n);
	for (auto i : t) {
		contrib[i] ++;
		while (i != 0)
			i = (a[papa[i]] == i ? b[papa[i]] : a[papa[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 (nod == 0) {
			root = i;
			papaTree[i] = -1;
		} else {
			papaTree[i] = nod;
			fiiTree[papaTree[i]].push_back(i);
		}
	}
	
	string ans;
	int nr = -1;
	for (int i = 0; i < n; i ++)
		if (inTree[i])
			nr ++;
	//ans += toString(5, nr);
	
	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]]);
			}
		}
	
	//AM TRANSMIS ARBORELE
	//trebuie sa trimitem acum in ce loc din arbore se afla fiecare muchie lipsa
	
	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;
}

/*           
            |
            1
           /\
          2  3
         /\  /\          
        5  67  8


		trebuie acum sa reusesc sa codific arborele
		trimit prima data numarul de noduri din arbore
		acesta este maxim 2 * q -> adica 5 biti
*/

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 += s[i] - '0';
		nr *= 2;
	}
	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) {
	vector<int> tsort;
	for (int i = 0; i < q; i ++)
		tsort.push_back(i);
	sort(tsort.begin(), tsort.end(), [&] (int u, int v) {return t[u] < t[v];});
	int noduri = s.size() - 5 * k;
	vector<bool> isLeaf(noduri, true);
	for (int i = 0; i < noduri; i ++) {
		if (inter(5 * i, 5  * (i + 1), s) != i)
			isLeaf[inter(5 * i, 5  * (i + 1), s)] = true;
	}
	vector<int> ass(noduri);
	int p = 0;
	for (int i = 0; i < noduri; i ++) {
		if (isLeaf[i])
			ass[i] = tsort[p ++];
	}
	vector<vector<int>> uses(noduri);
	for (int i = 0; i < k; i ++) {
		int g = inter(5 * i + 5 * noduri, 5 * (i + 1) + 5 * noduri, s);
		if (g == 31)
			continue;
		uses[g].push_back(i);
	}
	for (int i = 0; i < noduri; i ++) {
		if (!isLeaf[i])
			continue;
		int j = i;
		while (inter(5 * j, 5 * (j + 1), s) != j) {
			j = inter(5 * j, 5 * (j + 1), s);
			for (auto l : uses[j])
				uses[i].push_back(l);
		}
	}
	vector<bool> cooked(m);
	for (auto i : x) {
		cooked[i] = true;
		c[i] = 0;
	}
	for (int qs = 0; qs < q; qs ++) {
		int leaf = 0;
		for (int i = 0; i < n; i ++)
			if (tsort[i] == qs)
				leaf = i;
		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);
			}
		}
		for (auto i : uses[leaf]) {
			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> 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);
	}
}

/*
plan de actiune
prima data aflam ce muchii catre ce query-uri se duc
apoi rulam dijkstra-u pentru fiecare query

eu am nodurile reprezentate astfel incat frunza i este al i-lea cel mai mic t
*/ 

• Subtask 1: 0 / 100