// 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();
for (int i = 0; i < q; i++) {
int v = Tx[ls[i]];
ls2.clear();
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);
swap(ls1, ls2);
}
for (int i = 0; i < k; i++) s += to_binary(res[i], 4);
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[maxn];
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 = 0;
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 + 4);
lsw[j].pb(e); lx += 4;
}
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 ;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
5608 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
