Submission #404451

#	Time	Username	Problem	Language	Result	Execution time	Memory
404451		Aryan_Raina	Railway (BOI17_railway)	C++14	100 / 100	283 ms	38940 KiB

railway

#include <bits/stdc++.h>
using namespace std; 

#define int int64_t
#define ld long double
#define ar array

const int INF = 1e17;
const int MOD = 1e9+7;

template<class T> struct SegmentTree {
   int n; vector<T> values; 
   T IDENTITY = 0;
   SegmentTree(int n, int id = 0) : n(n), values(2*n, IDENTITY = id) {}
   T calc_op(T a, T b) { return a + b; }
   void modify(int i, T v) {
      for (values[i += n] = v; i >>= 1; ) 
         values[i] = calc_op(values[2*i], values[2*i + 1]);
   }
   T calc(int l, int r) {
      T rans = IDENTITY, lans = IDENTITY;
      for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
         if (l & 1) lans = calc_op(lans, values[l++]);
         if (r & 1) rans = calc_op(values[--r], rans);
      }
      return calc_op(lans, rans);
   }
};

const int MXN = 1e5+9;
vector<ar<int, 2>> g[MXN];
int N, M, K, up[20][MXN], depth[MXN], val[MXN];
int tin[MXN], tout[MXN], timer = 0;
vector<int> ans;

void dfs(int u, int pu) {
   up[0][u] = pu; tin[u] = timer++;
   for (int i = 1; i < 20; i++)
      up[i][u] = up[i-1][up[i-1][u]];

   for (auto v : g[u]) if (v[1] != pu) {
      depth[v[1]] = depth[u] + 1;
      dfs(v[1], u);
   }

   tout[u] = timer;
}

int lca(int u, int v) {
   if (depth[u] > depth[v]) swap(u, v);
   for (int i = 19; i >= 0; --i)
      if ((depth[v] - depth[u]) >> i & 1)
         v = up[i][v];

   if (u == v) return u;

   for (int i = 19; i >= 0; --i) 
      if (up[i][u] != up[i][v])
         u = up[i][u], v = up[i][v];

   return up[0][u];
}

void magic(int u, int pu) {
   for (auto v : g[u]) if (v[1] != pu) {
      magic(v[1], u);
      if (val[v[1]] >= K) ans.push_back(v[0]);
      val[u] += val[v[1]];
   }
}

int32_t main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   cin >> N >> M >> K;
   for (int i = 0; i < N - 1; ++i) {
      int a, b; cin >> a >> b; --a, --b;
      g[a].push_back({i, b}); g[b].push_back({i, a});
   }

   dfs(0, 0);

   SegmentTree<int> seg(N, 0);

   while (M--) {
      int s; cin >> s;
      vector<int> shit(s);
      for (int &i : shit) cin >> i, --i;

      sort(shit.begin(), shit.end(), [&](int i, int j) { return depth[i] > depth[j]; });

      int baap = shit.back();
      for (int i : shit) baap = lca(baap, i);

      for (int i : shit) if (!seg.calc(tin[i], tout[i])) {
         int x = i;
         
         // get first top thingie with already +1 coz of this guy
         for (int j = 19; j >= 0; --j)
            if (depth[baap] < depth[up[j][x]] && !seg.calc(tin[up[j][x]], tout[up[j][x]]))
               x = up[j][x];
         x = up[0][x];

         val[i]++; val[x]--;
         seg.modify(tin[i], 1);
      }

      for (int i : shit) seg.modify(tin[i], 0);
   }   

   magic(0, 0);

   sort(ans.begin(), ans.end());
   
   cout << ans.size() << '\n';
   for (int i : ans) cout << i + 1 << ' ';
}  
 

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25