Submission #502325

#	Time	Username	Problem	Language	Result	Execution time	Memory
502325		n00bie_1004	Railway (BOI17_railway)	C++17	0 / 100	41 ms	23480 KiB

railway

#include <bits/stdc++.h>
typedef long long int ll; 

using namespace std;

vector<ll> adj[100005];
ll l = 20; 
ll dp[100005][20]; 
ll timer = 0;
vector<ll> tin(100005), tout(100005);
vector<ll> dep(100005);   
bool comp(ll u, ll v){
    return dep[u] <= dep[v]; 
}
void precomp(ll v, ll par){
    dep[v] = 0; 
    if(par != -1)
        dep[v] = dep[par] + 1; 
    dp[v][0] = par;
    for(ll i=1;i<l;i++)
        dp[v][i] = dp[dp[v][i - 1]][i - 1]; 
    tin[v] = ++timer; 
    for(auto u : adj[v])
        if(u != par)
            precomp(u, v); 
    tout[v] = ++timer; 
} 
ll is_ancs(ll u, ll v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];  
}
ll find_LCA(ll u, ll v){
    if(is_ancs(u, v))
        return u;
    if(is_ancs(v, u))
        return v; 
    for(ll i=l-1;i>=0;i--)
        if(dp[u][i] && !is_ancs(dp[u][i], v))
            u = dp[u][i]; 
    return dp[u][0]; 
}
vector<ll> ans(100005); 
void sum(ll v, ll par){
    for(auto u : adj[v]){
        if(u != par){
            sum(u, v); 
            ans[tin[v]] += ans[tin[u]]; 
        }
    }
}
int main(){ 
    ios_base::sync_with_stdio(false); cin.tie(NULL); 
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> u_(n - 1), v_(n - 1); 
    for(ll i=0;i<n-1;i++){
        cin >> u_[i] >> v_[i]; 
        --u_[i]; --v_[i]; 
        adj[u_[i]].push_back(v_[i]); 
        adj[v_[i]].push_back(u_[i]); 
    }
    precomp(0, -1); 
    for(ll i=0;i<m;i++){
        ll s;
        cin >> s;
        vector<ll> vec(s); 
        for(auto &u : vec)
            cin >> u;
        sort(vec.begin(), vec.end(), comp); 
        for(ll i=0;i<s-1;i++){
            ll u = u_[i], v = v_[i + 1]; 
            ll lca = find_LCA(u, v); 
            ans[tin[u]]++; 
            ans[tin[v]]++; 
            ans[tin[lca]]-=2; 
        }
    }
    sum(0, -1);
    vector<ll> fin; 
    for(ll i=0;i<n;i++)
        if(ans[tin[i]] >= k)
            fin.push_back(i); 
    cout << fin.size() << "\n"; 
    for(auto &u : fin)
        cout << u << " ";
    cout << "\n"; 
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; 
}

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