| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1039483 |
2024-07-31T00:05:35 Z |
Trent |
Spy 3 (JOI24_spy3) |
C++17 |
|
248 ms |
8224 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';
for(int i : usedX) cerr << i << ' ';
cerr << '\n';
string ret;
forR(i, indIn.size()) {
if(!sUsedX.count(i)) ret += toBinNumber(indIn[i], 5);
else {
assert(indIn[i] + 1 < Q);
ret += toBinNumber(indIn[i] + Q + 1, 5);
}
}
for(int i : lOld) {
if(i == -1) ret += toBinNumber(usedX.size(), 4);
else {
bool found = false;
forR(j, usedX.size()) if(usedX[j] == i) {
ret += toBinNumber(j, 4);
found = true;
break;
}
assert(found);
}
}
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, 5));
if(val >= Q + 1) {
usedX.push_back(i);
indIn.push_back(val - Q - 1);
} else {
indIn.push_back(val);
}
ci += 5;
}
forR(i, Q) {
int val = fromBinNumber(s.substr(ci, 4));
if(val == usedX.size()) lOld.push_back(-1);
else {
lOld.push_back(usedX[val]);
}
ci += 4;
}
for(int i : indIn) cerr << i << ' ';
cerr << '\n';
for(int i : lOld) cerr << i << ' ';
cerr << '\n';
for(int i : usedX) 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:102:2: note: in expansion of macro 'forR'
102 | forR(i, indIn.size()) {
| ^~~~
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:113:13: note: in expansion of macro 'forR'
113 | forR(j, usedX.size()) if(usedX[j] == i) {
| ^~~~
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:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | if(val == usedX.size()) lOld.push_back(-1);
| ~~~~^~~~~~~~~~~~~~~
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:118:3: note: in expansion of macro 'REP'
118 | REP(j, 1, pth.size()) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
6152 KB |
Output is correct |
| 2 |
Correct |
0 ms |
776 KB |
Output is correct |
| 3 |
Partially correct |
49 ms |
6936 KB |
Partially correct |
| 4 |
Correct |
148 ms |
6968 KB |
Output is correct |
| 5 |
Partially correct |
55 ms |
7084 KB |
Partially correct |
| 6 |
Partially correct |
80 ms |
7184 KB |
Partially correct |
| 7 |
Partially correct |
45 ms |
7040 KB |
Partially correct |
| 8 |
Partially correct |
80 ms |
6900 KB |
Partially correct |
| 9 |
Partially correct |
143 ms |
6828 KB |
Partially correct |
| 10 |
Correct |
34 ms |
6684 KB |
Output is correct |
| 11 |
Partially correct |
40 ms |
6836 KB |
Partially correct |
| 12 |
Correct |
78 ms |
7088 KB |
Output is correct |
| 13 |
Correct |
54 ms |
6836 KB |
Output is correct |
| 14 |
Correct |
41 ms |
7084 KB |
Output is correct |
| 15 |
Correct |
112 ms |
6832 KB |
Output is correct |
| 16 |
Correct |
27 ms |
6664 KB |
Output is correct |
| 17 |
Partially correct |
235 ms |
7124 KB |
Partially correct |
| 18 |
Partially correct |
248 ms |
7180 KB |
Partially correct |
| 19 |
Partially correct |
62 ms |
8156 KB |
Partially correct |
| 20 |
Correct |
47 ms |
8224 KB |
Output is correct |
| 21 |
Partially correct |
57 ms |
8068 KB |
Partially correct |
| 22 |
Partially correct |
73 ms |
8152 KB |
Partially correct |
| 23 |
Correct |
56 ms |
8064 KB |
Output is correct |
| 24 |
Partially correct |
70 ms |
8104 KB |
Partially correct |
| 25 |
Partially correct |
207 ms |
7064 KB |
Partially correct |
| 26 |
Partially correct |
203 ms |
7064 KB |
Partially correct |
| 27 |
Correct |
0 ms |
784 KB |
Output is correct |
| 28 |
Correct |
63 ms |
7348 KB |
Output is correct |
| 29 |
Partially correct |
80 ms |
5156 KB |
Partially correct |
| 30 |
Correct |
80 ms |
7484 KB |
Output is correct |
| 31 |
Correct |
41 ms |
7464 KB |
Output is correct |
| 32 |
Correct |
64 ms |
7348 KB |
Output is correct |
| 33 |
Correct |
52 ms |
7124 KB |
Output is correct |
| 34 |
Correct |
99 ms |
7596 KB |
Output is correct |
| 35 |
Correct |
83 ms |
7572 KB |
Output is correct |
| 36 |
Correct |
83 ms |
7480 KB |
Output is correct |
| 37 |
Correct |
72 ms |
4108 KB |
Output is correct |
| 38 |
Partially correct |
187 ms |
5440 KB |
Partially correct |
| 39 |
Correct |
190 ms |
5312 KB |
Output is correct |
| 40 |
Correct |
25 ms |
4668 KB |
Output is correct |
| 41 |
Partially correct |
69 ms |
7820 KB |
Partially correct |
| 42 |
Correct |
53 ms |
8024 KB |
Output is correct |
| 43 |
Correct |
109 ms |
8036 KB |
Output is correct |
| 44 |
Correct |
31 ms |
7716 KB |
Output is correct |
| 45 |
Correct |
67 ms |
4068 KB |
Output is correct |
| 46 |
Partially correct |
87 ms |
5132 KB |
Partially correct |
| 47 |
Correct |
110 ms |
4884 KB |
Output is correct |
| 48 |
Correct |
0 ms |
776 KB |
Output is correct |
| 49 |
Correct |
1 ms |
776 KB |
Output is correct |
| 50 |
Correct |
23 ms |
6376 KB |
Output is correct |
| 51 |
Partially correct |
3 ms |
1032 KB |
Partially correct |
| 52 |
Correct |
2 ms |
772 KB |
Output is correct |
| 53 |
Correct |
32 ms |
6576 KB |
Output is correct |
| 54 |
Correct |
17 ms |
4376 KB |
Output is correct |
| 55 |
Correct |
38 ms |
5028 KB |
Output is correct |
| 56 |
Correct |
35 ms |
7536 KB |
Output is correct |
| 57 |
Correct |
50 ms |
7716 KB |
Output is correct |
| 58 |
Partially correct |
45 ms |
6140 KB |
Partially correct |
| 59 |
Correct |
64 ms |
7912 KB |
Output is correct |
| 60 |
Partially correct |
51 ms |
7624 KB |
Partially correct |
| 61 |
Correct |
65 ms |
8040 KB |
Output is correct |
| 62 |
Correct |
60 ms |
7412 KB |
Output is correct |
| 63 |
Correct |
65 ms |
7876 KB |
Output is correct |
| 64 |
Correct |
27 ms |
6840 KB |
Output is correct |
| 65 |
Correct |
38 ms |
5492 KB |
Output is correct |
| 66 |
Correct |
38 ms |
8180 KB |
Output is correct |
| 67 |
Correct |
38 ms |
5384 KB |
Output is correct |
| 68 |
Correct |
34 ms |
8132 KB |
Output is correct |
| 69 |
Correct |
0 ms |
860 KB |
Output is correct |
| 70 |
Correct |
0 ms |
784 KB |
Output is correct |
| 71 |
Correct |
2 ms |
784 KB |
Output is correct |
| 72 |
Correct |
15 ms |
3852 KB |
Output is correct |
| 73 |
Partially correct |
27 ms |
4632 KB |
Partially correct |
| 74 |
Partially correct |
31 ms |
4596 KB |
Partially correct |
| 75 |
Correct |
15 ms |
4632 KB |
Output is correct |
| 76 |
Correct |
0 ms |
780 KB |
Output is correct |
| 77 |
Correct |
46 ms |
7092 KB |
Output is correct |
| 78 |
Partially correct |
40 ms |
7096 KB |
Partially correct |
| 79 |
Correct |
47 ms |
7092 KB |
Output is correct |
| 80 |
Correct |
0 ms |
784 KB |
Output is correct |
| 81 |
Correct |
49 ms |
6976 KB |
Output is correct |
| 82 |
Partially correct |
45 ms |
6840 KB |
Partially correct |
| 83 |
Correct |
54 ms |
6856 KB |
Output is correct |
