Submission #886652

#	Time	Username	Problem	Language	Result	Execution time	Memory
886652		erray	Grapevine (NOI22_grapevine)	C++17	100 / 100	906 ms	109932 KiB

Main

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B>
string to_string(pair<A, B>);
string to_string(string S) {
  return '"' + S + '"';
}
string to_string(const char* c) {
  return to_string(string(c));
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template<size_t T>
string to_string(bitset<T> bs) {
  return bs.to_string();
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < int(v.size()); ++i) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(v[i]);
  }
  return res + "}";
}
template<typename T>
string to_string(T v) {
  string res = "{";
  for (auto e : v) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(e);
  }
  return res + "}";
}
template<typename A, typename B>
string to_string(pair<A, B> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
void debug_out() {
  cerr << endl;
}
template<typename H, typename... T>
void debug_out(H head, T... tail) {
  cerr << "  " << to_string(head);
  debug_out(tail...);
}

#ifdef DEBUG 
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) 
#else 
  #define debug(...) void(37)
#endif


const int BLOCK = 16; // divide smaller seg trees onto blocks if it gets TLE
const long long inf = 1LL << 55;
#define def int mid = (l + r) >> 1, rv  = v + ((mid - l + 1) << 1)
#define pull(v) tree[v].mn = min((l < mid) || act[l] ? tree[v + 1].mn : inf, (mid + 1 < r) || act[r] ? tree[rv].mn : inf) //change to if statements if it gets TLE
#define push(v) \
if (tree[v].tag != 0) { \
  tree[v + 1].modify(tree[v].tag); \
  tree[rv].modify(tree[v].tag); \
  tree[v].tag = 0; \
}

