oj.uz

Submission #1039480

# Submission time Handle Problem Language Result Execution time Memory
1039480 2024-07-30T23:59:09 Z Trent Spy 3 (JOI24_spy3) C++17
72 / 100
 270 ms 8424 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;
	}
    set<int> sUsedX;
    for(int i : lOld) if(i != -1) {
        sUsedX.insert(i);
    }
    vector<int> usedX;
    for(int i : sUsedX) usedX.push_back(i);
 
	for(int i : indIn) cerr << i << ' ';
	cerr << '\n';
	for(int i : lOld) cerr << i << ' ';
	cerr << '\n';

	string ret;
	forR(i, indIn.size()) {
        if(!sUsedX.count(i)) ret += toBinNumber(indIn[i], 6);
        else {
            assert(indIn[i] + 1 < Q);
            ret += toBinNumber(indIn[i] + Q + 1, 6);
        }
	}
	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;
    vector<int> usedX;
	int ci=0;
	forR(i, K) {
        int val = fromBinNumber(s.substr(ci, 6));
        if(val >= Q + 1) {
            usedX.push_back(i);
            indIn.push_back(val - Q - 1);
        } else {
            indIn.push_back(val);
        }
		ci += 6;
	}
	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;}
      |                                                     ~~~~~~~~~~~^~~~~~~~~~~~
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:5:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define forR(i, x) for(int i = 0; i < (x); ++i)
      |                                     ^
Aoi.cpp:100:2: note: in expansion of macro 'forR'
  100 |  forR(i, indIn.size()) {
      |  ^~~~

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:112:3: note: in expansion of macro 'REP'
  112 |   REP(j, 1, pth.size()) {
      |   ^~~

Subtask #1
72.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 26 ms 6328 KB Partially correct
2 Correct 0 ms 776 KB Output is correct
3 Partially correct 57 ms 7016 KB Partially correct
4 Partially correct 173 ms 6832 KB Partially correct
5 Partially correct 56 ms 7272 KB Partially correct
6 Partially correct 77 ms 7084 KB Partially correct
7 Partially correct 50 ms 6836 KB Partially correct
8 Partially correct 75 ms 7208 KB Partially correct
9 Partially correct 140 ms 6780 KB Partially correct
10 Partially correct 40 ms 6640 KB Partially correct
11 Partially correct 50 ms 7048 KB Partially correct
12 Correct 87 ms 7084 KB Output is correct
13 Correct 61 ms 6836 KB Output is correct
14 Correct 49 ms 6928 KB Output is correct
15 Correct 127 ms 6828 KB Output is correct
16 Correct 32 ms 6508 KB Output is correct
17 Partially correct 270 ms 7124 KB Partially correct
18 Partially correct 266 ms 7180 KB Partially correct
19 Partially correct 63 ms 8124 KB Partially correct
20 Partially correct 54 ms 8092 KB Partially correct
21 Partially correct 63 ms 8180 KB Partially correct
22 Partially correct 80 ms 8160 KB Partially correct
23 Partially correct 58 ms 8088 KB Partially correct
24 Partially correct 82 ms 8140 KB Partially correct
25 Partially correct 209 ms 7176 KB Partially correct
26 Partially correct 223 ms 7076 KB Partially correct
27 Correct 2 ms 784 KB Output is correct
28 Correct 63 ms 7352 KB Output is correct
29 Partially correct 82 ms 5356 KB Partially correct
30 Correct 88 ms 7348 KB Output is correct
31 Correct 43 ms 7412 KB Output is correct
32 Correct 62 ms 7352 KB Output is correct
33 Correct 62 ms 7068 KB Output is correct
34 Correct 109 ms 7640 KB Output is correct
35 Correct 84 ms 7624 KB Output is correct
36 Partially correct 81 ms 7724 KB Partially correct
37 Partially correct 69 ms 3972 KB Partially correct
38 Partially correct 192 ms 5432 KB Partially correct
39 Correct 186 ms 5420 KB Output is correct
40 Correct 30 ms 4664 KB Output is correct
41 Partially correct 76 ms 7816 KB Partially correct
42 Partially correct 53 ms 8024 KB Partially correct
43 Correct 102 ms 8044 KB Output is correct
44 Correct 32 ms 7888 KB Output is correct
45 Partially correct 82 ms 4016 KB Partially correct
46 Partially correct 91 ms 5004 KB Partially correct
47 Correct 108 ms 4944 KB Output is correct
48 Correct 1 ms 776 KB Output is correct
49 Correct 1 ms 776 KB Output is correct
50 Partially correct 24 ms 6324 KB Partially correct
51 Partially correct 3 ms 1164 KB Partially correct
52 Correct 2 ms 784 KB Output is correct
53 Partially correct 31 ms 6356 KB Partially correct
54 Partially correct 18 ms 4356 KB Partially correct
55 Correct 41 ms 5124 KB Output is correct
56 Partially correct 39 ms 7376 KB Partially correct
57 Partially correct 54 ms 7836 KB Partially correct
58 Partially correct 46 ms 6068 KB Partially correct
59 Correct 65 ms 8200 KB Output is correct
60 Partially correct 53 ms 7768 KB Partially correct
61 Partially correct 69 ms 7900 KB Partially correct
62 Correct 65 ms 7388 KB Output is correct
63 Correct 69 ms 7920 KB Output is correct
64 Correct 27 ms 6900 KB Output is correct
65 Correct 39 ms 5408 KB Output is correct
66 Partially correct 40 ms 8424 KB Partially correct
67 Partially correct 39 ms 5424 KB Partially correct
68 Partially correct 38 ms 8200 KB Partially correct
69 Correct 0 ms 776 KB Output is correct
70 Correct 0 ms 776 KB Output is correct
71 Correct 2 ms 776 KB Output is correct
72 Partially correct 17 ms 3852 KB Partially correct
73 Partially correct 31 ms 4620 KB Partially correct
74 Partially correct 32 ms 4784 KB Partially correct
75 Correct 16 ms 4628 KB Output is correct
76 Correct 0 ms 784 KB Output is correct
77 Correct 46 ms 7308 KB Output is correct
78 Partially correct 49 ms 7216 KB Partially correct
79 Correct 53 ms 7064 KB Output is correct
80 Correct 1 ms 776 KB Output is correct
81 Correct 53 ms 7004 KB Output is correct
82 Partially correct 47 ms 6984 KB Partially correct
83 Correct 59 ms 6836 KB Output is correct