Submission #1213278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213278		Malix	Railway (BOI17_railway)	C++20	100 / 100	93 ms	25288 KiB

railway

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,q,k,m;
vector<vector<pi>> a;
vector<pi> p;
vi num,cnt,low;
vii par;
int nm=0,lw=0;

void dfs(int x){
    num[x]=nm++;
    for(auto [u,v]:a[x])if(p[x].F!=u){
        par[u][0]=x;
        p[u]={x,v};
        dfs(u);
    }
    low[x]=lw++;
}

void dfs2(int x){
    for(auto [u,v]:a[x])if(p[x].F!=u){
        dfs2(u);
        cnt[x]+=cnt[u];
    }
}

bool ances(int x,int y){
    if(y==-1)return 1;
    if(x==-1)return 0;
    return (num[x]>=num[y]&&low[x]<=low[y]);
}

int LCA(int x,int y){
    if(ances(x,y))return y;
    if(ances(y,x))return x;
    for(int i=m-1;i>=0;i--)if(!ances(x,par[y][i]))y=par[y][i];
    return par[y][0];
}

int main() {   
// ios::sync_with_stdio(0);
// cin.tie(0);
// freopen("test_input.txt", "r", stdin);
// freopen("test_output.txt", "w", stdout);
    cin>>n>>q>>k;
    m=log2(n)+1;
    a.resize(n);p.resize(n,{-1,-1});num.resize(n);low.resize(n);
    par.resize(n,vi(m,-1));
    cnt.resize(n,0);
    REP(i,0,n-1){
        int x,y;cin>>x>>y;
        x--;y--;
        a[x].PB({y,i});
        a[y].PB({x,i});
    }
    dfs(0);
    REP(j,1,m)REP(i,0,n)if(par[i][j-1]!=-1)par[i][j]=par[par[i][j-1]][j-1];
    while(q--){
        int sz;cin>>sz;
        vector<pi> arr;
        REP(i,0,sz){
            int y;cin>>y;
            y--;
            arr.PB({num[y],y});
        }
        sort(arr.begin(),arr.end());
        arr.erase(unique(arr.begin(),arr.end()),arr.end());
        reverse(arr.begin(),arr.end());
        sz=arr.size();
        REP(i,0,sz){
            int x=arr[i].S,y=arr[(i+1)%sz].S;
            int z=LCA(x,y);
            cnt[x]++;
            cnt[z]--;
        }
    }
    dfs2(0);
    vi ans;
    REP(i,1,n)if(cnt[i]>=k)ans.PB(p[i].S);
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<"\n";
    for(auto u:ans)cout<<u+1<<" ";
}

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