Submission #1039881

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1039881	2024-07-31T11:21:42 Z	Unforgettablepl	Spy 3 (JOI24_spy3)	C++17	0 / 100	46 ms	4756 KB

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);
	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

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	4756 KB	Output is correct
2	Correct	0 ms	776 KB	Output is correct
3	Correct	40 ms	4052 KB	Output is correct
4	Correct	31 ms	3864 KB	Output is correct
5	Correct	43 ms	4048 KB	Output is correct
6	Correct	38 ms	4116 KB	Output is correct
7	Correct	41 ms	4108 KB	Output is correct
8	Correct	40 ms	4272 KB	Output is correct
9	Correct	27 ms	3928 KB	Output is correct
10	Correct	17 ms	3764 KB	Output is correct
11	Correct	41 ms	4252 KB	Output is correct
12	Correct	34 ms	4112 KB	Output is correct
13	Correct	35 ms	4040 KB	Output is correct
14	Correct	46 ms	4016 KB	Output is correct
15	Incorrect	36 ms	4072 KB	Wrong Answer [5]
16	Halted	0 ms	0 KB	-