Submission #171261

#	Time	Username	Problem	Language	Result	Execution time	Memory
171261		mehrdad_sohrabi	Railway (BOI17_railway)	C++14	100 / 100	599 ms	47184 KiB

railway

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
using namespace std;
/// khodaya komak kon
/// ya navid navid
const int N=2e5+100,M=22;
vector <int> g[N];
ll par[N][22];
ll hi[N];
ll st[N];
ll fn[N],tss=1;
ll dfs(ll v,ll p,ll h){
    hi[v]=h;
    st[v]=tss;
    for (int i=0;i<g[v].size();i++){
        ll u=g[v][i];
        if (u==p) continue;
        par[u][0]=v;
        tss++;
        dfs(u,v,h+1);
    }
    tss++;
    fn[v]=tss;
}
ll getpar(ll v,ll h){
    if (h==-1 || h==0){
        return v;
    }
    for(int i=0;i<M;i++){
        if (h & (1 << i)) v = par[v][i];
    }
    return v;
}
int lca(int v, int u) {
    if (hi[v]<hi[u]){
        ll y=v;
        v=u;
        u=y;
    }
    v = getpar(v,hi[v]-hi[u]);
    if (v==u){
        return v;
    }
    for(int i=20;i>=0;i--){
        if (par[v][i] != par[u][i]) {
            v=par[v][i];
            u=par[u][i];
        }

    }
    return par[v][0];
}
ll vis[N];
ll val[N];
ll dp[N];
ll dfss(ll v,ll p){
    dp[v]=val[v];
    for (int i=0;i<g[v].size();i++){
        ll u=g[v][i];
        if (u==p) continue;
        dfss(u,v);
        dp[v]+=dp[u];
    }
}
map <pii,int> mp;
int32_t main(){
    ll n,m,k;
    cin >> n >> m >> k;
    for (int i=0;i<n-1;i++){
        ll u,v;
        cin >> u >> v;
        g[v].pb(u);
        g[u].pb(v);
        mp[{u,v}]=i+1;
        mp[{v,u}]=i+1;
    }
    dfs(1,1,1);
    par[1][0]=1;
    for (int i=1;i<M;i++){
        for (int j=1;j<=n;j++){
            par[j][i]=par[par[j][i-1]][i-1];
        }
    }
    for (int i=0;i<m;i++){
        ll x;
        cin >> x;
        vector <pair <pii,int> > a,d;
        for (int j=0;j<x;j++){
            ll v;
            cin >> v;
            a.pb({{st[v],fn[v]},v});
        }
        sort(a.begin(),a.end());
        for (int i=0;i<a.size();i++){
            vis[a[i].S]=1;
            d.pb(a[i]);
        }
        if (a.size()){
            a.pb(a[0]);
        }
        for (int i=1;i<a.size();i++){
            ll v=a[i].S,u=a[i-1].S;
            ll f=lca(v,u);
            //cout << v << " " << u << " f " << f << endl;
            if (!vis[f]) d.pb({{st[f],fn[f]},f});
            vis[f]=1;
        }
        sort(d.begin(),d.end());
        vector <pii> b;
        b.pb({1e9+100,0});
        for (int i=0;i<d.size();i++){
            while(d[i].F.S>=b.back().F) b.pop_back();
            ll v=b.back().S;
            if (v!=0){
                /// yrkari monde
                val[d[i].S]++;
                val[v]--;
                //cout << d[i].S << " yal " << v << endl;
            }

            b.pb({d[i].F.S,d[i].S});
        }
        for (int i=0;i<d.size();i++){
            vis[d[i].S]=0;
        }
    }

    dfss(1,1);
    ll ans=0;
    vector <int> p;
    for (int i=1;i<=n;i++){
        if (dp[i]>=k){
            ans++;
            p.pb(mp[{i,par[i][0]}]);
        }
    }
    sort(p.begin(),p.end());
    cout << ans << endl;
    for (int i=0;i<p.size();i++){
        cout << p[i] << " " ;
    }
}

Compilation message (stderr)

railway.cpp: In function 'll dfs(ll, ll, ll)':
railway.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<g[v].size();i++){
                  ~^~~~~~~~~~~~
railway.cpp:34:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
railway.cpp: In function 'll dfss(ll, ll)':
railway.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<g[v].size();i++){
                  ~^~~~~~~~~~~~
railway.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
railway.cpp: In function 'int32_t main()':
railway.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<a.size();i++){
                      ~^~~~~~~~~
railway.cpp:111:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=1;i<a.size();i++){
                      ~^~~~~~~~~
railway.cpp:121:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<d.size();i++){
                      ~^~~~~~~~~
railway.cpp:133:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<d.size();i++){
                      ~^~~~~~~~~
railway.cpp:149:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<p.size();i++){
                  ~^~~~~~~~~

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