oj.uz

Submission #1039457

# Submission time Handle Problem Language Result Execution time Memory
1039457 2024-07-30T22:51:39 Z Trent Spy 3 (JOI24_spy3) C++17
92 / 100
 245 ms 8272 KB 
#include "Aoi.h"
#include "bits/stdc++.h"

using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()

namespace {
	typedef long long ll;
	struct pii{int a, b;};
	bool operator <(pii a, pii b) {return a.a < b.a || a.a == b.a && a.b < b.b;}
	struct edge{int t; ll len;};
	struct node{int i; ll to;};
	bool operator <(node a, node b){
		return a.to > b.to;
	}
	const ll INF = 1e17;
	string toBinNumber(int x, int bits) {
		string ret;
		forR(i, bits) {
			ret.push_back(x % 2 == 0 ? '0' : '1');
			x /= 2;
		}
		reverse(all(ret));
		assert(x == 0);
		return ret;
	}
}

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<edge>> adj(N);
	map<pii, int> xi;
	forR(i, M){
		adj[A[i]].push_back({B[i], C[i]});
		adj[B[i]].push_back({A[i], C[i]});
	}
	forR(i, K){
		xi.insert({{A[X[i]], B[X[i]]}, i});
		xi.insert({{B[X[i]], A[X[i]]}, i});
	}

	vector<int> indIn(K, Q);
	vector<int> lOld(Q);
	// dijkstra
	forR(i, Q){
		vector<ll> dis(N, INF);
		vector<bool> vis(N);
		vector<int> pre(N);
		priority_queue<node> dij;
		dij.push({0, 0});
		dis[0] = 0;
		while(!dij.empty()){
			auto [cur, len] = dij.top();
			dij.pop();
			if(!vis[cur]){
				vis[cur] = true;
				for(auto [to, el] : adj[cur]){
					if(len + el < dis[to]){
						dis[to] = len + el;
						pre[to] = cur;
						dij.push({to, dis[to]});
					}
				}
			}
		}

		vector<int> pth;
		for(int j = T[i]; j != 0; j = pre[j]) pth.push_back(j);
		pth.push_back(0);
		reverse(all(pth));
		int lasUsed = -1;
		forR(j, (int) pth.size() - 1) {
			if(xi.count({pth[j], pth[j+1]})) {
				int eInd = xi[{pth[j], pth[j+1]}];
				if(indIn[eInd] == Q) {
					indIn[eInd] = i;
				} else {
					lasUsed = eInd;
				}
			}
		}
		lOld[i] = lasUsed == -1 ? -1 : lasUsed;
	}

	for(int i : indIn) cerr << i << ' ';
	cerr << '\n';
	for(int i : lOld) cerr << i << ' ';
	cerr << '\n';
	string ret;
	for(int i : indIn) {
		ret += toBinNumber(i, 5);
	}
	for(int i : lOld) {
		ret += toBinNumber(i + 1, 9);
	}
	cerr << ret << '\n';
	return ret;
}

#include "Bitaro.h"
#include "bits/stdc++.h"

using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()

