Submission #1039870

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1039870	2024-07-31T11:12:35 Z	Unforgettablepl	Spy 3 (JOI24_spy3)	C++17	0 / 100	46 ms	4776 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 = 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>> 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	46 ms	4776 KB	Output is correct
2	Correct	0 ms	780 KB	Output is correct
3	Correct	37 ms	4024 KB	Output is correct
4	Correct	29 ms	3940 KB	Output is correct
5	Correct	43 ms	4092 KB	Output is correct
6	Correct	39 ms	4116 KB	Output is correct
7	Correct	40 ms	4068 KB	Output is correct
8	Correct	36 ms	4024 KB	Output is correct
9	Correct	24 ms	3768 KB	Output is correct
10	Correct	16 ms	3948 KB	Output is correct
11	Correct	39 ms	3856 KB	Output is correct
12	Correct	31 ms	4016 KB	Output is correct
13	Correct	35 ms	4116 KB	Output is correct
14	Correct	40 ms	4020 KB	Output is correct
15	Incorrect	26 ms	4064 KB	Wrong Answer [5]
16	Halted	0 ms	0 KB	-