Submission #605276

#	Time	Username	Problem	Language	Result	Execution time	Memory
605276		czhang2718	Railway (BOI17_railway)	C++17	100 / 100	120 ms	26032 KiB

railway

#include "bits/stdc++.h"
using namespace std;
 
#define rep(i,a,b) for(int i=a; i<=b; i++)
 
const int N=1e5, K=18;
int n, t;
vector<pair<int,int>> adj[N];
int tin[N], tout[N];
int ans[N];
int par[N][K];
int up[N];
 
void dfs(int x){
    tin[x]=++t;
    for(int i=1; i<K; i++) par[x][i]=par[par[x][i-1]][i-1];
    for(auto e:adj[x]){
        int k=e.first;
        if(k==par[x][0]) continue;
        par[k][0]=x;
        up[k]=e.second;
        dfs(k);
    }
    tout[x]=++t;
}
 
bool anc(int u, int v){ return tin[u]<=tin[v] && tout[u]>=tout[v]; }
 
int lca(int u, int v){
    if(anc(u,v)) return u;
    for(int k=K-1; k>=0; k--){
        if(!anc(par[u][k], v)) u=par[u][k];
    }
    return par[u][0];
}
 
void dfs2(int x){
    // cout << "to_add[" << x << "] " << ans[x] << "\n";
    for(auto e:adj[x]){
        int k=e.first;
        if(k==par[x][0]) continue;
        dfs2(k);
        ans[x]+=ans[k];
    }
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0);
    
    int k, m;
    cin >> n >> m >> k;

    vector<vector<int>> nodes(m);
    
    for(int i=1; i<n; i++){
        int u,v; cin >> u >> v;
        u--, v--;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    for(int i=0; i<m; i++){
        int cnt; cin >> cnt;
        while(cnt--){
            int x; cin >> x;
            nodes[i].push_back(x-1);
        }
    }
 
    dfs(0);
 
    for(int c=0; c<m; c++){
        sort(nodes[c].begin(), nodes[c].end(), [&](int i, int j){
            return tin[i]<tin[j]; 
        });
        for(int j=0; j<nodes[c].size(); j++){
            int x=nodes[c][j];
            int prv=nodes[c][(nodes[c].size()+j-1)%(nodes[c].size())];
            ans[x]++;
            ans[lca(prv, x)]--;
        }
    }
 
    dfs2(0);
    vector<int> v;
    for(int i=1; i<n; i++){
        if(ans[i]>=k) v.push_back(up[i]);
    }
    cout << v.size() << "\n";
    sort(v.begin(), v.end());
    for(int x:v) cout << x << " ";
}   

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int j=0; j<nodes[c].size(); j++){
      |                      ~^~~~~~~~~~~~~~~~

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