Submission #1096003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096003		giaminh2211	Railway (BOI17_railway)	C++14	100 / 100	96 ms	25804 KiB

railway

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
using ll=long long;

const int N=1e5+13;
int n, m, k;
vector<pair<int, int>> g[N];
int s, x, y;
int tdfs;
int tin[N];
int st[N][20];
int f[N];
int h[N];

void pre_dfs(int v, int par){
    ++tdfs;
    tin[v]=tdfs;
    for(auto c: g[v]){
        if(c.fi==par) continue;
        h[c.fi]=h[v]+1;
        st[c.fi][0]=v;
        for(int j=1; j<20; j++){
            st[c.fi][j]=st[st[c.fi][j-1]][j-1];
        }
        pre_dfs(c.fi, v);
    }
}

int lca(int u, int v){
    if(h[u] > h[v]) swap(u, v);
    int k=h[v]-h[u];
    for(int j=0; j<20; j++){
        if(k >> j & 1){
            v=st[v][j];
        }
    }
    if(u==v) return v;
    for(int j=19; j>=0; j--){
        if(st[u][j]!=st[v][j]){
            u=st[u][j];
            v=st[v][j];
        }
    }
    return st[u][0];
}

vector<int> v;
vector<int> ans;

void scan(){
    cin >> n >> m >> k;
    for(int i=1; i<n; i++){
        cin >> x >> y;
        g[x].emplace_back(y, i);
        g[y].emplace_back(x, i);
    }
    pre_dfs(1, 1);
}

void dfs(int v, int par){
    for(auto c: g[v]){
        if(c.fi==par) continue;
        dfs(c.fi, v);
        f[v]+=f[c.fi];
        if(f[c.fi] >= 2*k){
            ans.push_back(c.se);
        }
    }
}

void solve(){
    while(m--){
        v.clear();
        cin >> s;
        while(s--){
            cin >> x;
            v.push_back(x);
        }
        sort(begin(v), end(v), [&](int x, int y){
           return tin[x] < tin[y];
        });
        for(int i=0; i<v.size(); i++){
            x=v[i];
            y=v[(i+1)%v.size()];
            int sus=lca(x, y);
            //cout << x << ' ' << y << ' ' << sus << '\n';
            ++f[x];
            ++f[y];
            f[sus]-=2;
        }
    }
    dfs(1, 1);
    sort(begin(ans), end(ans));
    cout << ans.size() << '\n';
    for(int c: ans){
        cout << c << ' ';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

Compilation message (stderr)

railway.cpp: In function 'void solve()':
railway.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int i=0; i<v.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