제출 #413644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413644		Berted	Road Closures (APIO21_roads)	C++14	100 / 100	202 ms	40844 KiB

roads

#include "roads.h"

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define ll long long
#define pii pair<ll, ll>
#define ppi pair<pii, ll>
#define fst first
#define snd second

using namespace std;

vector<pii> adj[100001];
vector<ll> temp;

namespace BIT
{
	vector<ll> C;
	ll BIT[100001][2];
	inline void reset()
	{
		for (int i = 0; i <= C.size(); i++) {BIT[i][0] = BIT[i][1] = 0;}
		C.clear();
	}
	inline void pushPoint(ll x) {C.push_back(x);}
	inline void process() {sort(C.begin(), C.end()); C.resize(unique(C.begin(), C.end()) - C.begin());}
	inline ll query(int t, ll x)
	{
		x = upper_bound(C.begin(), C.end(), x) - C.begin();
		ll ret = 0;
		for (; x; x -= x & (-x)) {ret += BIT[x][t];}
		return ret;
	}
	inline ll query2(int t, ll x)
	{
		ll ret = 0;
		for (; x; x -= x & (-x)) {ret += BIT[x][t];}
		return ret;
	}
	inline void update(int t, int x, ll v)
	{
		x = upper_bound(C.begin(), C.end(), x) - C.begin();
		//cerr << "UPD: " << t << " " << x << " " << v << "\n";
		for (; x <= C.size(); x += x & (-x)) {BIT[x][t] += v;}
	}
	inline ll findKth(int x)
	{
		int L = 1, R = C.size() + 1;
		while (L < R)
		{
			int M = L + R >> 1;
			if (query2(0, M) < x) {L = M + 1;}
			else {R = M;}
		}
		if (L == C.size() + 1) {return query2(1, C.size());}
		else {return query2(1, L - 1) + C[L - 1] * (x - query2(0, L - 1));}
	}
}
struct DS {vector<pii> DP; int fix = 0;};

inline bool comp(const pair<DS*, int> L, const pair<DS*, int> R)
{
	return L.fst -> DP.size() > R.fst -> DP.size();
}

