Submission #502514

#	Time	Username	Problem	Language	Result	Execution time	Memory
502514		n00bie_1004	Railway (BOI17_railway)	C++17	100 / 100	122 ms	35896 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]; 
vector<ll> dep(100005); 
ll timer = 0;
vector<ll> tin(100005), tout(100005);
bool comp(ll u, ll v){
    return tin[u] < tin[v]; 
}
void precomp(ll v, ll par){
    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[v] += ans[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, 0); 
    for(ll i=0;i<m;i++){
        ll s;
        cin >> s;
        vector<ll> vec(s); 
        for(auto &u : vec)
            cin >> u, --u;
        sort(vec.begin(), vec.end(), comp);
        for(ll i=0;i<s;i++){
            ll u = vec[i], v = vec[(i + 1) % s]; 
            ll lca = find_LCA(u, v); 
            ans[u]++; 
            ans[v]++; 
            ans[lca]-=2; 
        }
    }
    sum(0, 0); 
    vector<ll> fin; 
    for(ll i=0;i<n-1;i++){
        ll v = v_[i];  
        if(dep[v_[i]] < dep[u_[i]])
            v = u_[i]; 
        if(ans[v] / 2 >= 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: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25