Submission #920644

#	Time	Username	Problem	Language	Result	Execution time	Memory
920644		BBart888	Railway (BOI17_railway)	C++14	100 / 100	285 ms	85016 KiB

railway

#include "bits/stdc++.h"
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define endl '\n'
#define int long long
#define f first
#define mp make_pair
#define s second
using namespace std;

int n, m, k;
int fa[100005][21], par[100005], dep[100005], arr[150005];
set <int> vals[100005], ans;
vector <int> g[100005], rem[100005], add[100005];
unordered_map<int, unordered_map<int,int> > edge;

void dfs(int x, int d, int p){
    dep[x] = d;
    par[x] = p;
    for(int k : g[x]){
        if(k != p) dfs(k, d + 1, x);
    }
} 

int LCA(int a, int b){
    if(dep[a] > dep[b]) swap(a, b);
    int d = dep[b] - dep[a];
    for(int i = 0; i < 20; i++){
        if(d & (1 << i)) b = fa[b][i];
    }
    if(a == b) return a;
    for(int i = 20; i >= 0; i--){
        if(fa[a][i] != fa[b][i]){
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return par[a];
}

void solve(int node, int parent){
    int big = node;
    for(int i : g[node]){
        if(i == parent) continue;
        solve(i, node);
        if(vals[i].size() > vals[big].size()) big = i;
        if(vals[i].size() >= k) ans.insert(edge[node][i]);
    }
    swap(vals[node], vals[big]);
    for(int i : g[node]){
        if(i == parent) continue;
        for(int x : vals[i]) vals[node].insert(x);
    }
    for(int i : add[node]) vals[node].insert(i);
    for(int i : rem[node]) vals[node].erase(i);
}

signed main()
{
    fast;
    cin >> n >> m >> k;
    for(int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        edge[a][b] = edge[b][a] = i;
    }
    dfs(1, 1, -1);
    par[1] = 1;
    for(int i = 1; i <= n; i++) fa[i][0] = par[i];
    for(int k = 0; k < 20; k++){
        for(int i = 1; i <= n; i++){
            fa[i][k+1] = fa[fa[i][k]][k];
        }
    }
    for(int i = 0; i < m; i++){
        int t; cin >> t;
        int y = 0;
        for(int j = 0; j < t; j++){
            cin >> arr[j];
            y = (j == 0 ? arr[j] : LCA(y, arr[j]));
        }
        rem[y].push_back(i);
        for(int j = 0; j < t; j++) add[arr[j]].push_back(i);
    }
    solve(1, -1);
    cout << ans.size() << endl;
    for(int i : ans) cout << i + 1 << ' ';
    cout << endl;
}

Compilation message (stderr)

railway.cpp: In function 'void solve(long long int, long long int)':
railway.cpp:46:27: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   46 |         if(vals[i].size() >= k) ans.insert(edge[node][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