Submission #284340

#	Time	Username	Problem	Language	Result	Execution time	Memory
284340		AlexLuchianov	Railway (BOI17_railway)	C++14	100 / 100	297 ms	25076 KiB

railway

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int const lgmax = 20;

std::vector<std::pair<int,int>> g[1 + nmax];
int ord[1 + nmax], ptr = 0;
int level[1 + nmax];
int far[1 + lgmax][1 + nmax];

void computefar(int n) {
  for(int h = 1; h <= lgmax; h++)
    for(int i = 1;i <= n; i++)
      far[h][i] = far[h - 1][far[h - 1][i]];
}

int getlca(int x, int y) {
  if(level[x] < level[y])
    std::swap(x, y);
  for(int h = lgmax; 0 <= h; h--)
    if(level[y] + (1 << h) <= level[x])
      x = far[h][x];
  if(x == y)
    return x;
  else
    for(int h = lgmax; 0 <= h; h--)
      if(far[h][x] != far[h][y]) {
        x = far[h][x];
        y = far[h][y];
      }
  return far[0][x];
}

int ref[1 + nmax];

void dfs(int node, int parent) {
  ord[node] = ++ptr;
  level[node] = level[parent] + 1;
  far[0][node] = parent;
 
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h].first;
    if(to != parent) {
      ref[to] = g[node][h].second;
      dfs(to, node);
    }
  }
}

int dp[1 + nmax];
void update(int a, int b) {
  int lca = getlca(a, b);
  dp[a]++;
  dp[b]++;
  dp[lca] -= 2;
}

bool compare(int x, int y) {
  return ord[x] < ord[y];
}

void refresh(int node, int parent) {
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h].first;
    if(to != parent) {
      refresh(to, node);
      dp[node] += dp[to];
    }
  }
}

int main() {
  int n, m, k;
  std::cin >> n >> m >> k;
  for(int i = 1;i < n; i++) {
    int x, y;
    std::cin >> x >> y;
    g[x].push_back({y, i});
    g[y].push_back({x, i});
  }
  dfs(1, 0);
  computefar(n);
  
  for(int i = 1;i <= m; i++) {
    std::vector<int> aux;
    int _count;
    std::cin >> _count;
    for(int i = 0; i < _count; i++) {
      int val;
      std::cin >> val;
      aux.push_back(val);
    }
    std::sort(aux.begin(), aux.end(), compare);
    for(int i = 0; i < aux.size(); i++) 
      update(aux[i], aux[(i + 1) % aux.size()]);
  }

  refresh(1, 0);
  std::vector<int> sol;
  for(int i = 2;i <= n; i++)
    if(k * 2 <= dp[i])
      sol.push_back(ref[i]);
  std::cout << sol.size() << '\n';
  std::sort(sol.begin(), sol.end());
  for(int i = 0; i < sol.size(); i++)
    std::cout << sol[i] << " ";
  return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
railway.cpp: In function 'void refresh(int, int)':
railway.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0; i < aux.size(); i++)
      |                    ~~^~~~~~~~~~~~
railway.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i = 0; i < sol.size(); i++)
      |                  ~~^~~~~~~~~~~~

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