Submission #1099460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099460		Niosakaru	Railway (BOI17_railway)	C++17	29 / 100	139 ms	38980 KiB

railway

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define mp make_pair
#define ii pair <int,int>
 
const int N = 1e5 + 5 , Lg = 17;
 
int n , m , k , u , v , P , T , Roto , in[N] , d[N] , x[N] , dp[N] , p[N][Lg] , cnt[N];
vector <ii> adj[N];
vector <int> rt , qu[N];
 
void dfs(int u){
    in[u] = ++ T;
    for (int i = 1 ; i < Lg ; i ++) p[u][i] = p[p[u][i-1]][i-1];
    for (auto i : adj[u]) if (i.first != p[u][0])
    {
        p[i.first][0] = u , d[i.first] = d[u] + 1;
        dfs(i.first);
    }
}
 
int __lca(int u,int v){
    if (d[u] < d[v]) swap(u,v);
    for (int i = Lg - 1 ; i >= 0 ; i --) if (d[p[u][i]] >= d[v]) u = p[u][i];
    if (u == v) return u;
    for (int i = Lg - 1 ; i >= 0 ; i --) if (p[u][i] != p[v][i]) u = p[u][i] , v = p[v][i];
    return p[u][0];
}
 
bool cmp(int& a,int& b){
    return in[a] < in[b];
}
 
void calc(int u){
    for (int j = 0 ; j < (int)adj[u].size() ; j ++){
        int v = adj[u][j].first , i = adj[u][j].second;
        if (v == p[u][0]) continue;
        calc(v) , cnt[i] = dp[v] , dp[u] += dp[v];
    }
}
 
signed main(){
    cin.tie(0)->sync_with_stdio(0);
 
    cin >> n >> m >> k;
    for (int i = 1 ; i < n ; i ++) cin >> u >> v , adj[u].push_back(mp(v,i)) , adj[v].push_back(mp(u,i));
    
    dfs(1);
  	int cn = 1;
    for (int i = 1 ; i <= m ; i ++){
        cin >> x[i];
        cn &= x[i] == 2;
      	qu[i].resize(x[i]);
        for (int j = 0 ; j < x[i] ; j ++) cin >> qu[i][j];
        sort(qu[i].begin() , qu[i].end() , cmp);
    }
  
  	if (cn){
		for (int i = 1 ; i <= m ; i ++){
          	u = qu[i][0] , v = qu[i][1];
          	P = __lca(u,v);
          	dp[u] ++ , dp[v] ++;
          	dp[P] -= 2;
        }
      	    calc(1);
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
    cout << rt.size() << '\n';
    sort(rt.begin() , rt.end());
    for (auto u : rt) cout << u << ' ';
      return 0;
    }
  
  	for (int i = 1 ; i <= m ; i ++){
        Roto = qu[i][0];
      ++ dp[Roto];
        for (int j = 1 ; j < x[i] ; j ++){
            P = __lca(qu[i][j-1] , qu[i][j]);
            dp[qu[i][j]] ++ , dp[P] --;
            if (d[Roto] > d[P]) dp[Roto] ++ , dp[P] -- , Roto = P;
        }
    }
  
    calc(1);
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
    cout << rt.size() << '\n';
    sort(rt.begin() , rt.end());
    for (auto u : rt) cout << u << ' ';
 
    return 0;
}

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