Submission #535841

#	Time	Username	Problem	Language	Result	Execution time	Memory
535841		nemethm	Railway (BOI17_railway)	C++17	23 / 100	1088 ms	75704 KiB

railway

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <list>

using namespace std;
using ll = long long int;

vector<int> g[100100];
int dp[100100][30];
map<int, int> in[100100], out[100100];
int level[100100];
map<pair<int,int>,int> id;
vector<int> ans;
int k;
void dfs(int node, int prev = 0, int l = 1){
  level[node] = l;
  dp[node][0] = prev;
  for(auto i : g[node]){
    if(i != prev){
      dfs(i, node, l + 1);
    }
  }
}

int jump(int a, int x){
    for(int i = 0; i < 20; ++i){
        if((x >> i) & 1){
            a = dp[a][i];
        }
    }
    return a;
}

int lca(int a, int b){
    if(level[a] < level[b]) swap(a,b);
    a = jump(a, level[a] - level[b]);
    if(a == b) return a;
    for(int i = 20; i >= 0; --i){
        if(dp[a][i] != dp[b][i]){
            a = dp[a][i], b = dp[b][i];
        }
    }
    return dp[a][0];
}

pair<map<int,int>,int> solve(int node, int prev = -1){
  map<int,int> open; int ctr = 0;
  for(auto i : g[node]){
    if(i != prev){
      auto a = solve(i, node);
      if(a.first.size() >= k){
        ans.push_back(id[{node, i}]);
      }
      //if(a.first.size() > open.size()) swap(a.first, open);
      for(auto& j : a.first){
        if(open[j.first] == 0) ++ctr;
        open[j.first] += j.second;
      }
    }
  }
  for(auto& i : out[node]){
    open[i.first] -= i.second;
    if(open[i.first] == 0) open.erase(i.first);
  }
  for(auto& i : in[node]){
    open[i.first] += i.second;
    if(open[i.first] == 0) open.erase(i.first);
  }
    /*cerr << node << ": ";
    for(auto i : open){
      cerr << i.first << " " << i.second << endl;
    }
    cerr << endl;*/
  return {open, ctr};
}

int main()
{
  int n, m;
  cin >> n >> m >> k;
  for(int i = 0; i < n - 1; ++i){
    ll a, b;
    cin >> a >> b;
    g[a].emplace_back(b), g[b].emplace_back(a);
    id[{a,b}] = id[{b,a}] = i + 1;
  }
  dfs(1);
  for(int i = 1; i < 20; ++i){
    for(int node = 1; node <= n; ++node){
      dp[node][i] = dp[dp[node][i - 1]][i - 1];
    }
  }
  while(m--){
    int meret;
    cin >> meret;
    vector<int> v(meret);
    for(auto& i : v) cin >> i;
    for(int i = 1; i < meret; ++i){
      int c = lca(v[i], v[0]);
      //if(c != v[i])
        in[v[i]][m]++;
     // if(c != v[0])
        in[v[0]][m]++;
      out[c][m] += 2;
    }
  }
  solve(1);
  sort(begin(ans), end(ans));
  cout << ans.size() << endl;
  for(auto& i : ans){
    cout << i << " ";
  }
  if(ans.size() > 0)
    cout << endl;
  return 0;
}

Compilation message (stderr)

railway.cpp: In function 'std::pair<std::map<int, int>, int> solve(int, int)':
railway.cpp:58:25: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |       if(a.first.size() >= k){
      |          ~~~~~~~~~~~~~~~^~~~

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