Submission #394089

#	Time	Username	Problem	Language	Result	Execution time	Memory
394089		Sundavar	Railway (BOI17_railway)	C++14	100 / 100	366 ms	37000 KiB

railway

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int X = 18;
struct node{
    vector<pii> to;
    vector<int> father = *new vector<int>(X);
    int with = -1, cnt = 0, d = -1, out = 0;
    bool was = false;
};
vector<node> graph;
bool sortFunc(int a, int b){
    return graph[a].out < graph[b].out;
}
int in = 0;
void DFS(int curr, int father){
    graph[curr].was = true;
    graph[curr].father[0] = father;
    graph[curr].d = graph[father].d + 1;
    for(int i = 1; i < X; i++)
        graph[curr].father[i] = graph[graph[curr].father[i-1]].father[i-1];
    for(pii& to : graph[curr].to)
        if(!graph[to.first].was) 
            DFS(to.first, curr), graph[to.first].with = to.second;
    graph[curr].out = in++;
    graph[curr].was = false;
}
int lca(int a, int b){
    if(graph[a].d < graph[b].d) swap(a,b);
    for(int i = X-1; i >= 0; i--)
        if(graph[graph[a].father[i]].d >= graph[b].d)
            a = graph[a].father[i];
    if(a == b) return a;
    for(int i = X-1; i>= 0; i--)
        if(graph[a].father[i] != graph[b].father[i])
            a = graph[a].father[i], b = graph[b].father[i];
    return graph[a].father[0];
}
int n,m,k;
vector<int> sol;
int count(int curr){
    graph[curr].was = true;
    for(pii& to : graph[curr].to)
        if(!graph[to.first].was) graph[curr].cnt += count(to.first);
    if(graph[curr].cnt >= k)
        sol.push_back(graph[curr].with);
    return graph[curr].cnt;
}
int main(){
    cin>>n>>m>>k;
    graph.resize(n+1);
    for(int i = 1; i < n; i++){
        int a,b;
        cin>>a>>b;
        graph[a].to.push_back({b,i});
        graph[b].to.push_back({a,i});
    }
    DFS(1, 0);
    while(m--){
        int x;
        cin>>x;
        vector<int> here(x);
        for(int& a : here) cin>>a, graph[a].cnt++;
        sort(here.begin(), here.end(), sortFunc);
        int l = here[0];
        for(int i = 0; i < x-1; i++)
            graph[lca(here[i], here[i+1])].cnt--, l = lca(l, here[i+1]);
        graph[l].cnt--;
    }
    count(1);
    cout<<sol.size()<<"\n";
    sort(sol.begin(), sol.end());
    for(int& a : sol) cout<<a<<" ";
    cout<<"\n";
}

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