제출 #1280930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280930		trideser	Spy 3 (JOI24_spy3)	C++20	23 / 100	132 ms	6320 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(Q * K, '0');
	for(int i = 0; i < Q; i++) {
		ll current = T[i];
		while(current != -1) {
			if(mp.find(eee[current]) != mp.end()) {
				s[i * K + mp[eee[current]]] = '1';
			}
			current = parent[current];
		}
	}
	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) {
	for (int i = 0; i < Q; i++) {
		vector<ll> newC = C;
		for(int j = 0; j < K; j++) {
			newC[X[j]] = s[K * i + j] == '1' ? 0 : 0x7fffffffffff;
		}
		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: 23 / 100