Submission #1133808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133808		Math4Life2020	Road Closures (APIO21_roads)	C++20	Compilation error	0 ms	0 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 1e5+5; ll N;
const ll K = 300;
ll ans[Nm];

vector<pii> adj[Nm];
vector<ll> fadj[Nm];
ll deg[Nm];
pii radj[Nm]; //{number, cost}
vector<ll> itpl; //inverse topological sort

ll slvH(ll k) {
	ll dp0[N]; //no path up
	ll dp1[N]; //path up
	for (ll i=(N-1);i>=0;i--) {
		ll x = itpl[i];
		vector<ll> vaug; //augment vector
		ll val0 = 0; //minimum value
		for (ll y: fadj[x]) {
			val0 += dp0[y];
			vaug.push_back(dp1[y]-dp0[y]);
		}
		sort(vaug.begin(),vaug.end());
		ll NDEL = max(0LL,deg[x]-k);
		dp0[x]=val0;
		for (ll j=0;j<NDEL;j++) {
			dp0[x]+=vaug[j];
		}
		NDEL = max(0LL,deg[x]-k-1);
		dp1[x]=val0+radj[x].second;
		for (ll j=0;j<NDEL;j++) {
			dp1[x]+=vaug[j];
		}
		if (x!=0) {
			dp0[x]=min(dp1[x],dp0[x]);
		}
	}
	return dp0[0];
}

vector<ll> minimum_closure_costs(int N1, vector<int> U, vector<int> V, vector<int> W) {
	N=N1;
	for (ll i=0;i<N;i++) {
		adj[i].clear();
		fadj[i].clear();
	}
	tipl.clear();
	ll sroad = 0;
	for (ll i=0;i<(N-1);i++) {
		adj[U[i]].push_back({V[i],W[i]});
		adj[V[i]].push_back({U[i],W[i]});
		sroad += W[i];
	}
	for (ll i=0;i<N;i++) {
		deg[i]=adj[i].size();
	}
	queue<ll> q0;
	q0.push(0); //root is 0
	radj[0]={-1,-1};
	while (!q0.empty()) {
		ll x = q0.front(); q0.pop();
		itpl.push_back(x);
		for (pii p0: adj[x]) {
			if (p0.first!=radj[x].first) {
				fadj[x].push_back(p0.first);
				radj[p0.first]={x,p0.second};
				q0.push(p0.first);
			}
		}
	}
	for (ll k=1;k<N;k++) {
		ans[k]=slvH(k);
	}
	ans[0]=sroad;
	vector<ll> ansF(N,0);
	for (ll i=0;i<N;i++) {
		ansF[i]=ans[i];
	}
	return ansF;
}

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:51:9: error: 'tipl' was not declared in this scope; did you mean 'itpl'?
   51 |         tipl.clear();
      |         ^~~~
      |         itpl