Submission #832049

#	Time	Username	Problem	Language	Result	Execution time	Memory
832049		Antekb	Road Closures (APIO21_roads)	C++17	36 / 100	2081 ms	30536 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.end()[-1-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.end()[-1-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];
	}
	for(int i=0; i<n; i++){
		sort(all(E[i]), [](pii a, pii b){return mp(a.nd, a.st)<mp(b.nd, b.st);});
	}
	vector<ll> ans(n);
	ans[0]=sum;
	par[0]=-1;
	int K=50;
	for(int i=1; i<K && i<n; i++){
		dfs(0, i);
		ans[i]=sum-dp[0][1];
	}
	vi todo;
	for(int t=K; t<n; t++){
		if(t==50 || t==100 || t==200 || t==400 || t==800 || t==1600 || t==4000){
			todo.clear();
			sum=0;
			for(int i=0; i<n; i++){
				if(E[i].size()>=K){
					E2[i].clear();
					suf[i].clear();
					co[i].clear();
					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];
						}
					}
				}
			}
		}
				ans[t]=sum;
				for(int v:todo){
					dfs2(v, t);
					ans[t]-=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.end()[-1-j];
      |      ~^~~~~~~~~~
roads.cpp:87:25: 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.end()[-1-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:127:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |     if(E[i].size()>=K){
      |        ~~~~~~~~~~~^~~
roads.cpp:131:33: 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(i==0 || E[par[i]].size()<K)todo.pb(i);
      |                 ~~~~~~~~~~~~~~~~^~
roads.cpp:133:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  133 |       if(E[e.st].size()>=K && e.st!=par[i]){
      |          ~~~~~~~~~~~~~~^~~
roads.cpp:137:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |       if(E[e.st].size()<K || e.st!=par[i]){
      |          ~~~~~~~~~~~~~~^~
roads.cpp:139:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |        if(E[e.st].size()<K){
      |           ~~~~~~~~~~~~~~^~
roads.cpp:148:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |       if(j!=co[i].size()-1){
      |          ~^~~~~~~~~~~~~~~~

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