| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1091637 |
2024-09-21T16:01:55 Z |
marvinthang |
Spy 3 (JOI24_spy3) |
C++17 |
|
52 ms |
5128 KB |
/*************************************
* author: marvinthang *
* created: 21.03.2024 16:27:06 *
*************************************/
#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define REPD(i, n) for (int i = (n); i-- > 0; )
#define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; )
#define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
#include "debug.h"
#else
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define DB(...) 23
#define db(...) 23
#define debug(...) 23
#endif
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
// end of template
namespace {
template <class A, class B> bool minimize(A &a, B b) { return a > b ? a = b, true : false; }
const long long INF = 1e18;
}
string aoi(int N, int M, int Q, int K, vector <int> A, vector <int> B, vector <long long> C, vector <int> T, vector <int> X) {
vector <vector <int>> adj(N);
REP(i, M) {
adj[A[i]].push_back(i);
adj[B[i]].push_back(i);
}
priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> pq;
vector <long long> dist(N, INF);
vector <int> par(N, -1);
pq.emplace(dist[0] = 0, 0);
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du != dist[u]) continue;
for (int i: adj[u]) {
int v = A[i] ^ B[i] ^ u;
if (minimize(dist[v], du + C[i])) {
pq.emplace(dist[v], v);
par[v] = i;
}
}
}
vector <int> lost_roads(M, -1), in_query(N, -1);
REP(i, K) lost_roads[X[i]] = i;
REP(i, Q) in_query[T[i]] = i;
REP(i, N) adj[i].clear();
FOR(i, 1, N) adj[A[par[i]] ^ B[par[i]] ^ i].push_back(par[i]);
vector <int> nodes(K, -1);
vector <int> pid(Q, -1);
auto dfs = [&] (auto &&self, int u) -> int {
vector <int> child;
for (int i: adj[u]) {
int v = self(self, A[i] ^ B[i] ^ u);
if (v == -1) continue;
child.push_back(v);
if (lost_roads[i] != -1) nodes[lost_roads[i]] = v;
}
if ((int) child.size() >= 2 && in_query[u] == -1) {
in_query[u] = pid.size();
pid.push_back(-1);
}
if (in_query[u] != -1) {
for (int v: child) pid[v] = in_query[u];
return in_query[u];
}
return child.empty() ? -1 : child[0];
};
dfs(dfs, 0);
string res;
int sz = pid.size();
int lg = __lg(sz) + 1;
vector <bool> is_leaf(sz, true);
REP(i, sz) if (pid[i] != -1) is_leaf[pid[i]] = false;
if (Q == 1) is_leaf[0] = false;
vector <int> id(sz, -1);
int cl = 0;
REP(i, sz) if (!is_leaf[i]) id[i] = cl++;
int lg2 = __lg(cl) + 1;
REP(i, Q) res += char('0' + is_leaf[i]);
REP(i, sz) {
if (pid[i] == -1) pid[i] = cl;
else pid[i] = id[pid[i]];
REP(j, lg2) res += char('0' + BIT(pid[i], j));
}
REP(i, K) {
if (nodes[i] == -1) nodes[i] = sz;
REP(j, lg) res += char('0' + BIT(nodes[i], j));
}
return res;
}
/*************************************
* author: marvinthang *
* created: 21.03.2024 16:32:33 *
*************************************/
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define REPD(i, n) for (int i = (n); i-- > 0; )
#define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; )
#define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
#include "debug.h"
#else
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define DB(...) 23
#define db(...) 23
#define debug(...) 23
#endif
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
// end of template
namespace {
template <class A, class B> bool minimize(A &a, B b) { return a > b ? a = b, true : false; }
const long long INF = 1e18;
}
void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B, vector<long long> C, vector<int> T, vector<int> X, string s) {
vector <vector <int>> adj(N);
REP(i, M) {
adj[A[i]].push_back(i);
adj[B[i]].push_back(i);
}
int t = 0;
vector <bool> is_leaf(Q, true);
REP(i, Q) if (s[t++] == '0') is_leaf[i] = false;
int num_leaf = count(ALL(is_leaf), true);
int lg = 0, lg2 = -1, sz = 0;
while (lg2 == -1) {
++lg;
int x = (int) s.size() - t - K * lg;
FORE(i, 1, lg) if (x % i == 0) {
int v = x / i;
if (num_leaf <= v && v < MASK(lg) && __lg(v - num_leaf) + 1 == i) {
lg2 = i;
sz = v;
break;
}
}
}
vector <int> nd;
REP(i, sz) if (i >= Q || !is_leaf[i]) nd.push_back(i);
nd.push_back(-1);
vector <int> par(sz), nodes(K);
REP(i, sz) {
int x = 0;
REP(j, lg2) if (s[t++] == '1') x |= MASK(j);
par[i] = nd[x];
}
REP(i, K) REP(j, lg) if (s[t++] == '1') nodes[i] |= MASK(j);
vector <vector <int>> child(sz);
vector <int> tmask(sz + 1);
int rt = -1;
REP(i, sz) {
if (par[i] == -1) rt = i;
else child[par[i]].push_back(i);
}
auto dfs = [&] (auto &&self, int u) -> void {
if (u < Q) tmask[u] = MASK(u);
for (int v: child[u]) {
self(self, v);
tmask[u] |= tmask[v];
}
};
dfs(dfs, rt);
REP(t, Q) {
REP(i, K) C[X[i]] = BIT(tmask[nodes[i]], t) ? 0 : INF;
priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> pq;
vector <long long> dist(N, INF);
vector <int> trace(N, -1);
pq.emplace(dist[0] = 0, 0);
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du != dist[u]) continue;
for (int i: adj[u]) {
int v = A[i] ^ B[i] ^ u;
if (minimize(dist[v], du + C[i])) {
pq.emplace(dist[v], v);
trace[v] = i;
}
}
}
int u = T[t];
vector <int> res;
while (u) {
int i = trace[u];
res.push_back(i);
u = A[i] ^ B[i] ^ u;
}
reverse(res.begin(), res.end());
answer(res);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2580 KB |
Output is correct |
| 2 |
Correct |
0 ms |
784 KB |
Output is correct |
| 3 |
Partially correct |
29 ms |
3604 KB |
Partially correct |
| 4 |
Partially correct |
25 ms |
4340 KB |
Partially correct |
| 5 |
Partially correct |
36 ms |
3612 KB |
Partially correct |
| 6 |
Partially correct |
32 ms |
3512 KB |
Partially correct |
| 7 |
Partially correct |
32 ms |
3508 KB |
Partially correct |
| 8 |
Partially correct |
27 ms |
3640 KB |
Partially correct |
| 9 |
Partially correct |
23 ms |
4004 KB |
Partially correct |
| 10 |
Correct |
16 ms |
3804 KB |
Output is correct |
| 11 |
Partially correct |
31 ms |
3508 KB |
Partially correct |
| 12 |
Correct |
36 ms |
3648 KB |
Output is correct |
| 13 |
Correct |
35 ms |
3424 KB |
Output is correct |
| 14 |
Correct |
32 ms |
3472 KB |
Output is correct |
| 15 |
Correct |
28 ms |
4024 KB |
Output is correct |
| 16 |
Correct |
13 ms |
3860 KB |
Output is correct |
| 17 |
Partially correct |
38 ms |
5128 KB |
Partially correct |
| 18 |
Partially correct |
38 ms |
5080 KB |
Partially correct |
| 19 |
Correct |
39 ms |
4512 KB |
Output is correct |
| 20 |
Correct |
28 ms |
4476 KB |
Output is correct |
| 21 |
Correct |
39 ms |
4492 KB |
Output is correct |
| 22 |
Correct |
52 ms |
4372 KB |
Output is correct |
| 23 |
Correct |
36 ms |
4432 KB |
Output is correct |
| 24 |
Correct |
52 ms |
4380 KB |
Output is correct |
| 25 |
Partially correct |
40 ms |
4500 KB |
Partially correct |
| 26 |
Partially correct |
40 ms |
4280 KB |
Partially correct |
| 27 |
Correct |
0 ms |
844 KB |
Output is correct |
| 28 |
Correct |
35 ms |
3760 KB |
Output is correct |
| 29 |
Partially correct |
13 ms |
3444 KB |
Partially correct |
| 30 |
Correct |
36 ms |
3964 KB |
Output is correct |
| 31 |
Correct |
22 ms |
4024 KB |
Output is correct |
| 32 |
Correct |
39 ms |
3764 KB |
Output is correct |
| 33 |
Correct |
39 ms |
3716 KB |
Output is correct |
| 34 |
Correct |
33 ms |
4372 KB |
Output is correct |
| 35 |
Correct |
27 ms |
4296 KB |
Output is correct |
| 36 |
Correct |
29 ms |
4304 KB |
Output is correct |
| 37 |
Correct |
10 ms |
3816 KB |
Output is correct |
| 38 |
Partially correct |
20 ms |
4872 KB |
Partially correct |
| 39 |
Correct |
18 ms |
4644 KB |
Output is correct |
| 40 |
Correct |
9 ms |
4136 KB |
Output is correct |
| 41 |
Partially correct |
48 ms |
3984 KB |
Partially correct |
| 42 |
Correct |
35 ms |
4240 KB |
Output is correct |
| 43 |
Correct |
52 ms |
4308 KB |
Output is correct |
| 44 |
Correct |
17 ms |
4092 KB |
Output is correct |
| 45 |
Correct |
10 ms |
3100 KB |
Output is correct |
| 46 |
Partially correct |
16 ms |
3764 KB |
Partially correct |
| 47 |
Correct |
15 ms |
3876 KB |
Output is correct |
| 48 |
Correct |
0 ms |
776 KB |
Output is correct |
| 49 |
Correct |
0 ms |
784 KB |
Output is correct |
| 50 |
Correct |
10 ms |
2580 KB |
Output is correct |
| 51 |
Partially correct |
2 ms |
776 KB |
Partially correct |
| 52 |
Correct |
0 ms |
776 KB |
Output is correct |
| 53 |
Correct |
13 ms |
2784 KB |
Output is correct |
| 54 |
Partially correct |
9 ms |
2316 KB |
Partially correct |
| 55 |
Correct |
25 ms |
2828 KB |
Output is correct |
| 56 |
Correct |
26 ms |
3768 KB |
Output is correct |
| 57 |
Partially correct |
39 ms |
3860 KB |
Partially correct |
| 58 |
Partially correct |
32 ms |
3568 KB |
Partially correct |
| 59 |
Correct |
44 ms |
4028 KB |
Output is correct |
| 60 |
Partially correct |
36 ms |
4020 KB |
Partially correct |
| 61 |
Correct |
49 ms |
4004 KB |
Output is correct |
| 62 |
Correct |
44 ms |
3920 KB |
Output is correct |
| 63 |
Correct |
45 ms |
3948 KB |
Output is correct |
| 64 |
Correct |
14 ms |
3852 KB |
Output is correct |
| 65 |
Correct |
27 ms |
3696 KB |
Output is correct |
| 66 |
Correct |
26 ms |
4384 KB |
Output is correct |
| 67 |
Correct |
24 ms |
3752 KB |
Output is correct |
| 68 |
Correct |
26 ms |
4328 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 |
776 KB |
Output is correct |
| 72 |
Correct |
11 ms |
2328 KB |
Output is correct |
| 73 |
Partially correct |
23 ms |
2768 KB |
Partially correct |
| 74 |
Partially correct |
23 ms |
2836 KB |
Partially correct |
| 75 |
Correct |
10 ms |
2840 KB |
Output is correct |
| 76 |
Correct |
0 ms |
776 KB |
Output is correct |
| 77 |
Correct |
31 ms |
3372 KB |
Output is correct |
| 78 |
Partially correct |
26 ms |
3324 KB |
Partially correct |
| 79 |
Correct |
32 ms |
3348 KB |
Output is correct |
| 80 |
Correct |
0 ms |
776 KB |
Output is correct |
| 81 |
Correct |
37 ms |
3364 KB |
Output is correct |
| 82 |
Partially correct |
30 ms |
3492 KB |
Partially correct |
| 83 |
Correct |
43 ms |
3392 KB |
Output is correct |
