Submission #1036397

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1036397	2024-07-27T10:32:27 Z	Unforgettablepl	Spy 3 (JOI24_spy3)	C++17	23 / 100	61 ms	4908 KB

Aoi
Bitaro

#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;
}

#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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	44 ms	4652 KB	Partially correct
2	Correct	0 ms	776 KB	Output is correct
3	Partially correct	37 ms	3860 KB	Partially correct
4	Partially correct	30 ms	3828 KB	Partially correct
5	Partially correct	45 ms	3884 KB	Partially correct
6	Partially correct	44 ms	3760 KB	Partially correct
7	Partially correct	41 ms	3672 KB	Partially correct
8	Partially correct	34 ms	3812 KB	Partially correct
9	Partially correct	24 ms	3688 KB	Partially correct
10	Correct	17 ms	3828 KB	Output is correct
11	Partially correct	43 ms	3856 KB	Partially correct
12	Correct	35 ms	3744 KB	Output is correct
13	Partially correct	36 ms	4012 KB	Partially correct
14	Partially correct	42 ms	3840 KB	Partially correct
15	Correct	32 ms	3764 KB	Output is correct
16	Correct	14 ms	3456 KB	Output is correct
17	Partially correct	38 ms	3824 KB	Partially correct
18	Partially correct	40 ms	4412 KB	Partially correct
19	Partially correct	46 ms	4740 KB	Partially correct
20	Partially correct	38 ms	4728 KB	Partially correct
21	Partially correct	47 ms	4668 KB	Partially correct
22	Partially correct	46 ms	4720 KB	Partially correct
23	Partially correct	33 ms	4644 KB	Partially correct
24	Partially correct	48 ms	4740 KB	Partially correct
25	Partially correct	40 ms	4200 KB	Partially correct
26	Partially correct	42 ms	4208 KB	Partially correct
27	Correct	0 ms	776 KB	Output is correct
28	Partially correct	43 ms	3880 KB	Partially correct
29	Partially correct	20 ms	3088 KB	Partially correct
30	Correct	36 ms	4020 KB	Output is correct
31	Correct	23 ms	3840 KB	Output is correct
32	Partially correct	46 ms	4092 KB	Partially correct
33	Correct	42 ms	3844 KB	Output is correct
34	Partially correct	43 ms	4024 KB	Partially correct
35	Correct	37 ms	4060 KB	Output is correct
36	Partially correct	43 ms	4024 KB	Partially correct
37	Partially correct	10 ms	2544 KB	Partially correct
38	Partially correct	23 ms	3100 KB	Partially correct
39	Partially correct	19 ms	3072 KB	Partially correct
40	Correct	7 ms	2836 KB	Output is correct
41	Partially correct	57 ms	4812 KB	Partially correct
42	Partially correct	34 ms	4884 KB	Partially correct
43	Correct	47 ms	4896 KB	Output is correct
44	Correct	16 ms	4856 KB	Output is correct
45	Partially correct	12 ms	2560 KB	Partially correct
46	Partially correct	16 ms	2844 KB	Partially correct
47	Correct	18 ms	3040 KB	Output is correct
48	Correct	0 ms	784 KB	Output is correct
49	Correct	0 ms	784 KB	Output is correct
50	Partially correct	30 ms	4644 KB	Partially correct
51	Partially correct	2 ms	780 KB	Partially correct
52	Partially correct	1 ms	776 KB	Partially correct
53	Partially correct	49 ms	4688 KB	Partially correct
54	Partially correct	27 ms	3176 KB	Partially correct
55	Partially correct	35 ms	3412 KB	Partially correct
56	Partially correct	39 ms	4852 KB	Partially correct
57	Partially correct	53 ms	4804 KB	Partially correct
58	Partially correct	45 ms	3820 KB	Partially correct
59	Partially correct	61 ms	4836 KB	Partially correct
60	Partially correct	58 ms	4896 KB	Partially correct
61	Partially correct	57 ms	4868 KB	Partially correct
62	Partially correct	54 ms	4300 KB	Partially correct
63	Partially correct	56 ms	4816 KB	Partially correct
64	Correct	14 ms	3964 KB	Output is correct
65	Partially correct	23 ms	3872 KB	Partially correct
66	Partially correct	29 ms	4908 KB	Partially correct
67	Partially correct	25 ms	3864 KB	Partially correct
68	Partially correct	30 ms	4868 KB	Partially correct
69	Correct	0 ms	776 KB	Output is correct
70	Correct	0 ms	776 KB	Output is correct
71	Correct	0 ms	784 KB	Output is correct
72	Partially correct	12 ms	2336 KB	Partially correct
73	Partially correct	26 ms	2844 KB	Partially correct
74	Partially correct	28 ms	2844 KB	Partially correct
75	Correct	8 ms	3100 KB	Output is correct
76	Correct	0 ms	776 KB	Output is correct
77	Correct	46 ms	4020 KB	Output is correct
78	Partially correct	48 ms	3892 KB	Partially correct
79	Correct	45 ms	3836 KB	Output is correct
80	Correct	1 ms	776 KB	Output is correct
81	Partially correct	48 ms	3840 KB	Partially correct
82	Partially correct	47 ms	3860 KB	Partially correct
83	Partially correct	44 ms	3772 KB	Partially correct

Submission #1036397

Compilation message

Subtask #1 23.0 / 100.0

Subtask #1
23.0 / 100.0