Submission #1097560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097560		BLOBVISGOD	Railway (BOI17_railway)	C++17	7 / 100	89 ms	27336 KiB

railway

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,m,k; cin >> n >> m >> k;

    map<pair<int,int>,int> to_input;
    vvi adj(n);
    rep(i,0,n-1){
        int u,v; cin >> u >> v;
        u--,v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
        if (u>v) swap(u,v);
        to_input[{u,v}] = i;
    }   

    int cc = 0;
    vi d(n), vis(n), dfsord(n);
    vvi par(__lg(n)+1,vi(n));
    auto dfs = [&](int at, int dep, auto&& self) -> void {
        vis[at] = 1;
        d[at] = dep;
        for(auto to : adj[at]) if (!vis[to]){
            par[0][to] = at;
            self(to,dep+1,self);
        }
        dfsord[at] = cc++;
    };
    dfs(0,0,dfs);
    rep(i,0,__lg(n)) rep(j,0,n) par[i+1][j] = par[i][par[i][j]];
    auto jmp = [&](int at, int k) -> int {
        for(int i = 0; k; i++,k/=2) if (k&1) at = par[i][at];
        return at;
    };

    auto lca = [&](int u, int v) -> int {
        if (d[u] < d[v]) swap(u,v);
        u = jmp(u,d[u]-d[v]);
        if (u==v) return u;
        for(int i = __lg(n); i; --i) 
            if (par[i][u] != par[i][v])
                u = par[i][u], v = par[i][v];
        return par[0][u];
    };

    vi cnt(n);
    auto addpath = [&](int at, int rt) -> void {
        if (d[at] <= d[rt]) return;
        cnt[at]++;
        cnt[rt]--;
    };

    rep(i,0,m){
        int t; cin >> t;
        vi a(t);
        rep(i,0,t) cin >> a[i], a[i]--;
        if (t<2) continue;
        sort(all(a),[&](int u, int v){
            return dfsord[u] < dfsord[v];
        });

        int llca = lca(a[0],a[1]);
        addpath(a[0],llca);
        addpath(a[1],llca);

        rep(i,2,t){
            int p1 = a[i-1], p2 = a[i];
            int curlca = lca(p1,p2);
            int mlca = lca(curlca,llca);
            addpath(p2,curlca);
            if (mlca != llca){
                addpath(llca,mlca);
                llca = mlca;
            }
        }
    }

    fill(all(vis),0);
    auto prop = [&](int at, auto&& self) -> void {
        vis[at] = 1;
        for(auto to : adj[at]) if (!vis[to]){
            self(to,self);
            cnt[at] += cnt[to];
        }
    };

    prop(0, prop);

    vi ans;

    rep(i,0,n) if (cnt[i] >= k) ans.push_back(i);
    cout << sz(ans) << '\n';
    for(auto c : ans) {
        int ot = par[0][c];
        if (c > ot) swap(c,ot);
        cout << to_input[{c,ot}]+1 << ' ';
    }
    cout << '\n';
}

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