제출 #30757

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

fireworks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
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;
vi srt[300000];

void merge(vi &dst, vi &s1, vi &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, int 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, int t, int inlen) {
	ll sum = 0;
	int sz = srt[x].size();
	int lmid = srt[x][(sz-1)/2], umid = srt[x][sz/2];
	if (lmid > t) {
		int 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) {
		int 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);
	int l = srt[1][0], r = srt[1][srt[1].size()-1]+1;
	while (r > l+3) {
		int mid = (l+r)/2;
		ll cost1 = func(1, mid, 0);
		ll cost2 = func(1, mid+1, 0);
		if (cost2 < cost1) {
			l = mid+1;
		}
		else {
			r = mid+1;
		}
	}
	ll best = (ll)1e18;
	for (int 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(vi&, vi&, vi&)':
fireworks.cpp:23:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ps1 == s1.size() && ps2 == s2.size()) return;
           ^
fireworks.cpp:23:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ps1 == s1.size() && ps2 == s2.size()) return;
                               ^
fireworks.cpp:24:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ps1 == s1.size()) {
           ^
fireworks.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if (ps2 == s2.size()) {
                ^
fireworks.cpp: In function 'void dfs(int, int)':
fireworks.cpp:43: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:61:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size()/2; i++) {
                     ^
fireworks.cpp:64: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:72: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:80: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:82: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, int, int)':
fireworks.cpp:95:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size(); i++) {
                     ^
fireworks.cpp:102:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size(); i++) {
                     ^
fireworks.cpp:107: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:119: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:123: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:127: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