제출 #1280946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280946		trideser	Spy 3 (JOI24_spy3)	C++20	0 / 100	111 ms	6308 KiB

Aoi

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

using namespace std;
#define ll long long
namespace {

int variable_example = 0;

int function_example(int a, int b) { return a + b; }

}	// namespace

std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
								std::vector<int> B, std::vector<long long> C,
								std::vector<int> T, std::vector<int> X) {
	vector<int> parent(N, -1);
	vector<ll> eee(N);
	vector<long long> dist(N, -1);
	priority_queue<tuple<ll, ll, ll, ll>> q;
	q.push(make_tuple(0, 0, -1, -1));
	vector<vector<tuple<ll, ll, ll>>> edges(N);
	for(int i = 0; i < M; i++) {
		ll a = A[i];
		ll b = B[i];
		ll c = C[i];
		edges[a].push_back(make_tuple(b, c, i));
		edges[b].push_back(make_tuple(a, c, i));
	}
	while(!q.empty()) {
		ll d, node, p, eg;
		tie(d, node, p, eg) = q.top();
		d *= -1;
		q.pop();
		if(dist[node] != -1) continue;
		dist[node] = d;
		parent[node] = p;
		eee[node] = eg;

		for(tuple<ll, ll, ll> e : edges[node]) {
			q.push(make_tuple(-(d + get<1>(e)), get<0>(e), node, get<2>(e)));
		}
	}
	map<int, int> mp;
	for(int i = 0; i < K; i++) {
		mp[X[i]] = i;
	}
	string s(9 * K + 9 * Q, '1');
	for(int i = 0; i < N; i++) {
		if(mp.find(eee[i]) == mp.end()) continue;
		ll current = parent[i];
		while(current != -1) {
			if(mp.find(eee[current]) != mp.end()) {
				for(int j = 0; j < 9; j++) {
					int r = mp[eee[i]];
					s[9 * r + j] = (char) ((eee[current] >> j) & 1) + 48;
				}
				break;
			}
			current = parent[current];
		}
	}
	for(int i = 0; i < Q; i++) {
		ll current = T[i];
		while(current != -1) {
			if(mp.find(eee[current]) != mp.end()) {
				for(int j = 0; j < 9; j++) {
					s[9 * K + 9 * i + j] = (char) ((eee[current] >> j) & 1) + 48;
				}
				break;
			}
			current = parent[current];
		}
	}

//	cout << s << "\n";
	return s;
}

Bitaro

#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace {

int variable_example = 0;

int function_example(int a, int b) { return a + b; }


}	// namespace

void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B,
						std::vector<long long> C, std::vector<int> T, std::vector<int> X,
						std::string s) {
	vector<ll> tree_parent(K);
	for(int i = 0; i < K; i++) {
		int a = 0;
		for(int j = 0; j < 9; j++) {
			a += (s[9 * i + j] - 48) << j;
		}
		if(a == 511) a = -1;
		tree_parent[i] = a;
	}
	/*cout << "\n";
	for(int a : tree_parent) cout << a << " ";
	cout << " <-tree\n";*/
	for (int i = 0; i < Q; i++) {
		vector<ll> newC = C;
		int a = 0;
		for(int j = 0; j < 9; j++) {
			a += (s[9 * (i + K) + j] - 48) << j;
		}
		if(a == 511) a = -1;
		//cout << "\n" << a << "\n";
		for(int j = 0; j < K; j++) {
			newC[X[j]] = 0x7fffffffffff;
		}
		while(a != -1) {
			newC[X[a]] = 0;
			a = tree_parent[a];
		}

		vector<int> parent(N, -1);
		vector<ll> eee(N);
		vector<long long> dist(N, -1);
		priority_queue<tuple<ll, ll, ll, ll>> q;
		q.push(make_tuple(0, 0, -1, -1));
		vector<vector<tuple<ll, ll, ll>>> edges(N);
		for(int i = 0; i < M; i++) {
			ll a = A[i];
			ll b = B[i];
			ll c = newC[i];
			edges[a].push_back(make_tuple(b, c, i));
			edges[b].push_back(make_tuple(a, c, i));
		}
		while(!q.empty()) {
			ll d, node, p, eg;
			tie(d, node, p, eg) = q.top();
			d *= -1;
			q.pop();
			if(dist[node] != -1) continue;
			dist[node] = d;
			parent[node] = p;
			eee[node] = eg;

			for(tuple<ll, ll, ll> e : edges[node]) {
				q.push(make_tuple(-(d + get<1>(e)), get<0>(e), node, get<2>(e)));
			}
		}
		vector<int> v;
		int node = T[i];
		while(node != -1) {
			if(eee[node] != -1) v.push_back(eee[node]);
			node = parent[node];
		}
		reverse(v.begin(), v.end());
		answer(v);
	}
}

• Subtask 1: 0 / 100