Submission #373142

---

Source Code Expand

#ifndef KOMAKI_LOCAL
#define NDEBUG
#endif

#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()

std::string dbgDelim(int &i){ return (i++ == 0 ? "" : ", "); }
#define dbgEmbrace(exp) { int i = 0; os << "{"; { exp; } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q);
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp);
template <int INDEX, class TUPLE> void dbgDeploy(std::ostream &os, TUPLE tuple){}
template <int INDEX, class TUPLE, class H, class ...Ts> void dbgDeploy(std::ostream &os, TUPLE t)
{ os << (INDEX == 0 ? "" : ", ") << get<INDEX>(t); dbgDeploy<INDEX + 1, TUPLE, Ts...>(os, t); }
template <class T, class K> void dbgDeploy(std::ostream &os, std::pair<T, K> p, std::string delim)
{ os << "(" << p.first << delim << p.second << ")"; }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, std::tuple<Ts...> t)
{ os << "("; dbgDeploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p)
{ dbgDeploy(os, p, ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v)
{ dbgEmbrace( for(T t: v){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> s)
{ dbgEmbrace( for(T t: s){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.front(); }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.top();   }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
#define DBG_OUT std::cerr
#define DBG_OVERLOAD(_1, _2, _3, _4, _5, _6, macro_name, ...) macro_name
#define DBG_LINE() { char s[99]; sprintf(s, "line:%3d | ", __LINE__); DBG_OUT << s; }
#define DBG_OUTPUT(v) { DBG_OUT << (#v) << "=" << (v); }
#define DBG1(v, ...) { DBG_OUTPUT(v); }
#define DBG2(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG1(__VA_ARGS__); }
#define DBG3(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG2(__VA_ARGS__); }
#define DBG4(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG3(__VA_ARGS__); }
#define DBG5(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG4(__VA_ARGS__); }
#define DBG6(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG5(__VA_ARGS__); }

#define DEBUG0() { DBG_LINE(); DBG_OUT << std::endl; }
#define DEBUG(...)                                                      \
  {                                                                     \
    DBG_LINE();                                                         \
    DBG_OVERLOAD(__VA_ARGS__, DBG6, DBG5, DBG4, DBG3, DBG2, DBG1)(__VA_ARGS__); \
    DBG_OUT << std::endl;                                               \
  }





const i64 MAX = 100500;
tuple<i64, i64> edge_ends[MAX];
set<i64> edge_indices[MAX];
i64 edge_positions[MAX];


class Tree
{
public:
  void change(i64 i, i64 d);
  Tree erase(i64 tree_n);
  i64 getSmaller(i64 v_0_0, i64 v_1_0);

  set<tuple<i64, i64>> s;
  unordered_map<i64, i64> edge_weights;
};

void Tree::change(i64 i, i64 d)
{
  s.erase(make_tuple(edge_weights[i], i));
  edge_weights[i] += d;
  s.insert(make_tuple(edge_weights[i], i));
}

i64 Tree::getSmaller(i64 v_0_0, i64 v_1_0)
{
  set<i64> used_0;
  set<i64> used_1;
  used_0.insert(v_0_0);
  used_1.insert(v_1_0);
  vector<i64> v_0(1, v_0_0);
  vector<i64> v_1(1, v_1_0);
  i64 i_0 = 0;
  i64 i_1 = 0;
  auto it_0 = edge_indices[v_0[i_0]].begin();
  auto it_1 = edge_indices[v_1[i_1]].begin();
  while(true){
    while(i_0 < sz(v_0) && edge_indices[v_0[i_0]].end() == it_0){
      if(++i_0 == sz(v_0)) return v_0_0;
      it_0 = edge_indices[v_0[i_0]].begin();
    }
    while(i_1 < sz(v_1) && edge_indices[v_1[i_1]].end() == it_1){
      if(++i_1 == sz(v_1)) return v_1_0;
      it_1 = edge_indices[v_1[i_1]].begin();
    }
    i64 e_0 = *(it_0++);
    i64 e_1 = *(it_1++);
    i64 n_0 = get<0>(edge_ends[e_0]);
    i64 n_1 = get<0>(edge_ends[e_1]);
    if(n_0 == v_0[i_0]) n_0 = get<1>(edge_ends[e_0]);
    if(n_1 == v_1[i_1]) n_1 = get<1>(edge_ends[e_1]);
    if(!used_0.count(n_0)) v_0.push_back(n_0);
    if(!used_1.count(n_1)) v_1.push_back(n_1);
    used_0.insert(n_0);
    used_1.insert(n_1);
  }
}

Tree Tree::erase(i64 tree_n)
{
  i64 mini_edge = get<1>(*s.begin());
  s.erase(*s.begin());
  edge_indices[get<0>(edge_ends[mini_edge])].erase(mini_edge);
  edge_indices[get<1>(edge_ends[mini_edge])].erase(mini_edge);
  edge_positions[mini_edge] = -1;
  cout << mini_edge + 1 << endl;

  i64 root = getSmaller(get<0>(edge_ends[mini_edge]), get<1>(edge_ends[mini_edge]));

  set<i64> used;
  used.insert(root);
  vector<i64> v(1, root);
  Tree tree;
  rep(i, sz(v)){
    i64 node = v[i];
    for(auto edge_i: edge_indices[node]){
      i64 t = get<0>(edge_ends[edge_i]);
      if(t == node) t = get<1>(edge_ends[edge_i]);
      if(used.count(t)) continue;
      used.insert(t);
      v.push_back(t);
      i64 weight = edge_weights[edge_i];
      s.erase(make_tuple(weight, edge_i));
      tree.s.insert(make_tuple(weight, edge_i));
      tree.edge_weights[edge_i] = weight;
      edge_positions[edge_i] = tree_n;
    }
  }
  return tree;
}

int main()
{
  vector<Tree> trees(1);
  i64 n;
  cin >> n;
  rep(i, n - 1){
    i64 a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    edge_ends[i] = make_tuple(a, b);
    edge_indices[a].insert(i);
    edge_indices[b].insert(i);
    edge_positions[i] = 0;
    trees[0].s.insert(make_tuple(c, i));
    trees[0].edge_weights[i] = c;
  }

  i64 q;
  cin >> q;
  rep(query_i, q){
    i64 type, i, d;
    cin >> type >> i;
    --i;
    if(type == 1){
      cin >> d;
      if(edge_positions[i] != -1) trees[edge_positions[i]].change(i, d);
    }else{
      if(edge_positions[i] == -1){
        cout << -1 << endl;
      }else{
        trees.push_back(trees[edge_positions[i]].erase(sz(trees)));
      }
    }
  }
}

Submission Info

Judge Result