Submission #1107709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107709		Articulation_points	Railway (BOI17_railway)	C++14	100 / 100	57 ms	26928 KiB

railway

/* Dirty code by Articulation_points */
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5;
const int MAXLG=16;
int n,m,k,x,y,timer,tin[MAXN+5],tout[MAXN+5],h[MAXN+5],anc[MAXN+5][MAXLG+5];
pair<int,int>dp[MAXN+5];
vector<pair<int,int>>adj[MAXN+5];
void dfs1(int u, int p){
    tin[u]=++timer;
    for(pair<int,int>tmp:adj[u]){
        int v=tmp.first;
        int idx=tmp.second;
        if(v==p)
            continue;
        h[v]=h[u]+1;
        anc[v][0]=u;
        dp[v].second=idx;
        dfs1(v,u);
    }
    tout[u]=timer;
}
void build(){
    for(int j=1;j<=MAXLG;++j)
        for(int i=1;i<=n;++i)
            if(h[i]-(1<<j)>=0)
                anc[i][j]=anc[anc[i][j-1]][j-1];
}
bool is_anc(int u, int v){
    return (tin[u]<=tin[v]&&tout[u]>=tout[v]);
}
int lca(int u, int v){
    if(h[u]>h[v])
        swap(u,v);
    if(is_anc(u,v))
        return u;
    for(int i=MAXLG;i>=0;--i)
        if(h[u]-(1<<i)>=0&&!is_anc(anc[u][i],v))
            u=anc[u][i];
    return anc[u][0];
}
void dfs2(int u, int p){
    for(pair<int,int>tmp:adj[u]){
        int v=tmp.first;
        if(v==p)
            continue;
        dfs2(v,u);
        dp[u].first+=dp[v].first;
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<n;++i){
        cin>>x>>y;
        adj[x].push_back({y,i});
        adj[y].push_back({x,i});
    }
    dfs1(1,0);
    build();
    for(int i=1;i<=m;++i){
        vector<pair<int,int>>v;
        cin>>x;
        for(int j=1;j<=x;++j){
            cin>>y;
            v.push_back({tin[y],y});
        }
        sort(v.begin(),v.end());
        v.push_back({tin[v[0].second],v[0].second});
        for(int j=1;j<v.size();++j){
            dp[v[j].second].first++;
            dp[v[j-1].second].first++;
            dp[lca(v[j].second,v[j-1].second)].first-=2;
        }
    }
    dfs2(1,0);
    vector<int>ans;
    for(int i=2;i<=n;++i)
        if(dp[i].first/2>=k)
            ans.push_back(dp[i].second);
    cout<<ans.size()<<'\n';
    sort(ans.begin(),ans.end());
    for(int x:ans)
        cout<<x<<' ';

}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j=1;j<v.size();++j){
      |                     ~^~~~~~~~~

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