Submission #1052086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052086		fuad27	Spy 3 (JOI24_spy3)	C++17	43 / 100	73 ms	7600 KiB

Aoi

#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
                std::vector<int> B, std::vector<long long> C,
                std::vector<int> T, std::vector<int> X) {
	vector<vector<int>> g(N);
	for(int i = 0;i<M;i++) {
		g[A[i]].push_back(i);
		g[B[i]].push_back(i);
	}
	vector<long long> dist(N, (long long)1e18);
	vector<int> pr(N, -1);
	dist[0] = 0;
	priority_queue<pair<long long, int>> pq;
	pq.push({0, 0});
	vector<int> bad_edge(M);
	for(auto i=0;i<X.size();i++)bad_edge[X[i]]=i+1;
	vector<bool> vis(N);
	while(pq.size()) {
		int at = pq.top().second;
		pq.pop();
		if(vis[at])continue;
		vis[at]=1;
		for(int idx:g[at]) {
			int to = (at^A[idx]^B[idx]);
			long long w = C[idx];
			if(dist[to] > dist[at] + w) {
				dist[to] = dist[at] + w;
				pr[to] = idx;
				pq.push(pair<long long, int>(-dist[to], to));
			}
		}
	}
	vector<int> par_final(K+Q);
	for(int iii = 0;iii<Q;iii++) {
		int cur = pr[T[iii]];
		int prev = iii+K;
		bool fl=0;
		while(1) {
			if(cur == -1 or bad_edge[cur]) {
				if(cur != -1) {
					par_final[prev] = bad_edge[cur]-1;
				}
				else {
					par_final[prev] = -1;
				}
				prev = bad_edge[cur]-1;
			}
			if(cur == -1)break;
			if(dist[A[cur]] < dist[B[cur]]) {
				cur = pr[A[cur]];		
			}
			else cur = pr[B[cur]];
		}
	}
	string res = "";
	for(int i = 0;i<Q+K;i++) {
//		cout << i << " " << par_final[i] << endl;
		par_final[i]++;
		for(int j = 0;j<9;j++) {
			if(par_final[i]&(1<<j))res+="1";
			else res+="0";
		}
	}
//	cout << res.size() << endl;
	return res;
}

Bitaro

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

void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B,
            std::vector<long long> C, std::vector<int> T, std::vector<int> X,
            std::string s) {
	vector<int> par(K+Q);
	for(int i = 0;i<K+Q;i++) {
		for(int j = 0;j<9;j++) {
			if(s[i*9 + j] == '1')par[i]|=(1<<j);
		}
		par[i]--;
	}
	map<pair<int,int>, int> mp;
	for(int i = 0;i<M;i++) {
		mp[{A[i], B[i]}]=i;
		mp[{B[i], A[i]}]=i;
	}
	for(int st = 0;st<Q;st++) {
		for(int idx:X) {
			C[idx] = 1e18;
		}
		{
			int at = par[st+K];
			while(at!=-1) {
				C[X[at]] = 0;
				at = par[at];
			}
		}
		vector<vector<pair<int, long long>>> g(N);
		for(int i = 0;i<M;i++) {
			g[A[i]].push_back({B[i], C[i]});
			g[B[i]].push_back({A[i], C[i]});
		}
		priority_queue<pair<long long, int>> pq;
		vector<long long> dist(N, 1e18);
		vector<int> pr(N, -1);
		vector<bool> vis(N,0);
		dist[0] =0 ;
		pq.push({0, 0});
		while(pq.size()) {
			int at = pq.top().second;
			pq.pop();
			if(vis[at])continue;
			vis[at]=1;
			for(auto [to,w]:g[at]) {
				if(dist[to] > dist[at] + w) {
					pr[to] = at;
					dist[to] = dist[at]+w;
					pq.push({-dist[to], to});
				}
			}
		}
		int cur=T[st];
		vector<int> ans;
		while(pr[cur]!=-1) {
			ans.push_back(mp[{pr[cur], cur}]);
			cur=pr[cur];
		}
		reverse(ans.begin(), ans.end());
		answer(ans);
	}
}

Compilation message (stderr)

Aoi.cpp: In function 'std::string aoi(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>)':
Aoi.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(auto i=0;i<X.size();i++)bad_edge[X[i]]=i+1;
      |               ~^~~~~~~~~
Aoi.cpp:39:8: warning: unused variable 'fl' [-Wunused-variable]
   39 |   bool fl=0;
      |        ^~

• Subtask 1: 43 / 100