namespace {
	typedef long long ll;
	struct pii{int a, b;};
	bool operator <(pii a, pii b) {return a.a < b.a || a.a == b.a && a.b < b.b;}
	struct edge{int t, ind; ll len;};
	struct node{int i; ll to;};
	bool operator <(node a, node b){
		return a.to > b.to;
	}
	const ll INF = 1e17;
	int fromBinNumber(string s) {
		int ret = 0;
		for(char i : s) ret = ret * 2 + (i == '0' ? 0 : 1);
		return ret;
	}
}

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) {
	map<pii, int> xi;
	forR(i, K){
		xi.insert({{A[X[i]], B[X[i]]}, i});
		xi.insert({{B[X[i]], A[X[i]]}, i});
	}

	vector<vector<edge>> adj(N);
	map<pii, int> ei;
	forR(i, M){
		int cxi = -1;
		if(xi.count({A[i], B[i]})){
			cxi = xi[{A[i], B[i]}];
		}
		adj[A[i]].push_back({B[i], cxi, C[i]});
		adj[B[i]].push_back({A[i], cxi, C[i]});
		ei[{A[i], B[i]}] = i;
		ei[{B[i], A[i]}] = i;
	}

	vector<int> indIn;
	vector<int> lOld;
	int ci=0;
	forR(i, K) {
		indIn.push_back(fromBinNumber(s.substr(ci, 5)));
		ci += 5;
	}
	forR(i, Q) {
		lOld.push_back(fromBinNumber(s.substr(ci, 9)) - 1);
		ci += 9;
	}
	for(int i : indIn) cerr << i << ' ';
	cerr << '\n';
	for(int i : lOld) cerr << i << ' ';
	cerr << '\n';

	vector<bool> solid(N, false);
	vector<int> sPre(N);
	forR(i, Q){
		vector<ll> dis(N, INF);
		vector<bool> vis(N);
		vector<int> pre(N);
		int stNode;
		if(lOld[i] == -1) stNode = 0;
		else {
			int eInd = X[lOld[i]];
			stNode = sPre[A[eInd]] == B[eInd] ? A[eInd] : B[eInd];
			assert(solid[stNode]);
		}

		priority_queue<node> dij;
		dij.push({stNode, 0});
		dis[stNode] = 0;
		while(!dij.empty()){
			auto [cur, len] = dij.top();
			dij.pop();
			if(!vis[cur]){
				vis[cur] = true;
				for(auto [to, ind, el] : adj[cur]){
					if(ind == -1 || indIn[ind] == i){
						el = ind == -1 ? el : 0;
						if(len + el < dis[to]){
							dis[to] = len + el;
							pre[to] = cur;
							dij.push({to, dis[to]});
						}
					}
				}	
			}
		}
		vector<int> pth;
		for(int j = T[i]; j != stNode; j = pre[j]) pth.push_back(j);
		for(int j = stNode; j != 0; j = sPre[j]) pth.push_back(j);
		pth.push_back(0);
		reverse(all(pth));
		for(int j : pth) cerr << j << ' ';
		cerr << '\n';
		REP(j, 1, pth.size()) {
			solid[pth[j]] = true;
			sPre[pth[j]] = pth[j-1];
		}
		vector<int> ret;
		forR(j, (int) pth.size() - 1) ret.push_back(ei[{pth[j], pth[j+1]}]);
		answer(ret);
	}
}

Compilation message

Aoi.cpp: In function 'bool {anonymous}::operator<({anonymous}::pii, {anonymous}::pii)':
Aoi.cpp:12:64: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   12 |  bool operator <(pii a, pii b) {return a.a < b.a || a.a == b.a && a.b < b.b;}
      |                                                     ~~~~~~~~~~~^~~~~~~~~~~~

Bitaro.cpp: In function 'bool {anonymous}::operator<({anonymous}::pii, {anonymous}::pii)':
Bitaro.cpp:12:64: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   12 |  bool operator <(pii a, pii b) {return a.a < b.a || a.a == b.a && a.b < b.b;}
      |                                                     ~~~~~~~~~~~^~~~~~~~~~~~
Bitaro.cpp: In function 'void bitaro(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::string)':
Bitaro.cpp:6:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define REP(i, a, b) for(int i = (a); i < (b); ++i)
      |                                         ^