DS* DFS(int u, int p)
{
	vector<pair<DS*, int>> child;
	for (const auto &v : adj[u])
	{
		if (v.fst == p) continue;
		child.push_back({DFS(v.fst, u), v.snd});
	}

	int deg = adj[u].size();
	if (child.size())
	{
		BIT :: reset();
		for (const auto &v : adj[u])
		{
			if (v.fst == p) continue;
			BIT :: pushPoint(-v.snd);
		}
		BIT :: process();
		sort(child.begin(), child.end(), comp);
		
		while (child[0].fst -> DP.size() < deg) child[0].fst -> DP.push_back({0, 0});
		for (int j = child[0].fst -> fix; j < deg; j++) {child[0].fst -> DP[j].fst = child[0].fst -> DP[j].snd;}
		for (int j = deg; j < child[0].fst -> fix; j++) {child[0].fst -> DP[j].snd = min(child[0].fst -> DP[j].snd, child[0].fst -> DP[j].fst + child[0].snd);}
		child[0].fst -> fix = deg;

		//cerr << "DFS: " << u << " " << child.size() << '\n';

		int jj = child.size() - 1; ll tp = 0; 
		for (int i = 0; i < deg; i++)
		{
			vector<ll> V; ll t = 0;
			for (; jj >= 0 && child[jj].fst -> DP.size() <= i; jj--)
			{
				//cerr << "jj: " << jj << "\n";
				tp += child[jj].snd;
				BIT :: update(0, -child[jj].snd, 1);
				BIT :: update(1, -child[jj].snd, -child[jj].snd);
			}
			t = tp;

			for (int j = 0; j <= jj; j++)
			{
				if (i >= child[j].fst -> fix) {child[j].fst -> DP[i].fst = child[j].fst -> DP[i].snd;}
				t += child[j].fst -> DP[i].fst + child[j].snd;
				V.push_back(child[j].fst -> DP[i].snd - (child[j].fst -> DP[i].fst + child[j].snd));
				if (V.back() >= 0) {V.pop_back();}
			}
			//cerr << i << ": " << t << " " << jj << '\n';
			sort(V.begin(), V.end());
			child[0].fst -> DP[i].fst = child[0].fst -> DP[i].snd = t;

			int j = 0;
			for (j = 0; j < V.size(); j++)
			{
				if (BIT :: query(0, V[j]) + (j + 1) <= i + 1) {child[0].fst -> DP[i].fst += V[j];}
				else {break;}
			}
			//cerr << j << " " << i + 1 - j << " " << BIT :: findKth(i + 1 - j) << "\n";
			child[0].fst -> DP[i].fst += BIT :: findKth(i + 1 - j);

			j = 0;
			for (j = 0; j < V.size(); j++)
			{
				if (BIT :: query(0, V[j]) + (j + 1) <= i) {child[0].fst -> DP[i].snd += V[j];}
				else {break;}
			}
			//cerr << j << " " << i - j << " " << BIT :: findKth(i - j) << "\n";
			child[0].fst -> DP[i].snd += BIT :: findKth(i - j);
		}

		for (int j = 1; j < child.size(); j++)
		{
			for (int k = deg; k < child[j].fst -> DP.size(); k++) 
			{
				if (k < child[j].fst -> fix) child[0].fst -> DP[k].snd += min(child[j].fst -> DP[k].fst + child[j].snd, child[j].fst -> DP[k].snd);
				else child[0].fst -> DP[k].snd += child[j].fst -> DP[k].snd;
			}
		}

		/*cerr << "DFS: " << u << " " << child[0].fst -> fix << "\n";
		for (int i = 0; i < child[0].fst -> DP.size(); i++)
		{
			cerr << child[0].fst -> DP[i].fst << " " << child[0].fst -> DP[i].snd << "\n";
		}*/

		return child[0].fst;
	}
	else {return new DS;}
}

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) 
{
	vector<ll> ret(N);
	for (int i = 1; i < N; i++)
	{
		ret[0] += W[i - 1];
		adj[U[i - 1]].push_back({V[i - 1], W[i - 1]});
		adj[V[i - 1]].push_back({U[i - 1], W[i - 1]});
	}

	DS* ans = DFS(0, -1);
	for (int i = 0; i < ans -> DP.size(); i++) 
	{
		if (i < ans -> fix) ret[i + 1] = ans -> DP[i].fst;
		else ret[i + 1] = ans -> DP[i].snd;
	}

	return ret;
}

컴파일 시 표준 에러 (stderr) 메시지

roads.cpp: In function 'void BIT::reset()':
roads.cpp:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for (int i = 0; i <= C.size(); i++) {BIT[i][0] = BIT[i][1] = 0;}
      |                   ~~^~~~~~~~~~~
roads.cpp: In function 'void BIT::update(int, int, long long int)':
roads.cpp:46:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for (; x <= C.size(); x += x & (-x)) {BIT[x][t] += v;}
      |          ~~^~~~~~~~~~~
roads.cpp: In function 'long long int BIT::findKth(int)':
roads.cpp:53:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |    int M = L + R >> 1;
      |            ~~^~~
roads.cpp:57:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   if (L == C.size() + 1) {return query2(1, C.size());}
      |       ~~^~~~~~~~~~~~~~~
roads.cpp: In function 'DS* DFS(int, int)':
roads.cpp:89:36: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |   while (child[0].fst -> DP.size() < deg) child[0].fst -> DP.push_back({0, 0});
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
roads.cpp:100:49: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |    for (; jj >= 0 && child[jj].fst -> DP.size() <= i; jj--)
      |                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
roads.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    for (j = 0; j < V.size(); j++)
      |                ~~^~~~~~~~~~
roads.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |    for (j = 0; j < V.size(); j++)
      |                ~~^~~~~~~~~~
roads.cpp:139:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<DS*, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   for (int j = 1; j < child.size(); j++)
      |                   ~~^~~~~~~~~~~~~~
roads.cpp:141:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |    for (int k = deg; k < child[j].fst -> DP.size(); k++)
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:170:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |  for (int i = 0; i < ans -> DP.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