oj.uz

Submission #1052086

# Submission time Handle Problem Language Result Execution time Memory
1052086 2024-08-10T11:45:51 Z fuad27 Spy 3 (JOI24_spy3) C++17
43 / 100
 73 ms 7600 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;
			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

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

# Verdict Execution time Memory Grader output
1 Partially correct 26 ms 6040 KB Partially correct
2 Correct 0 ms 776 KB Output is correct
3 Partially correct 54 ms 6604 KB Partially correct
4 Partially correct 55 ms 6116 KB Partially correct
5 Partially correct 64 ms 6700 KB Partially correct
6 Partially correct 57 ms 6548 KB Partially correct
7 Partially correct 55 ms 6688 KB Partially correct
8 Partially correct 60 ms 6496 KB Partially correct
9 Partially correct 52 ms 6140 KB Partially correct
10 Partially correct 24 ms 6376 KB Partially correct
11 Partially correct 57 ms 6692 KB Partially correct
12 Correct 56 ms 6516 KB Output is correct
13 Partially correct 57 ms 6600 KB Partially correct
14 Correct 56 ms 6684 KB Output is correct
15 Correct 56 ms 6340 KB Output is correct
16 Correct 20 ms 5772 KB Output is correct
17 Partially correct 71 ms 6164 KB Partially correct
18 Partially correct 67 ms 6124 KB Partially correct
19 Partially correct 57 ms 7460 KB Partially correct
20 Partially correct 49 ms 7452 KB Partially correct
21 Partially correct 57 ms 7516 KB Partially correct
22 Partially correct 65 ms 7528 KB Partially correct
23 Partially correct 48 ms 7476 KB Partially correct
24 Partially correct 63 ms 7496 KB Partially correct
25 Partially correct 71 ms 6008 KB Partially correct
26 Partially correct 72 ms 6028 KB Partially correct
27 Correct 0 ms 784 KB Output is correct
28 Correct 59 ms 6704 KB Output is correct
29 Partially correct 35 ms 4624 KB Partially correct
30 Correct 61 ms 6856 KB Output is correct
31 Partially correct 35 ms 6948 KB Partially correct
32 Partially correct 62 ms 6792 KB Partially correct
33 Correct 59 ms 6604 KB Output is correct
34 Correct 61 ms 7116 KB Output is correct
35 Correct 59 ms 6912 KB Output is correct
36 Partially correct 56 ms 7008 KB Partially correct
37 Partially correct 17 ms 3676 KB Partially correct
38 Partially correct 45 ms 4696 KB Partially correct
39 Partially correct 39 ms 4656 KB Partially correct
40 Partially correct 11 ms 4384 KB Partially correct
41 Partially correct 71 ms 7152 KB Partially correct
42 Partially correct 45 ms 7424 KB Partially correct
43 Correct 73 ms 7600 KB Output is correct
44 Partially correct 24 ms 7260 KB Partially correct
45 Partially correct 20 ms 3792 KB Partially correct
46 Partially correct 31 ms 4616 KB Partially correct
47 Correct 33 ms 4440 KB Output is correct
48 Correct 0 ms 776 KB Output is correct
49 Correct 0 ms 784 KB Output is correct
50 Partially correct 22 ms 5892 KB Partially correct
51 Partially correct 2 ms 1036 KB Partially correct
52 Correct 1 ms 784 KB Output is correct
53 Partially correct 25 ms 6052 KB Partially correct
54 Partially correct 17 ms 4112 KB Partially correct
55 Partially correct 37 ms 5020 KB Partially correct
56 Partially correct 38 ms 7016 KB Partially correct
57 Partially correct 56 ms 7152 KB Partially correct
58 Partially correct 48 ms 5816 KB Partially correct
59 Partially correct 65 ms 7396 KB Partially correct
60 Partially correct 60 ms 7056 KB Partially correct
61 Partially correct 68 ms 7348 KB Partially correct
62 Correct 62 ms 6780 KB Output is correct
63 Correct 66 ms 7416 KB Output is correct
64 Partially correct 20 ms 6344 KB Partially correct
65 Partially correct 31 ms 5304 KB Partially correct
66 Partially correct 33 ms 7408 KB Partially correct
67 Partially correct 35 ms 5324 KB Partially correct
68 Partially correct 36 ms 7476 KB Partially correct
69 Correct 0 ms 784 KB Output is correct
70 Correct 0 ms 784 KB Output is correct
71 Partially correct 0 ms 776 KB Partially correct
72 Partially correct 15 ms 3572 KB Partially correct
73 Partially correct 33 ms 4392 KB Partially correct
74 Partially correct 36 ms 4392 KB Partially correct
75 Partially correct 12 ms 4376 KB Partially correct
76 Correct 0 ms 784 KB Output is correct
77 Correct 52 ms 6628 KB Output is correct
78 Partially correct 48 ms 6584 KB Partially correct
79 Correct 55 ms 6648 KB Output is correct
80 Correct 0 ms 780 KB Output is correct
81 Partially correct 60 ms 6540 KB Partially correct
82 Partially correct 56 ms 6552 KB Partially correct
83 Correct 59 ms 6376 KB Output is correct