Bitaro.cpp:105:3: note: in expansion of macro 'REP'
  105 |   REP(j, 1, pth.size()) {
      |   ^~~

Subtask #1
92.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6392 KB Output is correct
2 Correct 0 ms 772 KB Output is correct
3 Partially correct 48 ms 7220 KB Partially correct
4 Partially correct 167 ms 6832 KB Partially correct
5 Partially correct 54 ms 7144 KB Partially correct
6 Partially correct 82 ms 7088 KB Partially correct
7 Partially correct 44 ms 7068 KB Partially correct
8 Partially correct 70 ms 6976 KB Partially correct
9 Partially correct 138 ms 6864 KB Partially correct
10 Correct 41 ms 6704 KB Output is correct
11 Partially correct 46 ms 7124 KB Partially correct
12 Correct 95 ms 7008 KB Output is correct
13 Correct 55 ms 7024 KB Output is correct
14 Correct 42 ms 6840 KB Output is correct
15 Correct 122 ms 6872 KB Output is correct
16 Correct 30 ms 6624 KB Output is correct
17 Partially correct 245 ms 7108 KB Partially correct
18 Partially correct 243 ms 7132 KB Partially correct
19 Partially correct 58 ms 8104 KB Partially correct
20 Partially correct 47 ms 8096 KB Partially correct
21 Partially correct 61 ms 8076 KB Partially correct
22 Partially correct 74 ms 8156 KB Partially correct
23 Partially correct 60 ms 8096 KB Partially correct
24 Partially correct 87 ms 8068 KB Partially correct
25 Partially correct 204 ms 7164 KB Partially correct
26 Partially correct 226 ms 7268 KB Partially correct
27 Correct 1 ms 776 KB Output is correct
28 Correct 69 ms 7268 KB Output is correct
29 Partially correct 102 ms 5036 KB Partially correct
30 Correct 90 ms 7452 KB Output is correct
31 Correct 41 ms 7276 KB Output is correct
32 Correct 59 ms 7384 KB Output is correct
33 Correct 59 ms 7172 KB Output is correct
34 Correct 108 ms 7712 KB Output is correct
35 Correct 91 ms 7428 KB Output is correct
36 Correct 91 ms 7716 KB Output is correct
37 Partially correct 70 ms 4080 KB Partially correct
38 Partially correct 186 ms 5440 KB Partially correct
39 Correct 179 ms 5440 KB Output is correct
40 Correct 27 ms 4648 KB Output is correct
41 Partially correct 67 ms 7792 KB Partially correct
42 Partially correct 60 ms 7972 KB Partially correct
43 Correct 120 ms 8092 KB Output is correct
44 Correct 33 ms 7760 KB Output is correct
45 Partially correct 78 ms 4112 KB Partially correct
46 Partially correct 96 ms 4916 KB Partially correct
47 Correct 104 ms 4880 KB Output is correct
48 Correct 0 ms 776 KB Output is correct
49 Correct 0 ms 776 KB Output is correct
50 Partially correct 22 ms 6112 KB Partially correct
51 Partially correct 4 ms 1156 KB Partially correct
52 Correct 2 ms 776 KB Output is correct
53 Correct 28 ms 6440 KB Output is correct
54 Partially correct 19 ms 4360 KB Partially correct
55 Correct 39 ms 5080 KB Output is correct
56 Partially correct 38 ms 7348 KB Partially correct
57 Partially correct 55 ms 7712 KB Partially correct
58 Partially correct 41 ms 6160 KB Partially correct
59 Correct 60 ms 7948 KB Output is correct
60 Partially correct 52 ms 7760 KB Partially correct
61 Correct 63 ms 7860 KB Output is correct
62 Correct 60 ms 7424 KB Output is correct
63 Correct 60 ms 8012 KB Output is correct
64 Correct 24 ms 6840 KB Output is correct
65 Correct 38 ms 5416 KB Output is correct
66 Correct 34 ms 8272 KB Output is correct
67 Correct 38 ms 5428 KB Output is correct
68 Correct 37 ms 8152 KB Output is correct
69 Correct 0 ms 784 KB Output is correct
70 Correct 0 ms 784 KB Output is correct
71 Correct 2 ms 784 KB Output is correct
72 Partially correct 16 ms 3828 KB Partially correct
73 Partially correct 28 ms 4632 KB Partially correct
74 Partially correct 30 ms 4592 KB Partially correct
75 Correct 14 ms 4528 KB Output is correct
76 Correct 0 ms 776 KB Output is correct
77 Correct 38 ms 7100 KB Output is correct
78 Partially correct 39 ms 7096 KB Partially correct
79 Correct 48 ms 7276 KB Output is correct
80 Correct 0 ms 784 KB Output is correct
81 Correct 50 ms 6972 KB Output is correct
82 Partially correct 51 ms 7108 KB Partially correct
83 Correct 55 ms 6836 KB Output is correct