Submission #832031

#	Time	Username	Problem	Language	Result	Execution time	Memory
832031		Antekb	Road Closures (APIO21_roads)	C++17	26 / 100	2063 ms	30608 KiB

roads

#include<bits/stdc++.h>
#include "roads.h"
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii > vii;

void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);

const int N=1e5+5;
vii E[N], E2[N];
ll dp[N][2];
int par[N];
int vis[N];
vi co[N];
vector<ll> suf[N];

void dfs(int v, int k){
	for(pii e:E[v]){
		int u=e.st, c=e.nd;
		if(u!=par[v]){
			par[u]=v;
			dfs(u, k);
		}
	}
	dp[v][1]=dp[v][0]=0;
		vector<int> V;
		for(pii e:E[v]){
			int u=e.st, c=e.nd;
			if(u!=par[v]){
					dp[v][0]+=dp[u][1];
					V.pb(dp[u][0]+c-dp[u][1]);
			}
		}
		sort(all(V));
		for(int j=V.size()-1; j>=int(V.size())-k+1 && j>=0 && V[j]>0; j--){
			dp[v][0]+=V[j];
		}
		dp[v][1]=dp[v][0];
		if(V.size()>=k && V.end()[-k]>0)dp[v][1]+=V.end()[-k];
		//if(i>=2)assert(2*dp[v][1][i-1]>=dp[v][1][i]+dp[v][1][i-2]);
	//deb(v, dp[v][0], dp[v][1], dp[v][2]);
}
void dfs2(int v, int k){
	for(pii e:E2[v])dfs2(e.st, k);
	dp[v][1]=dp[v][0]=0;
	vector<int> V;
	for(pii e:E2[v]){
		int u=e.st, c=e.nd;
		dp[v][0]+=dp[u][1];
		V.pb(dp[u][0]+c-dp[u][1]);
	}
	sort(all(V));
	ll s=0;
	ll opt=0, opt2=0;
	dp[v][1]=dp[v][0];
	/*for(int i:V){
		deb(i);
	}
	deb(" ");
	for(int i:suf[v]){
		deb(i);
	}*/
	if(suf[v].size()){
	for(int j=0; j<=V.size(); j++){
		if(j+1<k){
			opt=max(opt, suf[v].end()[max(-k+1+j, -int(suf[v].size()))]+s);
			//deb(j, s, suf[v].end()[-k+1+j]);
		}
		if(j<k)opt2=max(opt2, suf[v].end()[max(-k+j, -int(suf[v].size()))]+s);
		if(j!=V.size())s+=V[j];
	}
	}
	else{
		for(int j=0; j<k && j<=V.size(); j++){
		if(j+1<k){
			opt=max(opt,s);
			//deb(j, s, suf[v].end()[-k+1+j]);
		}
		if(j<k)opt2=max(opt2, s);
		if(j!=V.size())s+=V[j];
	}
	}
	opt2=max(opt, opt2);
	dp[v][0]+=opt;
	dp[v][1]+=opt2;
	//deb(v, dp[v][0], dp[v][1]);
}

std::vector<long long> minimum_closure_costs(int n, std::vector<int> uu, 
	std::vector<int> vv,std::vector<int> ww) {
	ll sum=0;
	for(int i=0; i<n-1; i++){
		E[uu[i]].eb(vv[i], ww[i]);
		E[vv[i]].eb(uu[i], ww[i]);
		sum+=ww[i];
	}
	vector<ll> ans(n);
	ans[0]=sum;
	par[0]=-1;
	int K=200;
	for(int i=1; i<K && i<n; i++){
		dfs(0, i);
		ans[i]=sum-dp[0][1];
	}

	vi todo;
	sum=0;
	for(int i=0; i<n; i++){
		if(E[i].size()>=K){
			if(i==0 || E[par[i]].size()<K)todo.pb(i);
			for(auto e:E[i]){
				if(E[e.st].size()>=K && e.st!=par[i]){
					//deb(i, par[i], e.st);
					E2[i].pb(e);
				}
				if(E[e.st].size()<K || e.st!=par[i]){
					sum+=e.nd;
					if(E[e.st].size()<K){
						co[i].pb(e.nd);
					}
				}
			}
			if(co[i].size())sort(all(co[i]));
			suf[i].resize(co[i].size());
			for(int j=int(co[i].size())-1; j>=0; j--){
				suf[i][j]=co[i][j];
				if(j!=co[i].size()-1){
					suf[i][j]+=suf[i][j+1];
				}
			}
		}
	}
	for(int i=K; i<n; i++){
		ans[i]=sum;
		for(int v:todo){
			dfs2(v, i);
			ans[i]-=dp[v][1];
		}
	}
	return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:32:15: warning: unused variable 'c' [-Wunused-variable]
   32 |   int u=e.st, c=e.nd;
      |               ^
roads.cpp:52:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |   if(V.size()>=k && V.end()[-k]>0)dp[v][1]+=V.end()[-k];
      |      ~~~~~~~~^~~
roads.cpp: In function 'void dfs2(int, int)':
roads.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int j=0; j<=V.size(); j++){
      |               ~^~~~~~~~~~
roads.cpp:83:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   if(j!=V.size())s+=V[j];
      |      ~^~~~~~~~~~
roads.cpp:87:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int j=0; j<k && j<=V.size(); j++){
      |                       ~^~~~~~~~~~
roads.cpp:93:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   if(j!=V.size())s+=V[j];
      |      ~^~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:122:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  122 |   if(E[i].size()>=K){
      |      ~~~~~~~~~~~^~~
roads.cpp:123:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |    if(i==0 || E[par[i]].size()<K)todo.pb(i);
      |               ~~~~~~~~~~~~~~~~^~
roads.cpp:125:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |     if(E[e.st].size()>=K && e.st!=par[i]){
      |        ~~~~~~~~~~~~~~^~~
roads.cpp:129:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |     if(E[e.st].size()<K || e.st!=par[i]){
      |        ~~~~~~~~~~~~~~^~
roads.cpp:131:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  131 |      if(E[e.st].size()<K){
      |         ~~~~~~~~~~~~~~^~
roads.cpp:140:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     if(j!=co[i].size()-1){
      |        ~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22