Submission #371356
Source Code Expand
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <cstdio>
#include <bitset>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<55;
template<int N>
struct ETTree {
struct Node;
typedef Node* NP;
static Node last_d;
static NP last;
struct Node {
NP p, l, r;
int sz, idl, idr;
typedef pair<ll, int> P;
P d, mi;
Node(int idl, int idr, int idx, ll d) :p(nullptr), l(last), r(last), sz(1), idl(idl), idr(idr),
d(P(d, idx)), mi(P(d, idx)) {}
Node() : l(nullptr), r(nullptr), sz(0) {}
//pushをすると、pushをした頂点とその子の"すべて"の値の正当性が保証される
void push() {
assert(sz);
}
NP update() {
assert(this != last);
sz = 1+l->sz+r->sz;
mi = d;
if (l->sz) {
mi = min(mi, l->mi);
}
if (r->sz) {
mi = min(mi, r->mi);
}
return this;
}
void setdata(int idx, ll dd) {
d = P(dd, idx);
update();
}
void adddata(ll dd) {
d.first += dd;
update();
}
inline int pos() {
if (p) {
if (p->l == this) return -1;
if (p->r == this) return 1;
}
return 0;
}
void rot() {
NP qq = p->p;
int pps = p->pos();
if (p->l == this) {
p->l = r; r->p = p;
r = p; p->p = this;
} else {
p->r = l; l->p = p;
l = p; p->p = this;
}
p->update(); update();
p = qq;
if (!pps) return;
if (pps == -1) {
qq->l = this;
} else {
qq->r = this;
}
qq->update();
}
NP splay() {
assert(this != last);
supush();
int ps;
while ((ps = pos())) {
int pps = p->pos();
if (!pps) {
rot();
} else if (ps == pps) {
p->rot(); rot();
} else {
rot(); rot();
}
}
return this;
}
void supush() {
if (pos()) {
p->supush();
}
push();
}
void debug() {
if (this == last) return;
push();
l->debug();
printf("(%d-%d-{%lld %d %lld %d}) ", idl, idr, d.first, d.second, mi.first, mi.second);
r->debug();
}
};
typedef pair<int, int> P;
map<int, int> mp[N+1];
Node pool[2*N];
ETTree() {
for (int i = 0; i < N; i++) {
pool[2*i] = Node(N, i, -1, INF);
pool[2*i+1] = Node(i, N, -1, INF);
merge(pool+2*i, pool+2*i+1);
mp[N][i] = 2*i;
mp[i][N] = 2*i+1;
}
}
void debug(int d) {
tree(d)->debug();
}
NP tree(int d) {
assert(0 <= d && d < N);
return (&pool[mp[d].begin()->second])->splay();
}
NP merge(NP l, NP r) {
if (l == last) return r;
if (r == last) return l;
r = at(r, 0);
r->l = l;
l->p = r;
return r->update();
}
pair<NP, NP> split(NP n, int k) {
if (!k) return {last, n};
if (n->sz == k) return {n, last};
n = at(n, k);
NP m = n->l;
m->p = nullptr;
n->l = last;
n->update();
return {m, n};
}
NP at(NP n, int k) {
assert(n != last);
n->push();
if (k < n->l->sz) {
return at(n->l, k);
} else if (k == n->l->sz) {
n->splay();
return n;
} else {
return at(n->r, k-(n->l->sz+1));
}
}
//yの子としてxを追加
void evert(int x) {
int rt = root(x);
NP xt = tree(x);
auto sp = split(xt, xt->l->sz);
NP L, ML, MR, R;
tie(L, ML) = split(sp.first, 1);
tie(MR, R) = split(sp.second, sp.second->sz-1);
assert(L->idl == N && L->idr == rt && R->idl == rt && R->idr == N);
int lp = mp[N][rt], rp = mp[rt][N];
pool[lp].idr = x; pool[rp].idl = x;
mp[N].erase(rt); mp[rt].erase(N);
mp[N][x] = lp; mp[x][N] = rp;
merge(merge(merge(L, MR), ML), R);
}
void link(int x, int y, int idx, ll d) {
assert(mp[x].count(N));
// printf("link %d %d\n", x, y);
NP xt = tree(x);
NP yt = tree(y);
//ytの前にtree(x)を入れたい
int lp = mp[N][x], rp = mp[x][N];
pool[lp].splay();
pool[lp].idl = y;
pool[lp].setdata(idx, d);
pool[rp].splay();
pool[rp].idr = y;
pool[rp].setdata(idx, d);
mp[N].erase(x); mp[x].erase(N);
mp[y][x] = lp; mp[x][y] = rp;
xt->splay();
yt->splay();
auto sp = split(yt, yt->l->sz);
merge(merge(sp.first, xt), sp.second);
}
void cut(int x, int y) {
assert(mp[x].count(y));
int lp = mp[y][x], rp = mp[x][y];
pool[lp].splay();
pool[lp].idl = N;
pool[lp].setdata(-1, INF);
pool[rp].splay();
pool[rp].idr = N;
pool[rp].setdata(-1, INF);
NP lx = pool+lp, rx = pool+rp;
mp[y].erase(x); mp[x].erase(y);
mp[N][x] = lp; mp[x][N] = rp;
// L M R
NP L, M, R;
rx->splay();
R = split(rx, rx->l->sz+1).second;
lx->splay();
tie(L, M) = split(lx, lx->l->sz);
merge(L, R);
}
int root(int x) {
NP xt = tree(x);
return at(xt, 0)->idr;
}
void set(int x, int y, ll d) {
int lp = mp[x][y], rp = mp[y][x];
pool[lp].splay();
pool[lp].adddata(d);
pool[rp].splay();
pool[rp].idr = y;
pool[rp].adddata(d);
}
pair<int, int> get(int x) {
NP xt = tree(x);
return xt->mi;
}
//debug用 めっちゃ重いよ
void scan() {
for (int i = 0; i <= N; i++) {
for (auto p: mp[i]) {
assert(pool[p.second].idl == i);
assert(pool[p.second].idr == p.first);
}
}
}
};
template<int N>
typename ETTree<N>::Node ETTree<N>::last_d = ETTree::Node();
template<int N>
typename ETTree<N>::NP ETTree<N>::last = &last_d;
const int MN = 100100;
ETTree<MN> et;
typedef pair<int, int> E;
E e[MN];
bool used[MN];
int main() {
int n;
cin >> n;
for (int i = 0; i < n-1; i++) {
// printf("e %d\n", i);
int a, b, c;
cin >> a >> b >> c; a--; b--;
e[i] = E(a, b);
// et.debug(a); printf("ev %d\n", a);
et.evert(a);
// et.debug(a); printf("lif %d\n", a);
// et.debug(b); printf("lif %d\n", b);
et.link(a, b, i, c);
// et.debug(a); printf("lie %d\n", a);
// et.debug(b); printf("lie %d\n", b);
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int t;
cin >> t;
if (t == 1) {
int x, d;
cin >> x >> d; x--;
et.set(e[x].first, e[x].second, d);
} else {
int x;
cin >> x; x--;
if (used[x]) {
cout << -1 << endl;
continue;
}
// printf("get %d\n", e[x].first );
auto res = et.get(e[x].first).second;
used[res] = true;
et.cut(e[res].first, e[res].second);
printf("%d\n", res+1);
}
// et.debug(0); printf("de\n");
}
return 0;
}
Submission Info
Submission Time |
|
Task |
I - 盆栽 |
User |
yosupo |
Language |
C++11 (GCC 4.9.2) |
Score |
300 |
Code Size |
8184 Byte |
Status |
AC |
Exec Time |
1606 ms |
Memory |
32932 KB |
Judge Result
Set Name |
Subtask |
All |
Score / Max Score |
30 / 30 |
270 / 270 |
Status |
|
|
Set Name |
Test Cases |
Subtask |
atetubou-challenge1.in, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt |
All |
scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt |
Case Name |
Status |
Exec Time |
Memory |
scrambled_00.txt |
AC |
146 ms |
29664 KB |
scrambled_01.txt |
AC |
145 ms |
29724 KB |
scrambled_02.txt |
AC |
141 ms |
29720 KB |
scrambled_03.txt |
AC |
140 ms |
29732 KB |
scrambled_04.txt |
AC |
141 ms |
29720 KB |
scrambled_05.txt |
AC |
142 ms |
29724 KB |
scrambled_06.txt |
AC |
139 ms |
29728 KB |
scrambled_07.txt |
AC |
143 ms |
29728 KB |
scrambled_08.txt |
AC |
143 ms |
29724 KB |
scrambled_09.txt |
AC |
143 ms |
29780 KB |
scrambled_10.txt |
AC |
139 ms |
29728 KB |
scrambled_11.txt |
AC |
1424 ms |
30620 KB |
scrambled_12.txt |
AC |
1430 ms |
30624 KB |
scrambled_13.txt |
AC |
1492 ms |
30628 KB |
scrambled_14.txt |
AC |
1484 ms |
30648 KB |
scrambled_15.txt |
AC |
1440 ms |
30624 KB |
scrambled_16.txt |
AC |
1430 ms |
30624 KB |
scrambled_17.txt |
AC |
1475 ms |
30628 KB |
scrambled_18.txt |
AC |
1461 ms |
30624 KB |
scrambled_19.txt |
AC |
1455 ms |
30640 KB |
scrambled_20.txt |
AC |
1471 ms |
30632 KB |
scrambled_21.txt |
AC |
1269 ms |
32932 KB |
scrambled_22.txt |
AC |
145 ms |
29728 KB |
scrambled_23.txt |
AC |
143 ms |
29728 KB |
scrambled_24.txt |
AC |
141 ms |
29732 KB |
scrambled_25.txt |
AC |
145 ms |
29724 KB |
scrambled_26.txt |
AC |
144 ms |
29724 KB |
scrambled_27.txt |
AC |
1518 ms |
29772 KB |
scrambled_28.txt |
AC |
1571 ms |
29780 KB |
scrambled_29.txt |
AC |
1597 ms |
29728 KB |
scrambled_30.txt |
AC |
1601 ms |
29728 KB |
scrambled_31.txt |
AC |
1606 ms |
29732 KB |
scrambled_32.txt |
AC |
138 ms |
29728 KB |
subtask_00.txt |
AC |
138 ms |
29724 KB |
subtask_01.txt |
AC |
149 ms |
29736 KB |
subtask_02.txt |
AC |
146 ms |
29732 KB |
subtask_03.txt |
AC |
147 ms |
29724 KB |
subtask_04.txt |
AC |
148 ms |
29724 KB |
subtask_05.txt |
AC |
148 ms |
29728 KB |
subtask_06.txt |
AC |
149 ms |
29760 KB |
subtask_07.txt |
AC |
146 ms |
29732 KB |
subtask_08.txt |
AC |
149 ms |
29736 KB |
subtask_09.txt |
AC |
145 ms |
29740 KB |
subtask_10.txt |
AC |
146 ms |
29728 KB |
subtask_11.txt |
AC |
149 ms |
29728 KB |
subtask_12.txt |
AC |
149 ms |
29732 KB |
subtask_13.txt |
AC |
152 ms |
29732 KB |
subtask_14.txt |
AC |
150 ms |
29728 KB |
subtask_15.txt |
AC |
145 ms |
29716 KB |
subtask_16.txt |
AC |
134 ms |
29720 KB |