Submission #366375

#	Time	Username	Problem	Language	Result	Execution time	Memory
366375		vkgainz	Railway (BOI17_railway)	C++17	23 / 100	203 ms	24556 KiB

railway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define f first
#define s second
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define vpi vector<pi>
#define vvpi vector<vpi>
#define pb push_back
#define mp make_pair
typedef long double ld;
typedef gp_hash_table<int, null_type, hash<int>> ht;
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update> 
const int MX = 1e5 + 5;
const int LOG = 18;

vvpi adj(MX);
vvi tab(MX, vi(LOG));
vi d(MX);
vi num(MX);
vi start(MX), en(MX);
vi seg(2*MX);
int currTime;

void upd(int i, int v) {
  seg[i+=MX] += v;
  while(i>1) {
    i/=2;
    seg[i] = seg[2*i] + seg[2*i+1];
  }
}

int query(int l, int r) {
  l+=MX, r+=MX;
  int ans = 0;
  while(l<r) {
    if(l%2) ans += seg[l++];
    if(r%2) ans += seg[--r];
    l/=2, r/=2;
  }
  return ans;
}

int lca(int a, int b) {
  if(d[a] < d[b]) swap(a, b);
  for(int i=LOG-1;i>=0;i--) {
    if(a-(1<<i) >= d[b]) a = tab[a][i];
  }
  
  if(a == b) return a;
  for(int i=LOG-1;i>=0;i--) {
    if(tab[a][i] == tab[b][i]) continue;
    a = tab[a][i], b = tab[b][i];
  }
  return tab[a][0];
}

void dfs(int curr, int par) {
  tab[curr][0] = par;
  start[curr] = currTime++;
  for(auto &next : adj[curr]) {
    if(next.f == par) continue;
    d[next.f] = d[curr] + 1;
    dfs(next.f, curr);
  }
  en[curr] = currTime++;
}
void dfs2(int curr, int par) {
  for(auto &next : adj[curr]) {
    if(next.f == par) continue;
    dfs2(next.f, curr);
    num[curr] += num[next.f];
  }
}

bool isPar(int i, int j) { //is i a parent of j
  return start[i] <= start[j] && en[i] >= en[j];
}

int main() {
  int n, m, k; cin >> n >> m >> k;
  for(int i=0;i<n-1;i++) {
    int a, b; cin >> a >> b;
    --a, --b;
    adj[a].pb({b, i});
    adj[b].pb({a, i});
  }
  dfs(0, -1);
  for(int i=1;i<LOG;i++) {
    for(int j=0;j<n;j++) {
      if(tab[j][i-1] == -1) tab[j][i] = -1;
      else
        tab[j][i] = tab[ tab[j][i-1] ][i-1];
    }
  }
  while(m--) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int s; cin >> s;
    vi in(s);
    for(auto &a : in) cin >> a, --a;
    int currLca = in[0];
    upd(start[in[0]], 1);
    for(int i=1;i<in.size();i++) {
      int curr = in[i];
      if(query(start[curr], en[curr])) {
        if(!isPar(currLca, curr)) {
          ++num[currLca];
          --num[curr];
          currLca = curr;
        }
        upd(start[in[i]], 1);
        continue;
      }
      for(int i=LOG-1;i>=0;i--) {
        if(tab[curr][i] == -1 || query(start[tab[curr][i]], en[tab[curr][i]])) continue;
        curr = tab[curr][i];
      }
      upd(start[in[i]], 1);
      curr = tab[curr][0];
      ++num[in[i]];
      --num[curr];
      if(!isPar(currLca, curr)) {
        ++num[currLca];
        --num[curr];
        currLca = curr;
      }
    }
    for(auto &a : in) upd(start[a], -1);
  }
  //propagate all updates
  dfs2(0, -1);
  vi ans;
  for(int i=0;i<n;i++) {
    if(num[i] < k) continue;
    for(auto &x : adj[i]) {
      if(d[x.f] < d[i]) {
        ans.push_back(x.s + 1);
      }
    }
  }
  sort(ans.begin(), ans.end());
  cout << ans.size() << "\n";
  for(auto &a : ans) cout << a << " ";
  cout << "\n";
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=1;i<in.size();i++) {
      |                 ~^~~~~~~~~~

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