# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1038128 |
2024-07-29T13:16:37 Z |
AmirAli_H1 |
Spy 3 (JOI24_spy3) |
C++17 |
|
61 ms |
6592 KB |
// In the name of Allah
#include <bits/stdc++.h>
#include "Aoi.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
namespace {
const int maxn = 2e4 + 4;
const ll oo = 1e18 + 4;
int n, m, q, k;
vector<int> adj[maxn];
vector<int> adjx[maxn];
vector<pair<pii, ll>> E;
int ind[maxn], M[maxn];
int res[maxn]; string s;
ll dis[maxn]; int mark[maxn], par[maxn];
priority_queue<pll> qu;
vector<int> ls, ls1, ls2;
void dij(int v) {
fill(dis, dis + n, oo);
fill(mark, mark + n, 0); fill(par, par + n, -1);
dis[v] = 0; qu.push(Mp(-dis[v], v));
while (!qu.empty()) {
int v = qu.top().S; qu.pop();
if (mark[v]) continue;
mark[v] = 1;
for (int j : adj[v]) {
int u = E[j].F.F; ll w = E[j].S;
if (u == v) u = E[j].F.S;
if (dis[v] + w < dis[u]) {
dis[u] = dis[v] + w;
par[u] = j; qu.push(Mp(-dis[u], u));
}
}
}
}
string to_binary(int x, int r) {
string res = "";
for (int j = r - 1; j >= 0; j--) {
if (x & (1 << j)) res += "1";
else res += "0";
}
return res;
}
void dfs(int v) {
if (ind[v] != -1) ls.pb(ind[v]);
for (int u : adjx[v]) {
dfs(u);
}
}
}
string aoi(int Nx, int Mx, int Qx, int Kx, vector<int> Ax,
vector<int> Bx, vector<ll> Cx,
vector<int> Tx, vector<int> Rx) {
n = Nx; m = Mx; q = Qx; k = Kx;
fill(ind, ind + n, -1);
for (int i = 0; i < q; i++) {
int v = Tx[i]; ind[v] = i;
}
fill(M, M + m, -1);
for (int i = 0; i < k; i++) {
int j = Rx[i]; M[j] = i;
}
for (int i = 0; i < m; i++) {
int u = Ax[i], v = Bx[i]; ll w = Cx[i];
adj[u].pb(i); adj[v].pb(i);
E.pb(Mp(Mp(u, v), w));
}
dij(0);
for (int v = 0; v < n; v++) {
int j = par[v];
if (j != -1) {
int u = E[j].F.F;
if (u == v) u = E[j].F.S;
adjx[u].pb(v);
}
}
dfs(0);
for (int i = 0; i < q; i++) {
s += to_binary(ls[i], 4);
}
ls1.clear(); ls2.clear();
fill(res, res + maxn, q);
for (int i = 0; i < q; i++) {
int v = Tx[ls[i]];
while (v != 0) {
int j = par[v];
if (M[j] != -1) ls2.pb(M[j]);
if (E[j].F.F != v) v = E[j].F.F;
else v = E[j].F.S;
}
reverse(all(ls2));
int R = 0;
while (R < min(len(ls1), len(ls2))) {
if (ls1[R] == ls2[R]) R++;
else break;
}
for (int e = R; e < len(ls2); e++) res[ls2[e]] = i;
s += to_binary(len(ls1) - R, 9);
ls1.clear(); swap(ls1, ls2);
}
for (int i = 0; i < k; i += 3) s += to_binary(res[i] + (res[i + 1] * 17) + (res[i + 2] * 289), 13);
return s;
}
// In the name of Allah
#include <bits/stdc++.h>
#include "Aoi.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
namespace {
const int maxn = 2e4 + 4;
const int maxq = 20;
const ll oo = 1e18 + 4;
int n, m, q, k; string s;
vector<int> adj[maxn];
vector<pair<pii, ll>> E;
int ind[maxn], M[maxn];
ll dis[maxn]; int mark[maxn], par[maxn];
priority_queue<pll> qu;
vector<int> ans[maxq];
vector<int> ls, lsx, lsw[maxq];
vector<int> Rx; int ok[maxn];
void dij(int v) {
fill(dis, dis + n, oo);
fill(mark, mark + n, 0); fill(par, par + n, -1);
dis[v] = 0; qu.push(Mp(-dis[v], v));
while (!qu.empty()) {
int v = qu.top().S; qu.pop();
if (mark[v]) continue;
mark[v] = 1;
for (int j : adj[v]) {
int u = E[j].F.F; ll w = E[j].S;
if (u == v) u = E[j].F.S;
if (dis[v] + w < dis[u]) {
dis[u] = dis[v] + w;
par[u] = j; qu.push(Mp(-dis[u], u));
}
}
}
}
void check_ans(int i, vector<int> Tx) {
for (int e = 0; e < k; e++) {
if (ok[e]) {
int j = Rx[e];
int u = E[j].F.F, v = E[j].F.S;
adj[u].pb(j); adj[v].pb(j);
}
}
dij(0); int v = Tx[i];
while (v != 0) {
int j = par[v];
ans[i].pb(j);
if (E[j].F.F != v) v = E[j].F.F;
else v = E[j].F.S;
}
reverse(all(ans[i]));
for (int e = 0; e < k; e++) {
if (ok[e]) {
int j = Rx[e];
int u = E[j].F.F, v = E[j].F.S;
adj[u].pop_back(); adj[v].pop_back();
}
}
}
bool cmp(int i, int j) {
int j1 = Rx[i], j2 = Rx[j];
return min(dis[E[j1].F.F], dis[E[j1].F.S]) < min(dis[E[j2].F.F], dis[E[j2].F.S]);
}
int get_num(int l, int r) {
int res = 0, j = 0;
for (int i = r - 1; i >= l; i--) {
if (s[i] == '1') res += (1 << j);
j++;
}
return res;
}
}
void answer(const vector<int> &e);
void bitaro(int Nx, int Mx, int Qx, int Kx, vector<int> Ax,
vector<int> Bx, vector<ll> Cx,
vector<int> Tx, vector<int> Rw, string sx) {
n = Nx; m = Mx; q = Qx; k = Kx; s = sx; Rx = Rw;
fill(ind, ind + n, -1);
for (int i = 0; i < q; i++) {
int v = Tx[i]; ind[v] = i;
}
fill(M, M + m, -1);
for (int i = 0; i < k; i++) {
int j = Rx[i]; M[j] = i;
}
for (int i = 0; i < m; i++) {
int u = Ax[i], v = Bx[i]; ll w = Cx[i];
if (M[i] == -1) {
adj[u].pb(i); adj[v].pb(i);
}
else w = 1;
E.pb(Mp(Mp(u, v), w));
}
int sz = 0;
for (int i = 0; i < q; i++) {
ls.pb(get_num(sz, sz + 4)); sz += 4;
}
int lx = q * 13;
for (int e = 0; e < k; e += 3) {
int j = get_num(lx, lx + 13); lx += 13;
lsw[j % 17].pb(e); lsw[(j / 17) % 17].pb(e + 1);
lsw[(j / 289) % 17].pb(e + 2);
}
lsx.clear();
for (int i = 0; i < q; i++) {
int R = get_num(sz, sz + 9); sz += 9;
while (R--) lsx.pop_back();
for (int e : lsw[i]) lsx.pb(e);
fill(ok, ok + k, 0);
for (int e : lsx) ok[e] = 1;
check_ans(ls[i], Tx);
sort(all(lsx), cmp);
}
for (int i = 0; i < q; i++) answer(ans[i]);
return ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
5140 KB |
Output is correct |
2 |
Correct |
1 ms |
2316 KB |
Output is correct |
3 |
Correct |
33 ms |
5500 KB |
Output is correct |
4 |
Correct |
28 ms |
5804 KB |
Output is correct |
5 |
Correct |
39 ms |
5816 KB |
Output is correct |
6 |
Correct |
36 ms |
5796 KB |
Output is correct |
7 |
Correct |
34 ms |
5608 KB |
Output is correct |
8 |
Correct |
31 ms |
5568 KB |
Output is correct |
9 |
Correct |
28 ms |
5704 KB |
Output is correct |
10 |
Correct |
20 ms |
5288 KB |
Output is correct |
11 |
Correct |
34 ms |
5288 KB |
Output is correct |
12 |
Correct |
41 ms |
5508 KB |
Output is correct |
13 |
Correct |
38 ms |
5492 KB |
Output is correct |
14 |
Correct |
34 ms |
5288 KB |
Output is correct |
15 |
Correct |
35 ms |
5656 KB |
Output is correct |
16 |
Correct |
15 ms |
5392 KB |
Output is correct |
17 |
Correct |
44 ms |
6528 KB |
Output is correct |
18 |
Correct |
41 ms |
6592 KB |
Output is correct |
19 |
Correct |
42 ms |
6444 KB |
Output is correct |
20 |
Correct |
36 ms |
6480 KB |
Output is correct |
21 |
Correct |
46 ms |
6560 KB |
Output is correct |
22 |
Correct |
55 ms |
6532 KB |
Output is correct |
23 |
Correct |
41 ms |
6444 KB |
Output is correct |
24 |
Correct |
52 ms |
6312 KB |
Output is correct |
25 |
Correct |
45 ms |
5976 KB |
Output is correct |
26 |
Correct |
43 ms |
6044 KB |
Output is correct |
27 |
Correct |
2 ms |
2312 KB |
Output is correct |
28 |
Correct |
33 ms |
5612 KB |
Output is correct |
29 |
Correct |
16 ms |
5128 KB |
Output is correct |
30 |
Correct |
45 ms |
5948 KB |
Output is correct |
31 |
Correct |
24 ms |
5848 KB |
Output is correct |
32 |
Correct |
41 ms |
5552 KB |
Output is correct |
33 |
Correct |
41 ms |
5544 KB |
Output is correct |
34 |
Correct |
35 ms |
6052 KB |
Output is correct |
35 |
Correct |
31 ms |
5956 KB |
Output is correct |
36 |
Correct |
32 ms |
6052 KB |
Output is correct |
37 |
Correct |
12 ms |
4784 KB |
Output is correct |
38 |
Correct |
26 ms |
5648 KB |
Output is correct |
39 |
Correct |
20 ms |
5640 KB |
Output is correct |
40 |
Correct |
10 ms |
5136 KB |
Output is correct |
41 |
Correct |
49 ms |
5800 KB |
Output is correct |
42 |
Correct |
32 ms |
6160 KB |
Output is correct |
43 |
Correct |
61 ms |
6308 KB |
Output is correct |
44 |
Correct |
24 ms |
6156 KB |
Output is correct |
45 |
Correct |
11 ms |
4632 KB |
Output is correct |
46 |
Correct |
15 ms |
5420 KB |
Output is correct |
47 |
Correct |
17 ms |
5112 KB |
Output is correct |
48 |
Correct |
1 ms |
2324 KB |
Output is correct |
49 |
Correct |
1 ms |
2324 KB |
Output is correct |
50 |
Correct |
12 ms |
5140 KB |
Output is correct |
51 |
Correct |
2 ms |
2324 KB |
Output is correct |
52 |
Correct |
1 ms |
2328 KB |
Output is correct |
53 |
Correct |
16 ms |
5108 KB |
Output is correct |
54 |
Correct |
11 ms |
4220 KB |
Output is correct |
55 |
Correct |
27 ms |
4604 KB |
Output is correct |
56 |
Correct |
25 ms |
5708 KB |
Output is correct |
57 |
Correct |
39 ms |
6128 KB |
Output is correct |
58 |
Correct |
34 ms |
5136 KB |
Output is correct |
59 |
Correct |
50 ms |
6132 KB |
Output is correct |
60 |
Correct |
39 ms |
5908 KB |
Output is correct |
61 |
Correct |
47 ms |
6024 KB |
Output is correct |
62 |
Correct |
45 ms |
5696 KB |
Output is correct |
63 |
Correct |
50 ms |
6052 KB |
Output is correct |
64 |
Correct |
17 ms |
5568 KB |
Output is correct |
65 |
Correct |
25 ms |
5140 KB |
Output is correct |
66 |
Correct |
24 ms |
6212 KB |
Output is correct |
67 |
Correct |
26 ms |
5200 KB |
Output is correct |
68 |
Correct |
25 ms |
6060 KB |
Output is correct |
69 |
Correct |
1 ms |
2312 KB |
Output is correct |
70 |
Correct |
1 ms |
2324 KB |
Output is correct |
71 |
Correct |
1 ms |
2320 KB |
Output is correct |
72 |
Correct |
13 ms |
4288 KB |
Output is correct |
73 |
Correct |
25 ms |
4628 KB |
Output is correct |
74 |
Correct |
25 ms |
4648 KB |
Output is correct |
75 |
Correct |
11 ms |
4628 KB |
Output is correct |
76 |
Correct |
1 ms |
2316 KB |
Output is correct |
77 |
Correct |
34 ms |
5212 KB |
Output is correct |
78 |
Correct |
29 ms |
5552 KB |
Output is correct |
79 |
Correct |
34 ms |
5364 KB |
Output is correct |
80 |
Correct |
1 ms |
2324 KB |
Output is correct |
81 |
Correct |
46 ms |
5640 KB |
Output is correct |
82 |
Correct |
37 ms |
5428 KB |
Output is correct |
83 |
Correct |
39 ms |
5500 KB |
Output is correct |