Submission #884747

#	Time	Username	Problem	Language	Result	Execution time	Memory
884747		Iliya_	Railway (BOI17_railway)	C++14	100 / 100	261 ms	52272 KiB

railway

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define pii         pair<int,int>
#define all(x)      x.begin(),x.end()
#define pb          push_back
#define fast_io     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_io     freopen("input.in" , "r" , stdin) ; freopen("output.out" , "w" , stdout);
using namespace std;
typedef long long ll; 
typedef long double dll;

const int N = 1e5+7, lg = 23; 
int mark[N], h[N], par[lg][N], st[N], en[N], tim, a[N];
set<int> dp[N], rem[N];
vector<pii> g[N], vec; 
vector<int> ans;

void dfs(int v){
     mark[v] = 1; 
     st[v] = ++tim;
     for(int i=1; i<lg; i++) par[i][v] = par[i-1][par[i-1][v]];
     for(pii cur : g[v]){
          int u = cur.F;
          if (mark[u]) continue; 
          h[u] = h[v]+1;
          par[0][u] = v; 
          dfs(u); 
     }
     en[v] = ++tim;
}

int lca(int v, int u){
     if (h[v] < h[u]) swap(v,u);
     int dif = h[v] - h[u];
     for(int i=lg-1; i>=0; i--) if ((dif>>i)&1) v = par[i][v]; 
     if (v == u) return v; 
     for(int i=lg-1; i>=0; i--){
          if (par[i][v] != par[i][u]){
               v = par[i][v]; 
               u = par[i][u]; 
          }
     }
     return par[0][v]; 
}

void dfs2(int v, int k){
     mark[v] = 1; 
     for(pii cur : g[v]){
          int u = cur.F, id = cur.S; 
          if (mark[u]) continue; 
          dfs2(u,k); 
          if (int(dp[u].size()) >= k) ans.pb(id); 
          if (int(dp[u].size()) > int(dp[v].size())) swap(dp[u],dp[v]);
          for(int cur : dp[u]) dp[v].insert(cur);
          for(int cur : rem[v]) dp[v].erase(cur);
     }
}

int32_t main(){
     fast_io;

     int n,m,k; cin >> n >> m >> k; 
     for(int i=1; i<n; i++){
          int v,u; cin >> v >> u; 
          g[v].pb({u,i}); 
          g[u].pb({v,i}); 
     }
     dfs(1); 
     for(int j=1; j<=m; j++){
          int x; cin >> x; 
          for(int i=1; i<=x; i++){
               cin >> a[i];
               vec.pb({st[a[i]],a[i]}); 
          }
          int lc = a[1]; 
          for(int i=2; i<=x; i++) lc = lca(lc,a[i]); 
          rem[lc].insert(j); 
          for(int i=1; i<=x; i++) dp[a[i]].insert(j); 
     }
     fill(mark+1,mark+n+1,0);
     dfs2(1,k); 
     sort(all(ans));
     cout << int(ans.size()) << endl;
     for(int cur : ans) cout << cur << " ";
     cout << endl;

     return 0;
}

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