제출 #1169382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169382		sasde	Railway (BOI17_railway)	C++20	36 / 100	106 ms	61372 KiB

railway

#include<bits/stdc++.h>
#define int long long
#define str string
#define task "a"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back//khi dùng pair
#define emb emplace_back//k pair
using namespace std;
const int N=1e6+5,lg=20,mod=1e9+7;
int n,h[N],dp[N],timt,m,k,up[N][lg+5],tin[N],tout[N],ans,g[N];
vector<ii>a[N];
void dfs1(int u,int cha){
    for(ii v:a[u]){
        if(v.fi==cha)continue;
        dfs1(v.fi,u);
        dp[u]+=dp[v.fi];
        g[v.se]=dp[v.fi];
    }
}
void dfs(int u,int cha){
    tin[u]=++timt;
    for(ii v:a[u]){
        if(v.fi==cha)continue;
        h[v.fi]=h[u]+1;
        up[v.fi][0]=u;
        dfs(v.fi,u);
    }
    tout[u]=timt;
}
void build(){
       for(int j=1;j<=lg;++j){
        for(int i=1;i<=n;++i){
            if(up[i][j-1] != 0)
             up[i][j]=up[up[i][j-1]][j-1];
            else 
             up[i][j] = 0;
        }
       }
}
int lca(int u,int v){
    if(h[v]>h[u])swap(u,v);
     for(int i=lg;i>=0;--i){
        if(h[u]-h[v]>=(1<<i)){
            u=up[u][i];
        }
     }
     if(u==v)return u;
     for(int i=lg;i>=0;--i){
        if(up[u][i]!=up[v][i]){
            u=up[u][i];
            v=up[v][i];
        }
     }
 return up[u][0];
}
bool cmp(int u,int v){
    return tin[u]<tin[v];
}
void solve(){
    cin >> n >> m >> k; 
    for(int i=1;i<n;++i){
        int u,v;
        cin >> u >> v;
         a[u].emb(v,i);
         a[v].emb(u,i);
    }
    dfs(1,-1);
    build();
    while(m--){
        int ss;
        cin >> ss;
        vector<int>res;stack<int>s;
        for(int i=1;i<=ss;++i){
            int u;
            cin >> u ;
            res.emb(u);
        }
      sort(res.begin(),res.end(),cmp);
      int u=-1;
      for(int j:res){
        if(u!=-1){
            dp[lca(u,j)]-=2;
            dp[u]++;
            ++dp[j];
        }
            u=j;
      }
      // cout<<'\n';
    }
    dfs1(1,-1);
    vector<int>res;
    for(int i=1;i<n;++i){
        if(g[i]>=k){

res.emb(i);
        }
    }
    sort(res.begin(),res.end());
    cout <<res.size()<<'\n';
    for(int i:res)cout <<i<<" ";
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    // cin >> t;
    while(t--){
        solve();
    }
    
}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main()
      | ^~~~

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