Submission #1039886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039886		Unforgettablepl	Spy 3 (JOI24_spy3)	C++17	100 / 100	52 ms	5092 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(pedge==M){}
		else 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);
		}
	}
	vector<int> firstuseby(300,Q);
	vector<int> lastedgeused(Q,K);
	string res;
	for(int i=0;i<Q;i++){
		int curr = T[i];
		while(curr){
			if(paredge[curr].second!=K){
				if(firstuseby[paredge[curr].second]==Q)firstuseby[paredge[curr].second]=i;
				else {lastedgeused[i]=paredge[curr].second;break;}
			}
			curr = paredge[curr].first;
		}
	}
	for(int i=1;i<Q;i++){
		for(int bit=0;bit<9;bit++)if(lastedgeused[i]&(1<<bit))res.insert(res.end(),'1');
								  else res.insert(res.end(),'0');
	}
	for(int i=0;i<K;i+=2){
		int poss = firstuseby[i]*17+firstuseby[i+1];
		for(int bit=0;bit<9;bit++)if(poss&(1<<bit))res.insert(res.end(),'1');
								  else res.insert(res.end(),'0');	
	}
	return res;
}

Bitaro

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

const long long INF = 1e18;

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>> finalparedge(N);
	vector<vector<pair<int,int>>> adj(N);
	vector<int> isForgotten(M,K);
	for(int i=0;i<K;i++)isForgotten[X[i]]=i;
	for(int i=0;i<M;i++){
		adj[A[i]].emplace_back(B[i],i);
		adj[B[i]].emplace_back(A[i],i);
	}
	int ptr = 0;
	auto read = [&](){
		return s[ptr++]=='1';
	};
	vector<int> firstuseby(300);
	vector<int> lastedgeused(Q);
	lastedgeused[0]=K;
	for(int i=1;i<Q;i++){
		for(int bit=0;bit<9;bit++)
			if(read())
				lastedgeused[i]|=(1<<bit);
	}
	for(int i=0;i<K;i+=2){
		int poss = 0;
		for(int bit=0;bit<9;bit++)if(read())poss|=(1<<bit);	
		firstuseby[i]=poss/17;
		firstuseby[i+1]=poss%17;
	}
	for(int sce=0;sce<Q;sce++){
		vector<pair<int,int>> paredge(N);
		vector<bool> included(K);
		if(lastedgeused[sce]!=K){
			included[lastedgeused[sce]]=true;
			int curr = A[X[lastedgeused[sce]]];
			while(curr){
				if(isForgotten[finalparedge[curr].second]!=K)included[isForgotten[finalparedge[curr].second]]=true;
				curr = finalparedge[curr].first;
			}
		}
		for(int i=0;i<K;i++)if(firstuseby[i]==sce)included[i]=true;
		for(int i=0;i<K;i++){
			if(included[i])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(pedge==M){}
			else 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){
			finalparedge[curr] = paredge[curr];
			ans.emplace_back(paredge[curr].second);
			curr = paredge[curr].first;
		}
		reverse(ans.begin(),ans.end());
		answer(ans);
	}
}

• Subtask 1: 100 / 100