Submission #1084594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084594		tuannm	Railway (BOI17_railway)	C++17	100 / 100	63 ms	31692 KiB

railway

#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 1e5 + 1;
const string NAME = "";
int n, m, k;
vector<ii> adj[N];
int in[N], out[N], cnt, euler[20][2 * N], lg[2 * N];
int sum[N], stk[N];
vector<int> ans;

int min_by_time(int u, int v){
    return (in[u] < in[v] ? u : v);
}

int LCA(int u, int v){
    int L = min(in[u], in[v]);
    int R = max(out[u], out[v]);
    int k = lg[R - L + 1];
    return min_by_time(euler[k][L], euler[k][R - (1 << k) + 1]);
}

void dfs(int u = 1, int p = 0){
    in[u] = ++cnt;
    euler[0][cnt] = u;
    for(auto [v, i] : adj[u]){
        if(v == p)
            continue;
        dfs(v, u);
        euler[0][++cnt] = u;
    }
    out[u] = cnt;
}

void DFS(int u = 1, int p = 0){
    for(auto [v, i] : adj[u]){
        if(v == p)
            continue;
        DFS(v, u);
        if(sum[v] >= k)
            ans.pb(i);
        sum[u] += sum[v];
    }
}

void init(){
    dfs();

    for(int i = 2; i <= cnt; ++i)
        lg[i] = lg[i / 2] + 1;
    for(int l = 1; l <= lg[cnt]; ++l)
        for(int i = 1; i <= cnt - (1 << l) + 1; ++i)
            euler[l][i] = min_by_time(euler[l - 1][i], euler[l - 1][i + (1 << (l - 1))]);
}

bool isAncestor(int u, int v){
    return (in[u] <= in[v] && in[v] <= out[u]);
}

void build_aux(vector<int> &vec){
    sort(vec.begin(), vec.end(), [&](int u, int v){
        return in[u] < in[v];
    });

    int z = vec.size();
    for(int i = 1; i < z; ++i)
        vec.pb(LCA(vec[i - 1], vec[i]));

    sort(vec.begin(), vec.end(), [&](int u, int v){
        return in[u] < in[v];
    });
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());

    int id = 0;

    stk[++id] = vec[0];

    for(int i = 1; i < vec.size(); ++i){
        while(id && !isAncestor(stk[id], vec[i]))
            --id;
        if(id)
            ++sum[vec[i]], --sum[stk[id]];
        stk[++id] = vec[i];
    }

}

void inp(){
    cin >> n >> m >> k;
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }
}

void solve(){
    init();

    while(m--){
        int s;
        cin >> s;

        vector<int> vec;
        for(int i = 1; i <= s; ++i){
            int x;
            cin >> x;
            vec.pb(x);
        }

        build_aux(vec);
    }

    DFS();

    sort(ans.begin(), ans.end());
    ans.resize(unique(ans.begin(), ans.end()) - ans.begin());

    cout << ans.size() << "\n";
    for(int i : ans)
        cout << i << " ";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }

    inp();
    solve();
}

Compilation message (stderr)

railway.cpp: In function 'void build_aux(std::vector<int>&)':
railway.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 1; i < vec.size(); ++i){
      |                    ~~^~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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