Submission #700070

#	Time	Username	Problem	Language	Result	Execution time	Memory
700070		TS_2392	Railway (BOI17_railway)	C++14	100 / 100	99 ms	23028 KiB

railway

#include <bits/stdc++.h>
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
using namespace std;
const int N = 1e5 + 3;
int n, m, k, node[N], cnt[N];
int Tin[N], Timer, jmp[N][18], dep[N];
bool mark[N];
vector<int> res;
vector< pair<int, int> > adj[N];
void dfsLca(int u, int par){
    Tin[u] = ++Timer;
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i].fi;
        if(v == par) continue;
        jmp[v][0] = u; dep[v] = dep[u] + 1;
        for(int j = 1; j <= 17; ++j){
            if(!jmp[v][j - 1]) break;
            jmp[v][j] = jmp[jmp[v][j - 1]][j - 1];
        }
        dfsLca(v, u);
    }
}
bool cmp(const int &a, const int &b){
    return Tin[a] < Tin[b];
}
int Lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 17; i >= 0; --i) if(dep[u] - (1 << i) >= dep[v]){
        u = jmp[u][i];
    }
    if(u == v) return u;
    for(int i = 17; i >= 0; --i) if(jmp[u][i] != jmp[v][i]){
        u = jmp[u][i]; v = jmp[v][i];
    }
    return jmp[u][0];
}
void dfs(int u, int pre_id){
    for(int i = 0; i < adj[u].size(); ++i){
        int v, id; tie(v, id) = adj[u][i];
        if(id == pre_id) continue;
        dfs(v, id); cnt[u] += cnt[v];
    }
    if(pre_id && cnt[u] / 2 >= k) res.eb(pre_id);
}
int main(){
    SPEED;
    cin >> n >> m >> k;
    for(int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        adj[u].eb(v, i); adj[v].eb(u, i);
    }
    dfsLca(1, 0);
    while(m--){
        int sz; cin >> sz;
        for(int i = 1; i <= sz; ++i) cin >> node[i];
        sort(node + 1, node + 1 + sz, cmp);
        node[sz + 1] = node[1];
        for(int i = 1; i <= sz; ++i){
            int u = node[i], v = node[i + 1];
            int lca = Lca(u, v);
            ++cnt[u]; ++cnt[v]; cnt[lca] -= 2;
        }
    }
    dfs(1, 0); sort(all(res));
    cout << res.size() << '\n';
    for(int &x : res) cout << x << ' ';
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfsLca(int, int)':
railway.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i = 0; i < adj[u].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < adj[u].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~

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