제출 #30768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30768		cdemirer	Fireworks (APIO16_fireworks)	C++14	0 / 100	2000 ms	142648 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int N, M;

vvii edges;
int edgesn;
vll srt[6000000];

void merge(vll &dst, vll &s1, vll &s2) {
	dst.resize(s1.size()+s2.size());
	int pdst = 0, ps1 = 0, ps2 = 0;
	while (true) {
		if (ps1 == s1.size() && ps2 == s2.size()) return;
		if (ps1 == s1.size()) {
			dst[pdst++] = s2[ps2++];
		}
		else if (ps2 == s2.size()) {
			dst[pdst++] = s1[ps1++];
		}
		else {
			if (s1[ps1] < s2[ps2]) {
				dst[pdst++] = s1[ps1++];
			}
			else {
				dst[pdst++] = s2[ps2++];
			}
		}
	}
}

void dfs(int x, ll d) {
	if (edges[x].size() > 0) {
		for (int i = 0; i < edges[x].size(); i++) {
			dfs(edges[x][i].first, d + edges[x][i].second);
		}
		if (edges[x].size() == 1) {
			srt[x] = srt[edges[x][0].first];
		}
		else {
			merge(srt[x], srt[edges[x][0].first], srt[edges[x][1].first]);
		}
	}
	else {
		srt[x].resize(1);
		srt[x][0] = d;
	}
}

void predfs(int x) {
	if (edges[x].size() > 2) {
		for (int i = 0; i < edges[x].size()/2; i++) {
			edges[edgesn].pb(edges[x][i]);
		}
		for (int i = edges[x].size()/2; i < edges[x].size(); i++) {
			edges[edgesn+1].pb(edges[x][i]);
		}
		edges[x].clear();
		edges[x].pb(mp(edgesn, 0));
		edges[x].pb(mp(edgesn+1, 0));
		edgesn += 2;
	}
	for (int i = 0; i < edges[x].size(); i++) {
		predfs(edges[x][i].first);
	}
}

void dbgdfs(int x, int b) {
	for (int i = 0; i < b; i++) cerr << "\t";
	cerr << x << ": ";
	for (int i = 0; i < srt[x].size(); i++) cerr << srt[x][i] << " ";
	cerr << endl;
	for (int i = 0; i < edges[x].size(); i++) {
		dbgdfs(edges[x][i].first, b+1);
	}
}

ll func(int x, ll t, ll inlen) {
	ll sum = 0;
	int sz = srt[x].size();
	ll lmid = srt[x][(sz-1)/2], umid = srt[x][sz/2];
	if (lmid > t) {
		ll tgtdec = lmid - t;
		tgtdec = min(tgtdec, inlen);
		sum += tgtdec;
		for (int i = 0; i < edges[x].size(); i++) {
			sum += func(edges[x][i].first, t + tgtdec, edges[x][i].second);
		}
	}
	else if (umid < t) {
		ll tgtinc = t - umid;
		sum += tgtinc;
		for (int i = 0; i < edges[x].size(); i++) {
			sum += func(edges[x][i].first, t - tgtinc, edges[x][i].second);
		}
	}
	else {
		for (int i = 0; i < edges[x].size(); i++) {
			sum += func(edges[x][i].first, t, edges[x][i].second);
		}
	}
	return sum;
}

int main(int argc, char **argv) {

	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);

	scanf("%d%d", &N, &M);
	edges.resize(20*(N+M));
	edgesn = N+M+1;
	for (int i = 2; i <= N; i++) {
		int a, b; scanf("%d%d", &a, &b);
		edges[a].pb(mp(i, b));
	}
	for (int i = N+1; i <= N+M; i++) {
		int a, b; scanf("%d%d", &a, &b);
		edges[a].pb(mp(i, b));
	}
	predfs(1);
	dfs(1, 0);
	//dbgdfs(1, 0);
	ll l = srt[1][0], r = srt[1][srt[1].size()-1]+1;
	while (r > l+3) {
		ll mid = (l+r)/2;
		ll cost1 = func(1, mid, 0);
		ll c2p = mid+1;
		ll cost2 = func(1, c2p, 0);
		while (cost2 == cost1) {
			c2p++;
			cost2 = func(1, c2p, 0);
		}
		if (cost2 < cost1) {
			l = mid+1;
		}
		else {
			r = mid+1;
		}
	}
	ll best = (ll)1e18;
	l = srt[1][0], r = srt[1][srt[1].size()-1]+1;
	for (ll i = l; i < r; i++) {
		//cerr << i << endl;
		ll cost = func(1, i, 0);
		//cerr << cost << endl;
		best = min(best, cost);
	}
	printf("%lld\n", best);

	return 0;
}

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

fireworks.cpp: In function 'void merge(vll&, vll&, vll&)':
fireworks.cpp:24:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ps1 == s1.size() && ps2 == s2.size()) return;
           ^
fireworks.cpp:24:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ps1 == s1.size() && ps2 == s2.size()) return;
                               ^
fireworks.cpp:25:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ps1 == s1.size()) {
           ^
fireworks.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if (ps2 == s2.size()) {
                ^
fireworks.cpp: In function 'void dfs(int, ll)':
fireworks.cpp:44:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size(); i++) {
                     ^
fireworks.cpp: In function 'void predfs(int)':
fireworks.cpp:62:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size()/2; i++) {
                     ^
fireworks.cpp:65:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = edges[x].size()/2; i < edges[x].size(); i++) {
                                     ^
fireworks.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges[x].size(); i++) {
                    ^
fireworks.cpp: In function 'void dbgdfs(int, int)':
fireworks.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < srt[x].size(); i++) cerr << srt[x][i] << " ";
                    ^
fireworks.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges[x].size(); i++) {
                    ^
fireworks.cpp: In function 'll func(int, ll, ll)':
fireworks.cpp:96:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size(); i++) {
                     ^
fireworks.cpp:103:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size(); i++) {
                     ^
fireworks.cpp:108:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size(); i++) {
                     ^
fireworks.cpp: In function 'int main(int, char**)':
fireworks.cpp:120:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
fireworks.cpp:124:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
                                  ^
fireworks.cpp:128:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
                                  ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45