Submission #434319

#	Time	Username	Problem	Language	Result	Execution time	Memory
434319		dqhungdl	Road Closures (APIO21_roads)	C++17	100 / 100	425 ms	128400 KiB

roads

#include "roads.h"

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

typedef pair<int,int> ii;
const int MAX=1e5+5;
const long long INF=1e18;
vector<long long> f0,f1; // f0: do not need to close parent edge, f1: force to close parent edge (f0[u] >= f1[u])
vector<int> deg[MAX];
vector<ii> g[MAX];
bool mark[MAX];

int getBit(int x,int k) {
	return (x>>k)&1;
}

struct Node {
	long long sum,cnt;
	Node* C[2];

	Node() {
		sum=cnt=0;
		C[0]=C[1]=NULL;
	}
};

struct MinBucket {
	Node *root;

	MinBucket() {
		root=new Node();
	}

	void insert(long long value) {
		Node *cur=root;
		for(int i=30;i>=0;i--) {
			cur->sum+=value;
			cur->cnt++;
			int tmp=getBit(value,i);
			if(cur->C[tmp]==NULL)
				cur->C[tmp]=new Node();
			cur=cur->C[tmp];
		}
		cur->sum+=value;
		cur->cnt++;
	}

	int count() {
		return root->cnt;
	}

	long long query(int k) {
		Node *cur=root;
		long long rs=0,curValue=0;
		for(int i=30;i>=0;i--) {
			if(cur->C[0]==NULL) {
				cur=cur->C[1];
				curValue+=(1<<i);
			}
			else if(cur->C[0]!=NULL&&cur->C[0]->cnt<k) {
				k-=cur->C[0]->cnt;
				rs+=cur->C[0]->sum;
				cur=cur->C[1];
				curValue+=(1<<i);
			} else
				cur=cur->C[0];
		}
		rs+=k*curValue;
		return rs;
	}
};

MinBucket S[MAX];

void dfs(int u,int p,int atMost) {
	mark[u]=true;
	long long sum=0;
	for(ii edge:g[u]) {
		int v=edge.first,w=edge.second;
		if(g[v].size()<=atMost)
			break;
		if(v==p)
			continue;
		dfs(v,u,atMost);
		sum+=f0[v];
	}
	int eraseNum=(int)g[u].size()-atMost;
	vector<long long> gaps;
	for(ii edge:g[u]) {
		int v=edge.first,w=edge.second;
		if(g[v].size()<=atMost)
			break;
		if(v==p)
			continue;
		// Cost for switching from 0 to 1
		gaps.push_back(f1[v]+w-f0[v]);
	}
	sort(gaps.begin(),gaps.end());
	// Iterate number of erase edges
	f0[u]=f1[u]=INF;
	long long sumGap=0;
	for(int i=0;i<=gaps.size();i++) {
		if(i+1>=eraseNum)
			f1[u]=min(f1[u],sum+sumGap);
		else if(S[u].count()>=eraseNum-i-1)
			f1[u]=min(f1[u],sum+sumGap+S[u].query(eraseNum-i-1));
		if(i>=eraseNum)
			f0[u]=min(f0[u],sum+sumGap);
		else if(S[u].count()>=eraseNum-i)
			f0[u]=min(f0[u],sum+sumGap+S[u].query(eraseNum-i));
		if(i<gaps.size())
			sumGap+=gaps[i];
	}
}

int cmp(int u,int v) {
	return g[u].size()>g[v].size();
}

bool cmpPair(ii u,ii v) {
	return g[u.first].size()>g[v.first].size();
}

std::vector<long long> minimum_closure_costs(int N, 
											 std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
	for(int i=0;i<N-1;i++) {
		g[U[i]].push_back({V[i],W[i]});
		g[V[i]].push_back({U[i],W[i]});
	}
	for(int i=0;i<N;i++)
		deg[g[i].size()].push_back(i);
	// Sort degree by decreasing order
	vector<int> VV;
	for(int i=0;i<N;i++)
		VV.push_back(i);
	sort(VV.begin(),VV.end(),cmp);
	for(int i=0;i<N;i++)
		sort(g[i].begin(),g[i].end(),cmpPair);
	// Processing
	vector<long long> rs(N);
	f0.resize(N),f1.resize(N);
	for(int i=0;i<N;i++) {
		for(int u:VV) {
			if(g[u].size()<=i)
				break;
			mark[u]=false;
		}
		// Add edges to bucket
		for(int v:deg[i]) {
			for(ii edge:g[v]) {
				int u=edge.first,w=edge.second;
				if(g[u].size()>i)
					S[u].insert(w);
			}
		}
		for(int u:VV) {
			if(g[u].size()<=i)
				break;
			if(!mark[u]) {
				dfs(u,u,i);
				rs[i]+=f0[u];
			}
		}
	}
	return rs;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:81: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]
   81 |   if(g[v].size()<=atMost)
      |      ~~~~~~~~~~~^~~~~~~~
roads.cpp:80:20: warning: unused variable 'w' [-Wunused-variable]
   80 |   int v=edge.first,w=edge.second;
      |                    ^
roads.cpp:92: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]
   92 |   if(g[v].size()<=atMost)
      |      ~~~~~~~~~~~^~~~~~~~
roads.cpp:103:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for(int i=0;i<=gaps.size();i++) {
      |              ~^~~~~~~~~~~~~
roads.cpp:112:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   if(i<gaps.size())
      |      ~^~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:147:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  147 |    if(g[u].size()<=i)
      |       ~~~~~~~~~~~^~~
roads.cpp:155: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]
  155 |     if(g[u].size()>i)
      |        ~~~~~~~~~~~^~
roads.cpp:160:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  160 |    if(g[u].size()<=i)
      |       ~~~~~~~~~~~^~~

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