fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using PII = pair<ll, ll>;
  5. #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
  6. #define REP(i, n) FOR(i, 0, n)
  7. #define ALL(x) x.begin(), x.end()
  8. template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
  9. template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
  10. struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
  11. #ifdef DEBUG_ 
  12. #include "../program_contest_library/memo/dump.hpp"
  13. #else
  14. #define dump(...)
  15. #endif
  16. const ll INF = 1LL<<60;
  17.  
  18. struct LCA {
  19.     const int n = 0;
  20.     const int log2_n = 0;
  21.     vector<vector<int>> g;
  22.     vector<vector<int>> par;  // par[2^i上][頂点v]
  23.     vector<int> dep;
  24.  
  25.     void dfs(int v, int p, int d) {
  26.         par[0][v] = p;
  27.         dep[v] = d;
  28.         for(auto to: g[v]) {
  29.             if(to == p) continue;
  30.             dfs(to, v, d+1);
  31.         }
  32.     }
  33.  
  34.     LCA() {}
  35.     LCA(int n) : n(n), log2_n(log2(n)+1), g(n),
  36.         par(log2_n, vector<int>(n)), dep(n) {}
  37.  
  38.     void add_edge(int u, int v) {
  39.         g[u].push_back(v);
  40.         g[v].push_back(u);
  41.     }
  42.  
  43.     void build(ll root=0) {
  44.         dfs(root, -1, 0);
  45.         for(int i=0; i+1 < log2_n; ++i) {
  46.             for(int j = 0; j < n; ++j) {
  47.                 if(par[i][j] < 0) par[i+1][j] = -1;
  48.                 else par[i+1][j] = par[i][par[i][j]];
  49.             }
  50.         }
  51.     }
  52.  
  53.     int get(int u, int v) {
  54.         if(dep[u] > dep[v]) swap(u, v);
  55.         REP(i, log2_n) {
  56.             if((dep[v] - dep[u]) >> i & 1) {
  57.                 v = par[i][v];
  58.             }
  59.         }
  60.         if(u == v) return u;
  61.         for(int i=log2_n-1; i>=0; --i) {
  62.             if(par[i][u] != par[i][v]) {
  63.                 u = par[i][u];
  64.                 v = par[i][v];
  65.             }
  66.         }
  67.         return par[0][u];
  68.     }
  69.  
  70.     ll dist(ll u, ll v) {
  71.         return dep[u] + dep[v] - 2 * dep[get(u, v)];
  72.     }
  73. };
  74.  
  75. int main(void) {
  76.     ll n;
  77.     cin >> n;
  78.     LCA lca(n);
  79.     vector<vector<ll>> g(n);
  80.     REP(i, n-1) {
  81.         ll a, b;
  82.         cin >> a >> b;
  83.         a--, b--;
  84.         g[a].push_back(b);
  85.         g[b].push_back(a);
  86.         lca.add_edge(a, b);
  87.     }
  88.     lca.build();
  89.  
  90.     vector<ll> sz(n), dead(n);
  91.     auto find_centroid = [&](ll root) {
  92.         auto get_size = [&](auto &&self, ll v, ll p) -> void {
  93.             sz[v] = 1;
  94.             for(auto to: g[v]) if(to != p && !dead[to]) {
  95.                 self(self, to, v);
  96.                 sz[v] += sz[to];
  97.             }
  98.         };
  99.         get_size(get_size, root, -1);
  100.         auto dfs = [&](auto &&self, ll v, ll p) -> ll {
  101.             for(auto to: g[v]) if(to != p && !dead[to]) {
  102.                 if(sz[to] > sz[root]/2) return self(self, to, v);
  103.             }
  104.             return v;
  105.         };
  106.         return dfs(dfs, root, -1);
  107.     };
  108.  
  109.     vector<ll> par(n);
  110.     auto centroid_decomposition = [&](auto &&self, ll root, ll p) -> void {
  111.         ll c = find_centroid(root);
  112.         dead[c] = true;
  113.         par[c] = p;
  114.         for(auto to: g[c]) if(!dead[to]) {
  115.             self(self, to, c);
  116.         }
  117.         dead[c] = false;
  118.     };
  119.     centroid_decomposition(centroid_decomposition, 0, -1);
  120.  
  121.     vector<ll> col(n);
  122.     vector<set<PII>> dist_to_white(n);
  123.     auto paint = [&](ll v) {
  124.         ll u = v;
  125.         while(u != -1) {
  126.             if(col[v] == 0) dist_to_white[u].insert({lca.dist(u, v), v});
  127.             else dist_to_white[u].erase({lca.dist(u, v), v});
  128.             u = par[u];
  129.         }
  130.         col[v] = 1-col[v];
  131.     };
  132.     auto query = [&](ll v) {
  133.         ll u = v, ret = INF;
  134.         while(u != -1) {
  135.             if(dist_to_white[u].size()) {
  136.                 chmin(ret, dist_to_white[u].begin()->first + lca.dist(u, v));
  137.             }
  138.             u = par[u];
  139.         }
  140.         return ret == INF ? -1 : ret;
  141.     };
  142.  
  143.     ll q;
  144.     cin >> q;
  145.     REP(i, q) {
  146.         ll t, v;
  147.         cin >> t >> v;
  148.         v--;
  149.         if(t == 0) paint(v);
  150.         else cout << query(v) << "\n";
  151.     }
  152.     cout << flush;
  153.  
  154.     return 0;
  155. }
Runtime error #stdin #stdout #stderr 0s 4148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/QhYs5x
problem QTREE5, based on SPOJ submission 25486165 (CPP14), 2020-03-03 07:32:17
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!