struct node {
  long long mn = 0;
  long long tag = 0;
  void modify(long long x) {
    mn += x;
    tag += x;
  }
};
struct SegTree {
  vector<node> tree;
  vector<bool> act;
  int n;
  void modify(int v, int l, int r, int ll, int rr, int x) {
    if (l >= ll && rr >= r) {
      tree[v].modify(x);
      return;
    }
    def;
    push(v);
    if (ll <= mid) {
      modify(v + 1, l, mid, ll, rr, x);
    } 
    if (mid < rr) {
      modify(rv, mid + 1, r, ll, rr, x);
    }
    pull(v);
  }
  int path(int v, int l, int r, int p) {
    if (l == r) {
      return v;
    }
    def;
    push(v);
    int res = -1;
    if (p <= mid) {
      res = path(v + 1, l, mid, p);
    } else {
      res = path(rv, mid + 1, r, p);
    }
    pull(v);
    //debug(v, l, r, tree[v].mn);
    return res;
  }
  void build(int v, int l, int r, vector<int>& a) {
    if (l == r) {
      tree[v].mn = a[l];
      return;
    }
    def;
    build(v + 1, l, mid, a);
    build(rv, mid + 1, r, a);
  }
  SegTree(int _n, vector<int>& a) : n(_n) {
    tree.resize(2 * n);
    act.resize(n);
    build(0, 0, n - 1, a); //same as 137
  }
  SegTree(int _n) : n(_n) {
    tree.resize(2 * n);
    if (n > 1) tree[0].mn = inf;
    act.resize(n);
  }
  SegTree() { } 
  long long mn() {
    return (n > 1 || act[0] ? tree[0].mn : inf);
  }
  long long dist(int i) {
    return tree[path(0, 0, n - 1, i)].mn; 
  }
  void change(int i) {
    act[i] = !act[i];
    path(0, 0, n - 1, i);
  }
  void modify(int ll, int rr, int x) {
    modify(0, 0, n - 1, ll, rr, x); //change variables to globals if it get's tle 
  }
};
#undef def
#undef pull
#undef push

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, QQ;
  cin >> N >> QQ;
  vector<vector<int>> g(N);
  vector<int> V(N - 1), U(N - 1), W(N - 1);
  for (int i = 0; i < N - 1; ++i) {
    cin >> V[i] >> U[i] >> W[i];
    --V[i], --U[i];
    g[V[i]].push_back(U[i]);
    g[U[i]].push_back(V[i]);
  }
  vector<int> tin(N, -1), tout(N), d(N);
  int tt = 0;
  function<void(int)> Dfs = [&](int v) {
    tin[v] = tt++;
    for (auto u : g[v]) {
      if (tin[u] == -1) {
        d[u] = d[v] + 1;
        Dfs(u);
      }
    }
    tout[v] = tt - 1;
  };
  Dfs(0);
  debug(tin, tout, d);
  vector<int> size(N);
  for (int i = 0; i < N; ++i) {
    size[i] = tout[i] - tin[i] + 1;
  }
  vector<int> par(N, -1);
  vector<int> cent_d(N);
  function<void(int, int)> Centroid = [&](int v, int from) {
    int to = -1;
    for (auto u : g[v]) {
      if (size[u] * 2 > size[v]) {
        to = u;
        break;
      }
    }
    if (to == -1) {
      par[v] = from;
      size[v] = 0;
      cent_d[v] = (from == -1 ? 0 : cent_d[from] + 1);
      for (auto u : g[v]) {
        if (size[u] > 0) {
          Centroid(u, v);
        }
      }
    } else {
      size[v] -= size[to];
      size[to] += size[v];
      Centroid(to, from);
    }
  };
  Centroid(0, -1);
  debug(par, cent_d);
  vector<int> inv_in(N);
  for (int i = 0; i < N; ++i) {
    inv_in[tin[i]] = i;
  }
  vector<vector<int>> inv_out(N);
  for (int i = 0; i < N; ++i) {
    inv_out[tout[i]].push_back(i);
  } 
  vector<vector<int>> in(N), out(N); //change sizes to const if it gets tle 
  for (int v = 0; v < N; ++v) {
    in[v].resize(cent_d[v] + 1);
    out[v].resize(cent_d[v] + 1);
  }
  vector<vector<int>> st_inds(N);
  for (auto v : inv_in) {
    int x = v;
    while (v != -1) {
      in[x][cent_d[v]] = int(st_inds[v].size());
      st_inds[v].push_back(tin[x]);
      v = par[v];
    }
  }
  vector<int> pt(N);
  for (int foo = 0; foo < N; ++foo) for (auto v : inv_out[foo]) {
    int p = v;
    while (p != -1) {
      int s = int(st_inds[p].size());
      while (pt[p] + 1 < s && st_inds[p][pt[p] + 1] <= tout[v]) {
        ++pt[p];
      }
      out[v][cent_d[p]] = pt[p];
      p = par[p];
    }
  }
  debug(in, out);
  vector<SegTree> st(N);
  for (int i = 0; i < N; ++i) {
    debug(i, st_inds[i]);
    st[i] = SegTree(int(st_inds[i].size()));
  }
  
  debug(inv_in);
  auto Lca = [&](int a, int b) {
    if (cent_d[a] > cent_d[b]) {
      swap(a, b);
    }
    while (cent_d[b] > cent_d[a]) {
      b = par[b];
    }
    while (a != b) {
      a = par[a], b = par[b];
    }
    return a;
  };
  auto Par = [&](int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tin[b];
  };
  
  auto Upd = [&](int a, int b, int w) {
    debug(a, b, w);
    int v = Lca(a, b);
    if (d[a] > d[b]) {
      swap(a, b);
    }
    int sub = b;
    while (v != -1) {
      int L = in[sub][cent_d[v]];
      int R = out[sub][cent_d[v]];
      bool inc = !Par(sub, v);
      debug(v, st_inds[v], L, R, w, inc); 
      //reduce two updates to one with constants if it get's tle 
      if (inc) { 
        st[v].modify(L, R, w);
      } else {
        if (L > 0) {
          st[v].modify(0, L - 1, w);
        }
        if (R + 1 < st[v].n) {
          st[v].modify(R + 1, st[v].n - 1, w);
        }
      }
      v = par[v];
    }
  };
  vector<int> new_W(N);
  for (int i = 0; i < N - 1; ++i) {
    if (d[V[i]] > d[U[i]]) {
      swap(V[i], U[i]);
    }
    new_W[U[i]] = W[i];
    Upd(V[i], U[i], W[i]);
  }
  /*
  for (int v = 0; v < N; ++v) {
    int p = v;
    while (p != -1) {
      debug(p, v, st[p].dist(in[v][cent_d[p]]));
      p = par[p];
    }
  }
  */
  swap(new_W, W);
  debug(W);
  int c = 0;
  vector<bool> act(N);
  while (QQ--) {
    int T;
    cin >> T;
    if (T == 1) {
      int Q;
      cin >> Q;
      --Q;
      int v = Q;
      debug(Q);
      long long ans = inf;
      while (v != -1) {
        debug(v, st[v].dist(in[Q][cent_d[v]]), st[v].mn());
        ans = min(ans, st[v].dist(in[Q][cent_d[v]]) + st[v].mn());
        v = par[v];
      }
      cout << (c == 0 ? -1LL : ans) << '\n';
    } else if (T == 2) {
      int U_i;
      cin >> U_i;
      --U_i;
      int v = U_i;
      c += (act[v] ? -1 : +1);
      act[v] = !act[v];
      while (v != -1) {
        debug(v, in[U_i][cent_d[v]]);
        st[v].change(in[U_i][cent_d[v]]);
        v = par[v];
      }
    } else {
      int A, B, W_i;
      cin >> A >> B >> W_i;
      --A, --B;
      if (d[A] > d[B]) {
        swap(A, B);
      }
      debug(A, B, W_i - W[B]);
      Upd(A, B, W_i - W[B]);
      W[B] = W_i;
    }
  }
}

• Subtask 1: 6 / 6
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 18 / 18
• Subtask 6: 32 / 32