| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1038112 |
2024-07-29T13:01:44 Z |
AmirAli_H1 |
Spy 3 (JOI24_spy3) |
C++17 |
|
56 ms |
6584 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 + k, 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++) s += to_binary(res[i], 5);
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++) {
int j = get_num(lx, lx + 5);
lsw[j].pb(e); lx += 5;
}
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 |
Partially correct |
13 ms |
5096 KB |
Partially correct |
| 2 |
Correct |
2 ms |
2324 KB |
Output is correct |
| 3 |
Partially correct |
32 ms |
5576 KB |
Partially correct |
| 4 |
Partially correct |
27 ms |
5900 KB |
Partially correct |
| 5 |
Partially correct |
43 ms |
5520 KB |
Partially correct |
| 6 |
Partially correct |
40 ms |
5568 KB |
Partially correct |
| 7 |
Partially correct |
34 ms |
5624 KB |
Partially correct |
| 8 |
Partially correct |
31 ms |
5484 KB |
Partially correct |
| 9 |
Partially correct |
26 ms |
5732 KB |
Partially correct |
| 10 |
Correct |
16 ms |
5484 KB |
Output is correct |
| 11 |
Partially correct |
34 ms |
5288 KB |
Partially correct |
| 12 |
Correct |
37 ms |
5536 KB |
Output is correct |
| 13 |
Correct |
43 ms |
5300 KB |
Output is correct |
| 14 |
Correct |
32 ms |
5496 KB |
Output is correct |
| 15 |
Correct |
32 ms |
5548 KB |
Output is correct |
| 16 |
Correct |
15 ms |
5372 KB |
Output is correct |
| 17 |
Partially correct |
45 ms |
6348 KB |
Partially correct |
| 18 |
Partially correct |
36 ms |
6584 KB |
Partially correct |
| 19 |
Partially correct |
42 ms |
6296 KB |
Partially correct |
| 20 |
Partially correct |
38 ms |
6188 KB |
Partially correct |
| 21 |
Partially correct |
39 ms |
6312 KB |
Partially correct |
| 22 |
Partially correct |
55 ms |
6148 KB |
Partially correct |
| 23 |
Partially correct |
39 ms |
6228 KB |
Partially correct |
| 24 |
Partially correct |
53 ms |
6304 KB |
Partially correct |
| 25 |
Partially correct |
44 ms |
5920 KB |
Partially correct |
| 26 |
Partially correct |
45 ms |
6092 KB |
Partially correct |
| 27 |
Correct |
1 ms |
2316 KB |
Output is correct |
| 28 |
Correct |
34 ms |
5592 KB |
Output is correct |
| 29 |
Partially correct |
19 ms |
5036 KB |
Partially correct |
| 30 |
Correct |
37 ms |
5772 KB |
Output is correct |
| 31 |
Correct |
25 ms |
5632 KB |
Output is correct |
| 32 |
Correct |
42 ms |
5624 KB |
Output is correct |
| 33 |
Correct |
40 ms |
5628 KB |
Output is correct |
| 34 |
Correct |
36 ms |
6040 KB |
Output is correct |
| 35 |
Correct |
32 ms |
5880 KB |
Output is correct |
| 36 |
Correct |
33 ms |
5800 KB |
Output is correct |
| 37 |
Partially correct |
11 ms |
4472 KB |
Partially correct |
| 38 |
Partially correct |
20 ms |
5832 KB |
Partially correct |
| 39 |
Correct |
21 ms |
5768 KB |
Output is correct |
| 40 |
Correct |
9 ms |
5144 KB |
Output is correct |
| 41 |
Partially correct |
49 ms |
5544 KB |
Partially correct |
| 42 |
Partially correct |
34 ms |
6140 KB |
Partially correct |
| 43 |
Correct |
56 ms |
6104 KB |
Output is correct |
| 44 |
Correct |
19 ms |
5980 KB |
Output is correct |
| 45 |
Partially correct |
12 ms |
4376 KB |
Partially correct |
| 46 |
Partially correct |
15 ms |
5092 KB |
Partially correct |
| 47 |
Correct |
17 ms |
5120 KB |
Output is correct |
| 48 |
Correct |
1 ms |
2316 KB |
Output is correct |
| 49 |
Correct |
1 ms |
2316 KB |
Output is correct |
| 50 |
Partially correct |
12 ms |
5064 KB |
Partially correct |
| 51 |
Partially correct |
3 ms |
2316 KB |
Partially correct |
| 52 |
Correct |
1 ms |
2316 KB |
Output is correct |
| 53 |
Correct |
16 ms |
5132 KB |
Output is correct |
| 54 |
Partially correct |
11 ms |
4120 KB |
Partially correct |
| 55 |
Correct |
27 ms |
4600 KB |
Output is correct |
| 56 |
Partially correct |
26 ms |
5700 KB |
Partially correct |
| 57 |
Partially correct |
39 ms |
5772 KB |
Partially correct |
| 58 |
Partially correct |
34 ms |
5128 KB |
Partially correct |
| 59 |
Correct |
48 ms |
6072 KB |
Output is correct |
| 60 |
Partially correct |
40 ms |
5756 KB |
Partially correct |
| 61 |
Correct |
48 ms |
5692 KB |
Output is correct |
| 62 |
Correct |
49 ms |
5640 KB |
Output is correct |
| 63 |
Correct |
48 ms |
5680 KB |
Output is correct |
| 64 |
Correct |
16 ms |
5588 KB |
Output is correct |
| 65 |
Correct |
24 ms |
5136 KB |
Output is correct |
| 66 |
Partially correct |
27 ms |
6248 KB |
Partially correct |
| 67 |
Correct |
28 ms |
5068 KB |
Output is correct |
| 68 |
Partially correct |
25 ms |
6052 KB |
Partially correct |
| 69 |
Correct |
1 ms |
2316 KB |
Output is correct |
| 70 |
Correct |
1 ms |
2316 KB |
Output is correct |
| 71 |
Correct |
1 ms |
2324 KB |
Output is correct |
| 72 |
Partially correct |
11 ms |
3868 KB |
Partially correct |
| 73 |
Partially correct |
25 ms |
4588 KB |
Partially correct |
| 74 |
Partially correct |
25 ms |
4524 KB |
Partially correct |
| 75 |
Correct |
13 ms |
4560 KB |
Output is correct |
| 76 |
Correct |
1 ms |
2324 KB |
Output is correct |
| 77 |
Correct |
33 ms |
5272 KB |
Output is correct |
| 78 |
Partially correct |
31 ms |
5040 KB |
Partially correct |
| 79 |
Correct |
35 ms |
5320 KB |
Output is correct |
| 80 |
Correct |
1 ms |
2328 KB |
Output is correct |
| 81 |
Correct |
40 ms |
5392 KB |
Output is correct |
| 82 |
Partially correct |
36 ms |
5388 KB |
Partially correct |
| 83 |
Correct |
43 ms |
5288 KB |
Output is correct |
