Submission #376435
Source Code Expand
#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define repsz(i,v) rep(i,(v).size())
#define aur auto&
#define bit(n) (1LL<<(n))
#define eb emplace_back
#define mt make_tuple
#define fst first
#define snd second
using namespace std;
typedef long long ll;
//#define int long long
template<class C>int size(const C &c){ return c.size(); }
template<class T>bool chmin(T&a,const T&b){if(a<=b)return false;a=b;return true;}
template<class T>bool chmax(T&a,const T&b){if(a>=b)return false;a=b;return true;}
// Allocator//{{{
template<typename T>
struct Allocator{//{{{
private:
struct Handler{//{{{
Handler(){ Allocator::constructor(); }
~Handler(){ Allocator::destructor(); }
};//}}}
using Ptr = T *;
static vector<Ptr> pool;
static vector<size_t> sizes;
static vector<Ptr> frees;
static inline void constructor(){ allocate(1024); }
static inline void destructor(){ for(auto &p : pool) ::operator delete(p); }
static inline Ptr get(const bool &clear = false){//{{{
static Handler h;
static size_t i = 0, p = 0;
if(clear){ i = p = 0; return nullptr; }
if(!frees.empty()){
Ptr res = frees.back(); frees.pop_back();
return res;
}
if(p == sizes[i]) if(++i == sizes.size()){
p = 0;
allocate(sizes.back() * 2);
}
return &pool[i][p++];
}//}}}
static inline void reserve(const size_t &n){ allocate(n); }
static inline void allocate(const size_t &n){//{{{
pool.emplace_back(static_cast<Ptr>(::operator new(n * sizeof(T))));
sizes.emplace_back(n);
}//}}}
public:
static void *operator new(size_t size){
return static_cast<void *>(get());
}
template<typename Arg, typename ...Args>
static void *operator new(size_t size, Arg arg, Args ...args){
return ::operator new(size, arg, args...);
}
static void operator delete(void *ptr){
frees.emplace_back(static_cast<Ptr>(ptr));
}
static void clear_allocated(){ get(true); }
};//}}}
template<typename T> vector<T*> Allocator<T>::pool;
template<typename T> vector<size_t> Allocator<T>::sizes;
template<typename T> vector<T*> Allocator<T>::frees;
//}}}
template<typename Node>
struct RBST{//{{{
static inline unsigned int xor128(){//{{{
static unsigned int x=129042, y=38923212, z=3829312, w=3893189;
unsigned int t=x^(x<<11);
x=y;y=z;z=w;
return w=(w^(w>>19))^(t^(t>>8));
}//}}}
static inline int rnd(int m){ return xor128() % m; }
using Ref = Node *;
static inline int size(Ref u){ return u == nullptr ? 0 : u->size; }
static inline Ref update(Ref u){ return u->update(); }
static inline Ref remove_ch(Ref u, int dir, bool need_update = true){//{{{
Ref c = u->ch(dir);
if(c != nullptr){
u->ch(dir) = c->p = nullptr;
if(need_update) update(u);
}
return c;
}//}}}
static inline Ref add_ch(Ref u, int dir, Ref c, bool need_update = true){//{{{
remove_ch(u, dir, false);
if((u->ch(dir) = c) != nullptr) c->p = u;
return need_update ? update(u) : u;
}//}}}
static Ref join(Ref l, Ref r){//{{{
if(l == nullptr or r == nullptr) return l == nullptr ? r : l;
if(rnd(size(l) + size(r)) < size(l)){
l->r = join(l->r, r);
if(l->r != nullptr) l->r->p = l;
return update(l);
}else{
r->l = join(l, r->l);
if(r->l != nullptr) r->l->p = r;
return update(r);
}
}//}}}
static Ref join(initializer_list<Ref> us){//{{{
Ref res = nullptr;
for(Ref u : us) res = join(res, u);
return res;
}//}}}
// [*, u), [u, *)
static pair<Ref, Ref> split_l(Ref u){//{{{
Ref l = remove_ch(u, 0), r = u;
for(Ref p = u->p; p; u = p, p = p->p){
if(p->l == u) r = add_ch(p, 0, r);
else l = add_ch(p, 1, l);
}
return make_pair(l, r);
}//}}}
// [*, u], (u, *)
static pair<Ref, Ref> split_r(Ref u){//{{{
Ref l = u, r = remove_ch(u, 1);
for(Ref p = u->p; p; u = p, p = p->p){
if(p->l == u) r = add_ch(p, 0, r);
else l = add_ch(p, 1, l);
}
return make_pair(l, r);
}//}}}
// [*, u), u, (u, *]
static pair<Ref, Ref> split_lr(Ref u){//{{{
Ref l = remove_ch(u, 0), r = remove_ch(u, 1);
for(Ref p = u->p; p; u = p, p = p->p){
if(p->l == u) r = add_ch(p, 0, r);
else l = add_ch(p, 1, l);
}
return make_pair(l, r);
}//}}}
static Ref root(Ref u){//{{{
while(u->p) u = u->p;
return u;
}//}}}
static int index(Ref u){//{{{
int res = size(u->l);
for(; u->p; u = u->p) if(u->p->r == u) res += size(u->p->l) + 1;
return res;
}//}}}
};//}}}
struct ETT{//{{{
struct Node : Allocator<Node>{//{{{
using Ref = Node *;
Ref l, r, p;
int size;
Ref &ch(int dir){ return dir > 0 ? r : l; }
Ref rev;
using NData = pair<ll, int>;
using TData = pair<ll, int>;
NData ndata;
TData tdata;
Node(const NData &ndata)
: l(nullptr), r(nullptr), p(nullptr), size(1), rev(nullptr),
ndata(ndata)
{
update();
}
Ref update(){
size = (l ? l->size : 0) + 1 + (r ? r->size : 0);
tdata = ndata;
if(l) chmin(tdata, l->tdata);
if(r) chmin(tdata, r->tdata);
return this;
}
void set_data(NData _ndata){
ndata = _ndata;
for(Ref u = this; u; u = u->p) u->update();
}
};//}}}
using Tree = RBST<Node>;
using Ref = Tree::Ref;
vector<Ref> vs;
unordered_map<ll, Ref> es;
template<typename F>
ETT(const int &n, F f){
vs.resize(n);
rep(u, n) vs[u] = new Node(f(u));
}
~ETT(){ for(auto &p : vs) delete p; }
void add_edge(int u, int v, const Node::NData &ndata){//{{{
if(u > v) swap(u, v);
const ll key = ((ll)(u)<<32) | v;
Ref ul, ur; tie(ul, ur) = Tree::split_l(vs[u]);
Ref vl, vr; tie(vl, vr) = Tree::split_l(vs[v]);
Ref uv = new Node(ndata), vu = new Node(ndata);
uv->rev = vu; vu->rev = uv;
Tree::join({ul, uv, vr, vl, vu, ur});
es[key] = uv;
}//}}}
void remove_edge(int u, int v){//{{{
if(u > v) swap(u, v);
const ll key = ((ll)(u)<<32) | v;
assert(es[key] != nullptr);
Ref uv = es[key], vu = uv->rev;
es.erase(key);
if(Tree::index(vu) < Tree::index(uv)) swap(uv, vu);
// A-uv-B-vu-C => C-A, B
Ref A, B, C;
tie(A, B) = Tree::split_lr(uv);
tie(B, C) = Tree::split_lr(vu);
Tree::join(C, A);
}//}}}
bool has_edge(int u, int v){//{{{
if(u > v) swap(u, v);
const ll key = ((ll)(u)<<32) | v;
return es.count(key);
}//}}}
void set_data(int u, const Node::NData &ndata){ vs[u]->set_data(ndata); }
void set_data(int u, int v, const Node::NData &ndata){//{{{
if(u > v) swap(u, v);
const ll key = ((ll)(u)<<32) | v;
es[key]->set_data(ndata);
es[key]->rev->set_data(ndata);
}//}}}
Node::TData get_tdata(int u){ return Tree::root(vs[u])->tdata; }
Node::NData get_ndata(int u){ return vs[u]->ndata; }
Node::NData get_ndata(int u, int v){//{{{
if(u > v) swap(u, v);
const ll key = ((ll)(u)<<32) | v;
return es[key]->ndata;
}//}}}
};//}}}
bool solve(){
int n;
cin >> n;
constexpr ll INF = 1LL<<40;
ETT g(n, [](int u) -> pair<ll, int>{ return make_pair(1LL<<55, u); } );
vector<int> as, bs;
vector<ll> cs;
rep(i, n-1){
int a, b, c;
cin >> a >> b >> c;
--a; --b;
g.add_edge(a, b, make_pair(c, i));
as.eb(a); bs.eb(b); cs.eb(c);
}
int q;
cin >> q;
rep(_, q){
int op;
cin >> op;
if(op == 1){
int i; ll d; cin >> i >> d; --i;
if(!g.has_edge(as[i], bs[i])) continue;
g.set_data(as[i], bs[i], make_pair(cs[i] += d, i));
}else{
int i; cin >> i; --i;
if(!g.has_edge(as[i], bs[i])){
cout << -1 << endl;
continue;
}
i = g.get_tdata(as[i]).second;
g.remove_edge(as[i], bs[i]);
cout << i+1 << endl;
}
}
return true;
}
signed main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << std::fixed << std::setprecision(10);
solve();
return 0;
}
// vim:set foldmethod=marker commentstring=//%s:
Submission Info
Submission Time |
|
Task |
I - 盆栽 |
User |
MiSawa |
Language |
C++11 (GCC 4.9.2) |
Score |
300 |
Code Size |
9265 Byte |
Status |
AC |
Exec Time |
929 ms |
Memory |
28644 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 |
35 ms |
736 KB |
scrambled_01.txt |
AC |
31 ms |
1056 KB |
scrambled_02.txt |
AC |
33 ms |
1176 KB |
scrambled_03.txt |
AC |
31 ms |
1056 KB |
scrambled_04.txt |
AC |
33 ms |
1176 KB |
scrambled_05.txt |
AC |
30 ms |
1056 KB |
scrambled_06.txt |
AC |
33 ms |
1048 KB |
scrambled_07.txt |
AC |
32 ms |
988 KB |
scrambled_08.txt |
AC |
33 ms |
1052 KB |
scrambled_09.txt |
AC |
31 ms |
1052 KB |
scrambled_10.txt |
AC |
33 ms |
1092 KB |
scrambled_11.txt |
AC |
906 ms |
28548 KB |
scrambled_12.txt |
AC |
922 ms |
28548 KB |
scrambled_13.txt |
AC |
881 ms |
28556 KB |
scrambled_14.txt |
AC |
923 ms |
28640 KB |
scrambled_15.txt |
AC |
897 ms |
28560 KB |
scrambled_16.txt |
AC |
918 ms |
28572 KB |
scrambled_17.txt |
AC |
897 ms |
28556 KB |
scrambled_18.txt |
AC |
918 ms |
28548 KB |
scrambled_19.txt |
AC |
913 ms |
28548 KB |
scrambled_20.txt |
AC |
929 ms |
28644 KB |
scrambled_21.txt |
AC |
597 ms |
28344 KB |
scrambled_22.txt |
AC |
29 ms |
1180 KB |
scrambled_23.txt |
AC |
31 ms |
1176 KB |
scrambled_24.txt |
AC |
33 ms |
1052 KB |
scrambled_25.txt |
AC |
29 ms |
1056 KB |
scrambled_26.txt |
AC |
29 ms |
1056 KB |
scrambled_27.txt |
AC |
769 ms |
28336 KB |
scrambled_28.txt |
AC |
769 ms |
28328 KB |
scrambled_29.txt |
AC |
804 ms |
28332 KB |
scrambled_30.txt |
AC |
840 ms |
28336 KB |
scrambled_31.txt |
AC |
865 ms |
28328 KB |
scrambled_32.txt |
AC |
25 ms |
796 KB |
subtask_00.txt |
AC |
26 ms |
920 KB |
subtask_01.txt |
AC |
33 ms |
1172 KB |
subtask_02.txt |
AC |
31 ms |
1056 KB |
subtask_03.txt |
AC |
31 ms |
1112 KB |
subtask_04.txt |
AC |
32 ms |
1060 KB |
subtask_05.txt |
AC |
31 ms |
1068 KB |
subtask_06.txt |
AC |
32 ms |
1048 KB |
subtask_07.txt |
AC |
32 ms |
1064 KB |
subtask_08.txt |
AC |
33 ms |
1184 KB |
subtask_09.txt |
AC |
32 ms |
1060 KB |
subtask_10.txt |
AC |
32 ms |
1064 KB |
subtask_11.txt |
AC |
35 ms |
1056 KB |
subtask_12.txt |
AC |
32 ms |
1060 KB |
subtask_13.txt |
AC |
32 ms |
1052 KB |
subtask_14.txt |
AC |
32 ms |
1060 KB |
subtask_15.txt |
AC |
32 ms |
1184 KB |
subtask_16.txt |
AC |
30 ms |
800 KB |