| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1038573 | krakenn | Railway (BOI17_railway) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ld long double
#define ii pair<int,int>
#define pll pair<ll,ll>
#define lll tuple<ll,ll,ll>
#define iii tuple<int,int,int>
#define forn(i,a,b) for (int i = a; i <= b; i++)
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define dbg(v) \
cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
#define m1(x) template<class T, class... U> void x(T&& a, U&&... b)
#define m2(x) (int[]){(x forward<U>(b),0)...}
m1(out) { cout << forward<T>(a); m2(cout << " " <<); cout << "\n"; }
m1(in) { cin >> forward<T>(a); m2(cin >>); }
// nmax = 1e5
int tin[100004], tout[100004], timer = 0, p_edge[100004];
vector<ii> adj[100004];
void dfs2(int node = 1, int parent = 0) {
tin[node] = ++timer;
for (pair<int, int> &i : adj[node])
if (i.first != parent) {
p_edge[i.first] = i.second;
dfs2(i.first, node);
}
tout[node] = timer;
}
template <typename T> class BinaryLift {
public:
int lgmax = 20;
int nmax = 0;
vector<vector<int>> far;
vector<int> level;
BinaryLift(int n): lgmax(__bit_width(n)+1), nmax(n), far(lgmax+1, vector<int>(nmax+3, 0)),
level(nmax+3) {
level[1] = 0;
dfs(1, -1);
for(int h = 1; h <= lgmax; h++) {
for(int i = 1; i <= nmax; i++) {
far[h][i] = far[h - 1][far[h - 1][i]];
}
}
}
int getLca(int x, int y) {
if(level[x] < level[y]) swap(x, y);
for(int h = lgmax; h >= 0; h--)
if(level[y] + (1 << h) <= level[x]){
x = far[h][x];
}
if(x == y) return x;
for(int h = lgmax; h >= 0; h--)
if(far[h][x] != far[h][y]) {
x = far[h][x];
y = far[h][y];
}
return far[0][x];
}
void dfs(int now, int p) {
for(auto &[v, cost]: adj[now]) {
if(v != p) {
// init
far[0][v] = now;
level[v] = level[now] + 1;
dfs(v, now);
}
}
}
int kth(int node, int k){
// beware k too high!
int x = node;
for(int h = lgmax; h >= 0; h--){
if(k & (1 << h)){
x = far[h][x];
}
}
return x;
}
};
class FenwickTree {
private:
vector<ll> f;
public:
int LSOne(int i){return (i&(-i));}
FenwickTree(int n){
f.assign(n+1, 0);
}
void update(int x, ll v){
for(int i = x; i <= (int)f.size()-1; i += LSOne(i)){
f[i] += v;
}
}
void update(int l, int r, ll v){
update(l, v);
update(r+1, -v);
}
ll print(int k){
ll sum = 0;
for(int i = k; i >= 1; i -= LSOne(i)){
sum += f[i];
}
return sum;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m,k; in(n,m,k);
forn(i,1,n-1){
int a, b; in(a, b);
adj[a].emplace_back(b, i);
adj[b].emplace_back(a, i);
}
dfs2();
BinaryLift<int> BL(n);
FenwickTree FT(n);
forn(i,1,m){
int g; in(g);
vector<int> q;
forn(j,1,g){
int temp; in(temp);
q.emplace_back(temp);
}
sort(q.begin(), q.end(), [](int a, int b){return tin[a] < tin[b];});
if(g==1) continue;
q.emplace_back(q[0]);
forn(j,1,sz(q)-1){
int c=tin[q[j-1]], d = tin[q[j]];
int lc = BL.getLca(q[j], q[j-1]);
int e = tin[lc];
FT.update(c, 1);
FT.update(d, 1);
FT.update(e, -2);
}
}
vector<int> fin;
const int trg = 2*k;
forn(i,2,n){
int res = FT.print(tout[i])-FT.print(tin[i]-1);
if(res>=2*k) fin.emplace_back(p_edge[i]);
}
sort(fin.begin(), fin.end());
out(sz(fin));
forn(i,0,sz(fin)-1){
cout << fin[i] << " \n"[i==sz(fin)-1];
}
return 0;
}