제출 #1128600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128600		JuanJL	Railway (BOI17_railway)	C++20	100 / 100	275 ms	49400 KiB

railway

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define forn(i,a,b) for(int i = a; i < b; i++)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

const int MAXN = 100000+5;

ll n,m,k;

ll lvl[MAXN];
ll prnt[MAXN];

vector<ll> cAdj[MAXN];
vector<ll> adj[MAXN];
set<ll> ndSet[MAXN];

ll obj[MAXN]; //Objetivo de conexiones del ministro I
ll aCon[MAXN]; //Conexiones actuales del objetivo i

map<pair<ll,ll>,ll> mp;

void dfs(ll nd,ll p,ll lv){
	lvl[nd]=lv;
	prnt[nd]=p;
	for(auto i:adj[nd]) if(i!=p) dfs(i,nd,lv+1);
}

void solve(){
	priority_queue<pair<ll,ll>> pq;
	forn(i,0,n) pq.push({lvl[i],i});
	
	while(!pq.empty()){
		ll nd = pq.top().snd; pq.pop();
		forn(i,0,SZ(adj[nd])){
			if(adj[nd][i]==prnt[nd]) continue;
			cAdj[nd][i]+=SZ(ndSet[adj[nd][i]]);
			if(SZ(ndSet[nd])<SZ(ndSet[adj[nd][i]])) swap(ndSet[nd],ndSet[adj[nd][i]]);
			for(auto j:ndSet[adj[nd][i]]){
				auto h = ndSet[nd].find(j);
				
				if(h!=ndSet[nd].end()){
					aCon[*h]++;
					if(aCon[*h]==obj[*h]){ ndSet[nd].erase(h); continue; }
				}
				ndSet[nd].insert(j);
				
			}
		}
	}
	
	vector<pair<ll,ll>> res;
	forn(i,0,n){
		forn(j,0,SZ(cAdj[i])){
			if(cAdj[i][j]>=k) res.pb({min((ll)i,adj[i][j]),max((ll)i,adj[i][j])});
		}
	}
	
	cout<<SZ(res)<<'\n';
	for(auto i:res){
		cout<<mp[i]<<" ";
	}
	cout<<'\n';
}

int main(){
	cin>>n>>m>>k;
	
	ll u,v;
	forn(i,0,n-1){
		cin>>u>>v; u--; v--;
		mp[{min(u,v),max(u,v)}]=i+1;
		adj[u].pb(v);
		cAdj[u].pb(0);
		adj[v].pb(u);
		cAdj[v].pb(0);
	}
	
	dfs(0,-1,0);
	
	ll t;
	ll aux;
	forn(i,0,m){
		cin>>t;
		obj[i]=t-1;
		aCon[i]=0;
		forn(j,0,t){
			cin>>aux; aux--;
			ndSet[aux].insert(i);
		}
	}
	
	solve();
	
	return 0;
}

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