Submission #934826

#	Time	Username	Problem	Language	Result	Execution time	Memory
934826		irmuun	Railway (BOI17_railway)	C++17	100 / 100	82 ms	28112 KiB

railway

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll int
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,k;
    cin>>n>>m>>k;
    vector<pair<ll,ll>>adj[n];
    for(ll i=1;i<n;i++){
        ll u,v;
        cin>>u>>v;
        u--,v--;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
    }
    ll tin[n],tout[n],timer=0,par[n][18],dep[n],edge[n];
    dep[0]=0;
    function <void(ll,ll)> dfs=[&](ll x,ll p){
        tin[x]=timer++;
        par[x][0]=p;
        for(auto [y,i]:adj[x]){
            if(y!=p){
                edge[y]=i;
                dep[y]=dep[x]+1;
                dfs(y,x);
            }
        }
        tout[x]=timer++;
    };
    dfs(0,0);
    function <bool(ll,ll)> compare=[&](ll a,ll b){
        return tin[a]<tin[b];
    };
    vector<ll>c[m],s(m);
    for(ll i=0;i<m;i++){
        cin>>s[i];
        c[i].resize(s[i]);
        for(auto &x:c[i]){
            cin>>x;
            x--;
        }
        sort(all(c[i]),compare);
        c[i].pb(c[i][0]);
    }
    vector<ll>cnt(n,0);
    for(ll lg=1;lg<=17;lg++){
        for(ll i=0;i<n;i++){
            par[i][lg]=par[par[i][lg-1]][lg-1];
        }
    }
    function <ll(ll,ll)> get=[&](ll x,ll l){
        for(ll lg=17;lg>=0;lg--){
            if(l&(1ll<<lg)){
                x=par[x][lg];
            }
        }
        return x;
    };
    function <ll(ll,ll)> lca=[&](ll a,ll b){
        if(dep[b]>dep[a]) swap(a,b);
        a=get(a,dep[a]-dep[b]);
        for(ll lg=17;lg>=0;lg--){
            if(par[a][lg]!=par[b][lg]){
                a=par[a][lg];
                b=par[b][lg];
            }
        }
        if(a==b) return a;
        return par[a][0];
    };
    for(ll i=0;i<m;i++){
        for(ll j=1;j<c[i].size();j++){
            ll x=c[i][j-1],y=c[i][j];
            ll l=lca(x,y);
            cnt[x]++;
            cnt[y]++;
            cnt[l]-=2;
        }
    }
    function <void(ll,ll)> dfs2=[&](ll x,ll p){
        for(auto [y,i]:adj[x]){
            if(y!=p){
                dfs2(y,x);
                cnt[x]+=cnt[y];
            }
        }
    };
    dfs2(0,-1);
    vector<ll>ans;
    for(ll i=0;i<n;i++){
        if(cnt[i]>=2*k){
            ans.pb(edge[i]);
        }
    }
    sort(all(ans));
    cout<<ans.size()<<"\n";
    for(auto x:ans){
        cout<<x<<' ';
    }
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(ll j=1;j<c[i].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