oj.uz

답안 #1039881

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039881 2024-07-31T11:21:42 Z Unforgettablepl Spy 3 (JOI24_spy3) C++17
0 / 100
 46 ms 4756 KB 
#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;
}

#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

# 결과 실행 시간 메모리 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 -