Submission #1275544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275544		Ludissey	Railway (BOI17_railway)	C++20	23 / 100	1098 ms	86888 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_node;   
vector<vector<int>> clr_rm;   
vector<vector<int>> clr_group;
vector<int> ans;
vector<vector<int>> parent;
vector<int> depth;
map<pair<int,int>,int> mp;
int n,m,k;

map<int,int> dfs(int x, int p){
    vector<map<int,int>> vec(1);
    for (auto u : clr_node[x]) vec[0][u]=1;
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        vec.push_back(dfs(u,x));
    }
    sort(all(vec),[](map<int,int> a, map<int,int> b){ return sz(a)<sz(b); });
    for (int i = 1; i < sz(vec); i++)
    {
        for (auto u : vec[i]) vec[0][u.first]=1;
    }
    for (auto u : clr_rm[x]) vec[0].erase(u);
    if(sz(vec[0])>=k){
        ans.push_back(mp[{x,p}]);
    }
    return move(vec[0]);
} 

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;
    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);
    clr_node.resize(n);
    clr_rm.resize(n);
    parent.resize(n,vector<int>(LOG,0));
    depth.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_node[a].push_back(i);
            clr_group[i].push_back(a);
        }
    }
    setup_lca(0,0);
    for (int i = 0; i < m; i++)
    {
        int lc=clr_group[i][0];
        for (int j = 0; j < sz(clr_group[i]); j++)
        {
            lc=lca(lc,clr_group[i][j]);
        }
        clr_rm[lc].push_back(i);
    }
    
    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: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25