Submission #448811

#	Time	Username	Problem	Language	Result	Execution time	Memory
448811		julian33	Railway (BOI17_railway)	C++14	100 / 100	146 ms	30012 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=1e5+5,mxL=20; //make sure this is right
const int mod=1e9+7;

vector<pii> graph[mxN];
vector<int> vt[mxN];
int sum[mxN],st[mxN],en[mxN],up[mxN][mxL],cur,ht[mxN];
vector<int> ans;

void dfs(int at,int p){
    up[at][0]=~p?p:at;
    for(int i=1;i<mxL;i++)
        up[at][i]=up[up[at][i-1]][i-1];
    st[at]=++cur;
    for(auto &[i,e]:graph[at]){
        if(i==p)
            continue;
        ht[i]=ht[at]+1;
        dfs(i,at);
    }
    en[at]=++cur;
}

int jump(int a,int k){
    for(int i=0;i<mxL;i++){
        if(k&(1<<i))
            a=up[a][i];
    }
    return a;
}

int lca(int a,int b){
    if(ht[a]>ht[b])
        swap(a,b);
    b=jump(b,ht[b]-ht[a]);
    if(a==b)
        return a;
    for(int i=19;i>=0;i--){
        if(up[a][i]!=up[b][i]){
            a=up[a][i];
            b=up[b][i];
        }
    }
    return up[a][0];
}

bool is_anc(int a,int b){return st[a]<=st[b] && en[a]>=en[b];}

void solve(int at,int p){
    for(int &i:vt[at])
        solve(i,at);
    if(~p)
        sum[at]++;
    sum[at]-=sz(vt[at]);
}

void build(vector<int> &a){
    sort(a.begin(),a.end(),[&](auto x,auto y){return st[x]<st[y];});
    int k=sz(a);
    for(int i=0;i<k-1;i++)
        a.pb(lca(a[i],a[i+1]));
    sort(a.begin(),a.end(),[&](auto x,auto y){return st[x]<st[y];});
    a.resize(unique(a.begin(),a.end())-a.begin());
    for(int &i:a)
        vt[i].clear();
    stack<int> stk; stk.push(a[0]);
    for(int i=1;i<sz(a);i++){
        while(sz(stk)>1 && !is_anc(stk.top(),a[i])){
            int p=stk.top(); stk.pop();
            vt[stk.top()].pb(p);
        }
        stk.push(a[i]);
    }
    while(sz(stk)>1){
        int p=stk.top(); stk.pop();
        vt[stk.top()].pb(p);
    }
    solve(stk.top(),-1);
}

void ps(int at,int p,int k){
    for(auto &[i,e]:graph[at]){
        if(i==p)
            continue;
        ps(i,at,k);
        if(sum[i]>=k)
            ans.pb(e);
        sum[at]+=sum[i];
    }
    deb(at,sum[at]);
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n,m,k; cin>>n>>m>>k;
    for(int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        graph[a].pb({b,i});
        graph[b].pb({a,i});
    }
    dfs(1,-1);
    for(int i=0;i<m;i++){
        int s; cin>>s;
        vector<int> a;
        for(int j=0;j<s;j++){
            int x; cin>>x;
            a.pb(x);
        }
        build(a);
    }
    ps(1,-1,k);
    cout<<sz(ans)<<"\n";
    sort(ans.begin(),ans.end());
    for(int i=0;i<sz(ans);i++)
        cout<<ans[i]<<" \n"[i==sz(ans)-1];
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto &[i,e]:graph[at]){
      |               ^
railway.cpp: In function 'void ps(int, int, int)':
railway.cpp:109:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |     for(auto &[i,e]:graph[at]){
      |               ^

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