oj.uz

Submission #1052084

# Submission time Handle Problem Language Result Execution time Memory
1052084 2024-08-10T11:45:04 Z fuad27 Spy 3 (JOI24_spy3) C++17
0 / 100
 1000 ms 7540 KB 
#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;
}

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

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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 28 ms 5968 KB Partially correct
2 Correct 0 ms 784 KB Output is correct
3 Partially correct 54 ms 6604 KB Partially correct
4 Partially correct 56 ms 6336 KB Partially correct
5 Partially correct 59 ms 6624 KB Partially correct
6 Partially correct 59 ms 6520 KB Partially correct
7 Partially correct 55 ms 6620 KB Partially correct
8 Partially correct 55 ms 6524 KB Partially correct
9 Partially correct 53 ms 6184 KB Partially correct
10 Partially correct 25 ms 6188 KB Partially correct
11 Partially correct 55 ms 6652 KB Partially correct
12 Correct 61 ms 6516 KB Output is correct
13 Partially correct 57 ms 6688 KB Partially correct
14 Correct 56 ms 6600 KB Output is correct
15 Correct 56 ms 6348 KB Output is correct
16 Correct 19 ms 5928 KB Output is correct
17 Partially correct 67 ms 6128 KB Partially correct
18 Partially correct 68 ms 6176 KB Partially correct
19 Partially correct 56 ms 7456 KB Partially correct
20 Partially correct 46 ms 7468 KB Partially correct
21 Partially correct 56 ms 7504 KB Partially correct
22 Execution timed out 1049 ms 7540 KB Time limit exceeded
23 Halted 0 ms 0 KB -