oj.uz

답안 #31984

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31984 2017-09-20T11:09:28 Z cki86201 바이오칩 (IZhO12_biochips) C++11
100 / 100
 66 ms 15884 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int n, k;
vector <int> E[200050];
int p[200050], C[200050];
int down[200050], del[200050];

void pre(int x) {
	down[x] = C[x];
	for(int e : E[x]) {
		pre(e);
		if(down[e] >= C[x]) del[x] = 1;
		down[x] = max(down[x], down[e]);
	}
}

void del_dfs(int x) {
	if(del[x]) {
		for(int e : E[x]) p[e] = p[x];
		p[x] = -1;
	}
	for(int e : E[x]) del_dfs(e);
}

int state[200050];

void solve(){
	int r = -1;
	scanf("%d%d", &n, &k);
	for(int i=1;i<=n;i++) {
		scanf("%d%d", p+i, C+i);
		if(p[i] == 0) r = i;
		else E[p[i]].pb(i);
	}
	pre(r);
	del_dfs(r);
	for(int i=1;i<=n;i++) E[i].clear();
	for(int i=1;i<=n;i++) if(p[i] != -1) E[p[i]].pb(i);
	for(int i=1;i<=n;i++) sort(all(E[i]), [](int a, int b) { return C[a] > C[b];});
	priority_queue <pii> pq;
	for(int e : E[0]) pq.push(pii(C[e], e));
	int cnt = 0, ans = 0;
	while(!pq.empty()) {
		pii t = pq.top(); pq.pop();
		ans += t.Fi; ++cnt;
		if(cnt == k) break;
		int u = t.Se;
		if(state[u] == 0) {
			if(sz(E[u]) <= 1) continue;
			pq.push(pii(C[E[u][0]] + C[E[u][1]] - t.Fi, u));
			state[u] = 1;
		}
		else {
			rep(v, 2) {
				int a = E[u][v];
				state[a] = 1;
				if(sz(E[a]) <= 1) continue;
				pq.push(pii(C[E[a][0]] + C[E[a][1]] - C[a], a));
			}
			for(int i=2;i<sz(E[u]);i++) pq.push(pii(C[E[u][i]], E[u][i]));
		}
	}
	
	printf("%d\n", ans);
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d\n", tc);
		solve();
	}
	return 0;
};

Compilation message

biochips.cpp: In function 'void solve()':
biochips.cpp:59:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
biochips.cpp:61:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", p+i, C+i);
                          ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 10616 KB Output is correct
2 Correct 0 ms 10616 KB Output is correct
3 Correct 0 ms 10616 KB Output is correct
4 Correct 0 ms 10892 KB Output is correct
5 Correct 3 ms 10892 KB Output is correct
6 Correct 6 ms 10892 KB Output is correct
7 Correct 56 ms 15872 KB Output is correct
8 Correct 63 ms 15884 KB Output is correct
9 Correct 66 ms 15824 KB Output is correct
10 Correct 59 ms 15824 KB Output is correct