Submission #826807

#	Time	Username	Problem	Language	Result	Execution time	Memory
826807		8pete8	Railway (BOI17_railway)	C++14	100 / 100	111 ms	47684 KiB

railway

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<cmath>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
//#define int long long
#define mod 1000000007
#define int long long
const int mxn=1e5,lg=20,inf=1e18;
vector<pii>e,adj[mxn+10];
int h[mxn+10],up[mxn+10][lg+10],add[mxn+10],ans[mxn+10],st[mxn+10];
bitset<mxn+10>vis;
int t=0;
 
void solve(int cur,int p){
    st[cur]=t++;
    for(auto i:adj[cur]){
        if(i.f==p)continue;
        up[i.f][0]=cur;
        h[i.f]=h[cur]+1;
        solve(i.f,cur);
    }
}
int push(int cur,int p){
    int cnt=add[cur],g;
    for(auto i:adj[cur]){
        if(i.f==p)continue;
        g=push(i.f,cur);
        ans[i.s]+=g;
        cnt+=g;
    }
    return cnt;
}
bool cmp(int a,int b){return st[a]>st[b];}
int lca(int a,int b){
    if(h[a]<h[b])swap(a,b);
    int k=h[a]-h[b];
    for(int i=0;i<=lg;i++)if(k&(1<<i))a=up[a][i];
    if(a==b)return a;
    for(int i=lg;i>=0;i--)if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i];
    return up[a][0];
}

int32_t main(){
    fastio
    int n,m,k;cin>>n>>m>>k;
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
        e.pb({u,v});
    }
    solve(1,-1);
    for(int i=1;i<=lg;i++)for(int j=1;j<=n;j++)up[j][i]=up[up[j][i-1]][i-1];
    while(m--){
        int a;cin>>a;
        vector<int>an(a);
        vis.reset();
        for(int i=0;i<a;i++)cin>>an[i];
        sort(an.begin(),an.end(),cmp);
        int node;
        for(int i=0;i<a;i++){
            node=lca(an[i],an[(i+1)%a]);
            add[node]-=2;
            add[an[i]]++;
            add[an[(i+1)%a]]++;
        }
    }
    push(1,-1);
    vector<int>v;
    for(int i=0;i<n-1;i++)if(ans[i]>=2*k)v.pb(i+1);
    cout<<v.size()<<'\n';
    for(auto i:v)cout<<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