Submission #875804

#	Time	Username	Problem	Language	Result	Execution time	Memory
875804		imarn	Railway (BOI17_railway)	C++14	100 / 100	78 ms	28324 KiB

railway

#include<bits/stdc++.h>
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second
#define vi vector<int>
#define vll vector<long long>
#define vpii vector<pii>
#define ll long long
using namespace std;
const int N=1e5+5;
vector<pii>g[N];
int tin[N],tout[N],pr[N][18],dep[N],t=0,ed[N]{0};
void dfs(int u,int p,int l){
    pr[u][0]=p;
    dep[u]=l;
    tin[u]=++t;
    for(int i=1;i<=17;i++)pr[u][i]=pr[pr[u][i-1]][i-1];
    for(auto v:g[u]){
        if(v.f==p)continue;
        ed[v.f]=v.s;dfs(v.f,u,l+1);
    }tout[u]=t;
}
int lca(int a,int b){
    if(dep[a]>dep[b])swap(a,b);
    for(int i=17;i>=0;i--)if(dep[b]-(1<<i)>=dep[a])b=pr[b][i];
    if(a==b)return a;
    for(int i=17;i>=0;i--)if(pr[a][i]!=pr[b][i])a=pr[a][i],b=pr[b][i];
    return pr[a][0];
}int a[N]{0};
int node[N]{0};
bool cmp(int a,int b){
    return tin[a]<tin[b];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q,k;cin>>n>>q>>k;
    for(int i=1,u,v;i<=n-1;i++)cin>>u>>v,g[u].pb({v,i}),g[v].pb({u,i});
    dfs(1,1,0);
    while(q--){
        int s;cin>>s;
        for(int i=0;i<s;i++)cin>>node[i];
        sort(node,node+s,cmp);node[s]=node[0];
        for(int i=0;i<s;i++){
            int LCA=lca(node[i],node[i+1]);
            a[tin[LCA]]-=2;a[tin[node[i]]]++,a[tin[node[i+1]]]++;
        }
    }set<int>ans;
    for(int i=1;i<=n;i++)a[i]+=a[i-1];
    for(int i=2;i<=n;i++)if(a[tout[i]]-a[tin[i]-1]>=2*k)ans.insert(ed[i]);
    cout<<ans.size()<<'\n';
    for(auto it : ans)cout<<it<<" ";
}

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