Submission #239538

#	Time	Username	Problem	Language	Result	Execution time	Memory
239538		dsjong	Railway (BOI17_railway)	C++14	100 / 100	241 ms	37620 KiB

railway

#include <bits/stdc++.h>
using namespace std;
vector<int>adj[200005];
int ind[200005], tim[200005];
int dep[200005];
int a[200005];  //actual rmq array (corresponding depths of tour vector)
vector<int>tour;
int timer=0;
void dfs(int i,int p){
    tim[i]=timer++;
    if(!dep[i]) dep[i]=dep[p]+1;
    ind[i]=tour.size();
    tour.push_back(i);
    for(int j:adj[i]){
        if(j!=p){
            dfs(j,i);
            tour.push_back(i);
        }
    }
}
int st[200005][20];
void build(int n){
    for(int i=0;i<n;i++){
        st[i][0]=i;
    }
    for(int j=1;(1<<j)<=n;j++){
        for(int i=0;i+(1<<j)<=n;i++){
            if(a[st[i][j-1]]>a[st[i+(1<<(j-1))][j-1]]){
                st[i][j]=st[i+(1<<(j-1))][j-1];
            }
            else{
                st[i][j]=st[i][j-1];
            }
        }
    }
}
int query(int l,int r){
    int j=(int)log2(r-l+1);
    if(a[st[l][j]]<a[st[r-(1<<j)+1][j]]){
        return st[l][j];
    }
    return st[r-(1<<j)+1][j];
}
int lca(int x,int y){
    if(ind[x]>ind[y]) swap(x,y);
    return tour[query(ind[x],ind[y])];
}
bool cmp(int x, int y){
    return tim[x]<tim[y];
}
int cnt[200005];
void go(int x, int p){
    for(int y:adj[x]){
        if(y==p) continue;
        go(y, x);
        cnt[x]+=cnt[y];
    }
}
vector<pair<int, int>>edges;
int main(){
    int n, m, k;
    cin>>n>>m>>k;
    for(int i=1;i<n;i++){
        int x, y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
        edges.push_back({x, y});
    }
    dfs(1, 0);
    for(int i=0;i<tour.size();i++){
        a[i]=dep[tour[i]];
    }
    build(tour.size());
    for(int i=1;i<=m;i++){
        int s;
        cin>>s;
        vector<int>v;
        for(int j=0;j<s;j++){
            int x;
            cin>>x;
            v.push_back(x);
        }
        sort(v.begin(), v.end(), cmp);
        for(int i=0;i<s;i++){
            int u=v[i], t=v[(i+1)%s];
            //cout<<u<<" "<<t<<" "<<lca(u, t)<<endl;
            cnt[u]++;
            cnt[t]++;
            cnt[lca(u, t)]-=2;
        }
        //cout<<endl;
    }
    go(1, 0);
    vector<int>ans;
    for(int i=0;i<n-1;i++){
        int x=edges[i].first, y=edges[i].second;
        if(dep[x]<dep[y]) swap(x, y);
        //cout<<x<<" "<<y<<" "<<cnt[x]<<endl;
        if(cnt[x]>=2*k) ans.push_back(i+1);
    }
    cout<<ans.size()<<"\n";
    for(int i:ans) cout<<i<<" ";
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tour.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