제출 #1281267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281267		trandangquang	Railway (BOI17_railway)	C++20	100 / 100	85 ms	25744 KiB

railway

#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=2e5+5;
const int LG=17;

int n,m,k;
int up[N][20],h[N],tin[N],tout[N],tim;
int st[N],top;
int val[N];
vector<ii> adj[N];

void dfs(int u, int p=0){
    h[u]=h[p]+1;
    up[u][0]=p;
    foru(i,1,LG) up[u][i]=up[up[u][i-1]][i-1];
    tin[u]=++tim;

    for(auto [v,id]:adj[u])if(v!=p){
        dfs(v,u);
    }

    tout[u]=tim;
}

int lca(int u, int v){
    if(h[u]<h[v]) swap(u,v);
    int d=h[u]-h[v];
    foru(i,0,LG) if(bit(d,i)) u=up[u][i];
    if(u==v)return u;

    ford(i,LG,0) if(up[u][i]!=up[v][i])u=up[u][i],v=up[v][i];
    return up[u][0];
}

vector<int> res;
void dfs2(int u, int p=0){
    for(auto [v,id]:adj[u]) if(v!=p){
        dfs2(v,u);
        val[u]+=val[v];
        if(val[v]>=k) res.eb(id);
    }
}

void solve(){
    cin>>n>>m>>k;
    foru(i,1,n-1){
        int u,v;cin>>u>>v;
        adj[u].eb(v,i);
        adj[v].eb(u,i);
    }
    dfs(1);

    foru(i,1,m){
        int s; cin>>s;
        vector<int> lst;
        foru(j,1,s){
            int x; cin>>x;
            lst.eb(x);
        }
//        continue;
        sort(all(lst),[](int x, int y){return tin[x]<tin[y];});
        foru(j,0,s-2){
            lst.eb(lca(lst[j],lst[j+1]));
        }
        sort(all(lst),[](int x, int y){return tin[x]<tin[y];});
        lst.erase(unique(all(lst)),lst.end());

//        continue;
        top=0;
        for(int j:lst){
            while(top && tout[st[top]]<tin[j])--top;
            if(top) val[st[top]]--,val[j]++;
            st[++top]=j;
        }
    }

    dfs2(1);

    cout<<sz(res)<<'\n';
    sort(all(res));
    for(int i:res)cout<<i<<" ";
    cout<<'\n';
}

int32_t main(){
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc=1; //cin>>tc;
    rep(i,tc){
        solve();
    }
}

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

railway.cpp: In function 'int32_t main()':
railway.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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