Submission #1177223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177223		Gray	Railway (BOI17_railway)	C++20	100 / 100	79 ms	39364 KiB

railway

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)
ll n, m, k;

struct edge{
    ll u, v, i;
};

vector<vector<ll>> A, bin;
vector<edge> e;
vector<ll> level, tin, pref;

void dfs1(ll u, ll p, ll clev, ll &timer){
    tin[u]=timer; timer++;
    level[u]=clev; bin[u][0]=p;
    for (ll i=1; i<20; i++) bin[u][i]=bin[bin[u][i-1]][i-1];
    for (auto i:A[u]){
        ll v = e[i].u^e[i].v^u;
        if (v!=p){
            dfs1(v, u, clev+1, timer);
        }
    }
}

ll lca(ll u, ll v){
    if (level[u]<level[v]) swap(u, v);
    ll jmp = level[u]-level[v];
    for (ll i=0; i<20; i++){
        if ((1<<i)&(jmp)) u=bin[u][i];
    }
    if (u==v) return u;
    for (ll i=19; i>=0; i--){
        if (bin[u][i]!=bin[v][i]) {
            u=bin[u][i]; v=bin[v][i];
        }
    }
    return bin[u][0];
}

void dfs3(ll u, ll p, vector<ll> &res){
    for (auto i:A[u]){
        ll v = e[i].u^e[i].v^u;
        if (v==p) continue;
        dfs3(v, u, res);
        // cout << u << " <-> " << v << ": " << pref[v] << ln;
        if (pref[v]>=k) res.push_back(e[i].i);
        pref[u]+=pref[v];
    }
}

void solve(){
    cin >> n >> m >> k;
    A.resize(n+1); e.resize(n); tin.resize(n+1);
    bin.resize(n+1, vector<ll>(21)); pref.resize(n+1);
    level.resize(n+1);
    for (ll i=1; i<=n-1; i++){
        ll u, v; cin >> u >> v; e[i] = {u, v, i};
        A[u].push_back(i); A[v].push_back(i);
    }
    ll timer=0; dfs1(1, 1, 0, timer);
    while (m--){
        ll a; cin >> a; vector<ll> vs(a);
        for (ll i=0; i<a; i++){
            cin >> vs[i];
        }
        sort(vs.begin(), vs.end(), [&](ll op1, ll op2){ return tin[op1]<tin[op2]; });
        // for (auto ch:vs) cout << tin[ch] << " ";
        // cout << ln;
        pref[vs[0]]++; pref[lca(vs[0], vs.back())]--;
        for (ll i=1; i<(ll)vs.size(); i++){
            pref[vs[i]]++; pref[lca(vs[i-1], vs[i])]--;
        }
    }
    vector<ll> res;
    dfs3(1, 1, res);
    sort(res.begin(), res.end());
    cout << res.size() << ln;
    for (auto ch:res) cout << ch << " ";
    cout << ln;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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