結果

問題 No.772 Dynamic Distance Sum
ユーザー pekempey
提出日時 2018-12-20 08:50:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,211 ms / 5,000 ms
コード長 9,834 bytes
コンパイル時間 1,238 ms
コンパイル使用メモリ 83,400 KB
実行使用メモリ 49,200 KB
最終ジャッジ日時 2024-09-25 08:23:30
合計ジャッジ時間 18,426 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
[1] wo sankou ni shita ga (omoni median), warito tigau koto wo shita.
Priority Queue wo tsukau to toptree wo tukawanaku temo ikeru ikeru (?)
[1] S. Alstrup, J. Holm, K. D. Lichtenberg, M. Thorup. Maintaining information in fully dynamic trees with top trees, Jornal ACM Transactions on
       Algorithms, 1(2), Pages 243--264, 2005.
*/
#include <stdio.h>
#include <assert.h>
#include <queue> /* priority_queue */
#include <iostream>
using namespace std;
#define N 100001
#define TRUE 1
#define FALSE 0
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void swapl(long long *x, long long *y) {
long long t = *x;
*x = *y;
*y = t;
}
struct Queue {
std::priority_queue<std::pair<int, int>> q;
std::priority_queue<std::pair<int, int>> q2;
void ins(int k, int v) {
q.emplace(k, v);
}
void del(int k, int v) {
q2.emplace(k, v);
}
std::pair<int, int> min() {
while (!q.empty() && !q2.empty() && q.top() == q2.top()) {
q.pop();
q2.pop();
}
return q.top();
}
int size() {
return q.size() - q2.size();
}
};
Queue q[N];
/* structure data */
int L[N], R[N], P[N], REV[N];
int MARKED[N]; /* whether the specified node is marked or not (this is a bool value) */
long long L_COST[N]; /* the cost of the downward edge */
long long R_COST[N]; /* the cost of the upward etge */
long long P_COST[N];
/* aggregation data */
int W[N]; /* the numebr of marked children */
long long WU[N]; /* the sum of weights from the external node named u to other nodes */
long long WV[N]; /* the sum of weights from the external node named v to other nodes */
long long WD[N]; /* the sum of weights from the central node to other nodes */
long long LEN[N]; /* the total length of the current cluster path */
/* special aggregation data (this data should be handled carefully !!) */
int W_DASHED[N]; /* the number of marked children lied on dashed subtrees */
long long WD_DASHED[N]; /* the sum of weights from the central node to the dashed children of the specified node */
/* external node, v is an ancestor of u */
void fix(int x) {
W[x] = MARKED[x] + W_DASHED[x] + W[L[x]] + W[R[x]];
WD[x] = WD_DASHED[x] + WV[L[x]] + WU[R[x]] + W[L[x]] * L_COST[x] + W[R[x]] * R_COST[x];
WU[x] = WU[L[x]] + WU[R[x]] + WD_DASHED[x] + (LEN[L[x]] + L_COST[x]) * (MARKED[x] + W_DASHED[x]) + (LEN[L[x]] + L_COST[x] + R_COST[x]) * W[R[x]];
WV[x] = WV[R[x]] + WV[L[x]] + WD_DASHED[x] + (LEN[R[x]] + R_COST[x]) * (MARKED[x] + W_DASHED[x]) + (LEN[R[x]] + R_COST[x] + L_COST[x]) * W[L[x]];
LEN[x] = LEN[L[x]] + LEN[R[x]] + L_COST[x] + R_COST[x]; /* (^^) */
}
void reverse(int x, int rev) {
if (!rev) return;
REV[x] ^= rev;
swapl(&WU[x], &WV[x]);
swapl(&L_COST[x], &R_COST[x]);
swap(&L[x], &R[x]);
}
void push(int x) {
reverse(L[x], REV[x]);
reverse(R[x], REV[x]);
REV[x] = FALSE;
}
void rot(int x) {
int y = P[x];
int z = P[y];
if (L[z] == y) L[z] = x;
if (R[z] == y) R[z] = x;
P_COST[x] = P_COST[y];
P_COST[y] = 0;
P[y] = x;
P[x] = z;
if (L[y] == x) {
L[y] = R[x];
R[x] = y;
if (L[y]) P[L[y]] = y;
else {
swapl(&L_COST[y], &R_COST[x]);
}
} else {
R[y] = L[x];
L[x] = y;
if (R[y]) P[R[y]] = y;
else {
swapl(&R_COST[y], &L_COST[x]);
}
}
fix(y);
}
bool is_root(int x) {
return L[P[x]] != x && R[P[x]] != x;
}
void local_splay(int x) {
while (!is_root(x)) {
if (!is_root(P[x])) {
rot((L[P[x]] == x) == (L[P[P[x]]] == P[x]) ? P[x] : x);
}
rot(x);
}
}
void push_ancestors(int x) {
if (!x) return;
push_ancestors(P[x]);
push(x);
}
void global_splay(int x) {
push_ancestors(x);
{
int y = x;
while (y != 0) {
while (!is_root(y)) y = P[y];
int z = P[y];
if (z) {
W_DASHED[z] -= W[y];
WD_DASHED[z] -= WV[y] + W[y] * P_COST[y];
q[z].del(W[y], y);
}
y = z;
}
}
int y = x;
int l = 0;
while (y != 0) {
local_splay(y);
int w = L[y];
P_COST[w] = L_COST[y];
L_COST[y] = P_COST[l];
P_COST[l] = 0;
W_DASHED[y] += W[w];
WD_DASHED[y] += WV[w] + W[w] * P_COST[w];
if (w) {
q[y].ins(W[w], w);
}
L[y] = l;
l = y;
fix(y);
y = P[y];
}
local_splay(x);
fix(x);
}
void reroot(int x) {
global_splay(x);
reverse(x, TRUE);
push(x);
}
void link(int x, int y, long long w) {
reroot(x);
global_splay(y);
// assert(L[y] == 0);
assert(P[x] == 0);
L[y] = x;
P[x] = y;
L_COST[y] = w;
fix(y);
}
void cut(int x, int y) {
reroot(x);
global_splay(y);
R_COST[y] = 0;
P_COST[R[y]] = 0;
P[R[y]] = 0;
R[y] = 0;
fix(y);
}
void dfs(int u) {
if (!u) {
return;
}
dfs(L[u]);
// assert(!(L[u] == 0 && L_COST[u] != 0));
// assert(!(R[u] == 0 && R_COST[u] != 0));
printf(" ");
printf("(%d,%lld)", L[u], L_COST[u]);
printf("%d", u);
printf("(%d,%lld)", R[u], R_COST[u]);
printf(" ");
dfs(R[u]);
}
void iter(int x, vector<int> &res) {
if (!x) return;
res.push_back(x);
iter(L[x], res);
iter(R[x], res);
}
bool same(int x, int y) {
while (P[x] != 0) x = P[x];
while (P[y] != 0) y = P[y];
bool res = x == y;
global_splay(x);
global_splay(y);
return res;
}
long long median2(int x, int n) {
long long res = 2e18;
for (int i = 1; i <= n; i++) {
if (same(i, x)) {
global_splay(i);
res = min(res, WD[i]);
}
}
return res;
}
pair<int, long long> median(int x) {
global_splay(x);
int ll = 0;
int rr = 0;
int E = W[x];
for (;;) {
push(x);
int n = W[x];
if (L[x]) {
int y = L[x];
int ny = ll + W[y];
int nx = E - ny;
assert(ny + nx == E);
if (ny > nx) {
rr += W[x] - W[y];
x = y;
continue;
}
}
if (R[x]) {
int y = R[x];
int ny = rr + W[y];
int nx = E - ny;
assert(ny + nx == E);
if (ny > nx) {
ll += W[x] - W[y];
x = y;
continue;
}
}
if (q[x].size() > 0) {
int y = q[x].min().second;
assert(is_root(y));
int ny = W[y];
int nx = E - ny;
if (ny > nx) {
rr += ll + W[x] - W[y];
ll = 0;
x = y;
continue;
}
}
break;
}
global_splay(x);
return make_pair(x, WD[x]);
}
void output(int n) {
for (int i = 1; i <= n; i++) {
global_splay(i);
printf("%d %lld %lld\n", i, WD[i], LEN[i]);
}
for (int i = 1; i <= n; i++) {
if (is_root(i)) {
printf("*** %d %d\n", i, P[i]);
}
}
for (int i = 1; i <= n; i++) {
if (is_root(i)) {
dfs(i);
}
puts("");
}
}
void test1() {
for (int i = 1; i <= 7; i++) {
MARKED[i] = 1;
}
link(1, 2, 2);
link(3, 4, 4);
link(2, 3, 3);
link(5, 6, 3);
link(5, 7, 10);
link(2, 5, 1);
printf("%d %d %d %d %lld %lld %lld %lld\n", L[0], R[0], P[0], W[0], WD[0], WU[0], WV[0], LEN[0]);
reroot(1);
for (int i = 1; i <= 7; i++) {
global_splay(i);
}
for (int i = 1; i <= 7; i++) {
printf("*** %d %lld\n", i, P_COST[i]);
}
global_splay(7);
for (int i = 1; i <= 7; i++) {
if (is_root(i)) {
dfs(i);
}
puts("");
}
global_splay(1); assert(WD[1] == 38); assert(W[1] == 7);
global_splay(2); assert(WD[2] == 28); assert(W[2] == 7);
global_splay(3); assert(WD[3] == 37); assert(W[3] == 7);
global_splay(4); assert(WD[4] == 57); assert(W[4] == 7);
global_splay(5); assert(WD[5] == 29); assert(W[5] == 7);
global_splay(6); assert(WD[6] == 44); assert(W[6] == 7);
global_splay(7); assert(WD[7] == 79); assert(W[7] == 7);
cout << "---" << endl;
cut(2, 5);
for (int i = 1; i <= 7; i++) {
printf("*** %d %lld\n", i, P_COST[i]);
}
for (int i = 1; i <= 7; i++) {
if (is_root(i)) {
dfs(i);
}
puts("");
}
}
void test2() {
for (int i = 1; i <= 7; i++) {
MARKED[i] = 1;
}
link(1, 2, 2);
link(3, 4, 4);
link(2, 5, 1);
link(5, 6, 3);
link(5, 7, 10);
link(2, 3, 3);
pair<int, long long> res = median(1);
assert(res.first == 2 && res.second == 28);
}
long long Q;
int main() {
int n, q;
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) {
MARKED[i] = TRUE;
}
long long S = 0;
while (q--) {
int type;
scanf("%d", &type);
if (type == 1) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a = (a - 1 + S) % n + 1;
b = (b - 1 + S) % n + 1;
link(a, b, c);
} else if (type == 2) {
int a, b;
scanf("%d %d", &a, &b);
a = (a - 1 + S) % n + 1;
b = (b - 1 + S) % n + 1;
cut(a, b);
} else {
int a;
scanf("%d", &a);
a = (a - 1 + S) % n + 1;
global_splay(a);
MARKED[a] ^= 1;
fix(a);
long long ans = median(a).second;
S += ans;
S %= n;
printf("%lld\n", ans);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0