oj.uz

답안 #111442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
111442 2019-05-15T11:34:51 Z ecasdqina Fireworks (APIO16_fireworks) C++14
7 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n, m; scanf("%d%d", &n, &m);
	std::vector<int> leaf(m);
	std::vector<std::vector<std::pair<int, i64>>> g(n + m); n += m;
	for(int i = 1; i < n; i++) {
		int a; i64 b; scanf("%d%lld", &a, &b);
		
	//	g[i].push_back({a - 1, b});
		g[a - 1].push_back({i, b});
	}
	
	std::vector<i64> dist(n, 0);
	std::function<void (int, int, i64)> dfs = [&](int v, int par, i64 ari) {
		dist[v] = ari;
		for(auto e: g[v]) {
			if(e.first == par) continue;
			dfs(e.first, v, ari + e.second);
		}
	};
	dfs(0, -1, 0);
	
	i64 ans = 1LL << 60;
	i64 ok = 0, ng = 1e15;
	for(int loop = 0; loop < 100; loop++) {
		i64 ml = (ok + ok + ng) / 3LL;
		i64 mr = (ok + ng + ng) / 3LL;
		
	//	cout << ok << " " << ml << " " << mr << " " << ng << endl;
		
		i64 tmp = 0;
		std::function<i64 (int, int, i64)> solve = [&](int v, int par, i64 t) {
			if(v > n - m - 1) return t - (i64)dist[v];
			
			std::vector<i64> vec;
			for(auto e: g[v]) {
				if(e.first == par) continue;
				vec.push_back(solve(e.first, v, t));
			}
			sort(begin(vec), end(vec));
			
			if(v == 0) {
				for(auto v: vec) tmp += std::abs(v);
				return 0LL;
			}
			
			if(vec.size() < 10) {
				i64 X = 0, Y = 1LL << 60;
				for(auto v: vec) {
					i64 HSI = std::abs(v);
					for(auto yys: vec) HSI += std::abs(v - yys);
					if(HSI < Y) {
						X = v;
						Y = HSI;
					}
				}
				for(auto v: vec) tmp += std::abs(v - X); 
				return X;
			}
			
			i64 makino = vec[(vec.size() - 1) / 2];
			for(auto v: vec) tmp += std::abs(v - makino);
			return makino;
		};
		solve(0, -1, ml);
		i64 L = tmp; tmp = 0;
		solve(0, -1, mr);
		i64 R = tmp; tmp = 0;
		
		ans = std::min({ans, L, R});
		if(L < R) ng = mr;
		else ok = ml;
	}
	
	printf("%lld\n", ans);
	return 0;
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:17:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d%d", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:21:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; i64 b; scanf("%d%lld", &a, &b);
                 ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 356 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 356 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Incorrect 3 ms 356 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 356 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Incorrect 3 ms 356 KB Output isn't correct
12 Halted 0 ms 0 KB -