Submission #1036397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036397		Unforgettablepl	Spy 3 (JOI24_spy3)	C++17	23 / 100	61 ms	4908 KiB

Aoi

#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

}

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<int> forgotten(M+1,K);
	for(int i=0;i<K;i++)forgotten[X[i]]=i;
	vector<pair<int,int>> paredge(N);
	vector<vector<pair<int,int>>> adj(N);
	for(int i=0;i<M;i++){
		adj[A[i]].emplace_back(B[i],i);
		adj[B[i]].emplace_back(A[i],i);
	}
	priority_queue<tuple<long long,int,int>> pq;
	vector<bool> visited(N);
	pq.emplace(0,0,M);
	while(!pq.empty()){
		auto [dist,curr,pedge] = pq.top();pq.pop();dist=-dist;
		if(visited[curr])continue;
		visited[curr]=true;
		if(A[pedge]==curr)paredge[curr]={B[pedge],forgotten[pedge]};
		else paredge[curr]={A[pedge],forgotten[pedge]};
		for(auto[v,idx]:adj[curr])if(!visited[v]){
			pq.emplace(-dist-C[idx],v,idx);
		}
	}
	string res;
	for(int i=0;i<Q;i++){
		for(int j=0;j<K;j++)res.insert(res.end(),'0');
		int curr = T[i];
		while(curr){
			if(paredge[curr].second!=K)res[i*K+paredge[curr].second]='1';
			curr = paredge[curr].first;
		}
	}
	return res;
}

Bitaro

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

const long long INF = 1e13;

namespace {

}

void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B,
			vector<long long> C, vector<int> T, vector<int> X,
			string s) {
	vector<pair<int,int>> paredge(N);
	vector<vector<pair<int,int>>> adj(N);
	for(int i=0;i<M;i++){
		adj[A[i]].emplace_back(B[i],i);
		adj[B[i]].emplace_back(A[i],i);
	}
	for(int sce=0;sce<Q;sce++){
		for(int i=0;i<K;i++){
			if(s[sce*K+i]=='1')C[X[i]]=0;
			else C[X[i]]=INF;
		}
		priority_queue<tuple<long long,int,int>> pq;
		vector<bool> visited(N);
		pq.emplace(0,0,M);
		while(!pq.empty()){
			auto [dist,curr,pedge] = pq.top();pq.pop();dist=-dist;
			if(visited[curr])continue;
			visited[curr]=true;
			if(A[pedge]==curr)paredge[curr]={B[pedge],pedge};
			else paredge[curr]={A[pedge],pedge};
			for(auto[v,idx]:adj[curr])if(!visited[v]){
				pq.emplace(-dist-C[idx],v,idx);
			}
		}
		vector<int> ans;
		int curr = T[sce];
		while(curr){
			ans.emplace_back(paredge[curr].second);
			curr = paredge[curr].first;
		}
		reverse(ans.begin(),ans.end());
		answer(ans);
	}
}

• Subtask 1: 23 / 100