Submission #1276108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276108		Ludissey	Railway (BOI17_railway)	C++20	100 / 100	136 ms	59904 KiB

railway

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

const int LOG=24;

vector<vector<int>> neigh;
vector<vector<int>> clr_group;
vector<int> val;
vector<int> in;
vector<int> ans;
vector<vector<int>> parent;
vector<int> depth;
map<pair<int,int>,int> mp;
int n,m,k;
int timer=0;
int dfs(int x, int p){
    int sm=val[x];
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        sm+=dfs(u,x);
    }
    if(sm>=k){
        ans.push_back(mp[{x,p}]);
    }
    return sm;
} 

int lca(int a, int b){
    if(depth[b]<depth[a]) swap(a,b);
    int d=depth[b]-depth[a];
    for (int j = LOG-1; j >= 0; j--)
    {
        if(d&(1<<j)) b=parent[b][j];
    }
    if(a==b) return a;
    for (int j = LOG-1; j >= 0; j--)
    {
        if(parent[a][j]!=parent[b][j]) b=parent[b][j], a=parent[a][j];
    }
    return parent[a][0];
}

void setup_lca(int x, int p){
    parent[x][0]=p;
    in[x]=timer++;
    for (int j = 1; j < LOG; j++) parent[x][j]=parent[parent[x][j-1]][j-1];
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        depth[u]=depth[x]+1;
        setup_lca(u,x);
    }
    return;
} 

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> k;
    neigh.resize(n);
    parent.resize(n,vector<int>(LOG,0));
    depth.resize(n);
    val.resize(n,0);
    in.resize(n);
    clr_group.resize(m);
    for (int i = 0; i < n-1; i++)
    {
        int a,b; cin >> a >> b;
        neigh[a-1].push_back(b-1);
        neigh[b-1].push_back(a-1);
        mp[{a-1,b-1}]=i;
        mp[{b-1,a-1}]=i;
    }
    for (int i = 0; i < m; i++)
    {
        int nm; cin >> nm; 
        while(nm--){
            int a; cin >> a; a--;
            clr_group[i].push_back(a);
        }
    }
    setup_lca(0,0);
    for (int i = 0; i < m; i++)
    {
        sort(all(clr_group[i]),[](int a, int b){ return in[a]<in[b]; });
        for (int j = 0; j < sz(clr_group[i]); j++)
        {
            val[clr_group[i][j]]++;
            val[lca(clr_group[i][(j-1+sz(clr_group[i]))%sz(clr_group[i])],clr_group[i][j])]--;
        }
    }
    
    dfs(0,0);
    sort(all(ans));
    cout << sz(ans) << "\n";
    for (auto u : ans) cout << u+1 << " ";
    
    return 0;
}

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