oj.uz

답안 #1081849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1081849 2024-08-30T12:01:07 Z vjudge1 Fireworks (APIO16_fireworks) C++17
100 / 100
 268 ms 23904 KB 
#include<bits/stdc++.h>
using namespace std;
int n, m;
int pr[300005], cnt[300005], c[300005];//父亲，儿子数量，边权
int cur, rt[300005];//可并堆节点数，可并堆中以原树每个点为根的堆的根
long long ans;
//左偏树(维护大根堆) 部分 
//注意，拐点之间k差为1(允许有重的拐点) 
struct LeftistHeap{
	int l, r, d; 
	long long val;//val在实际存储中表示拐点的横坐标 
} p[600005]; 
#define ls p[k1].l
#define rs p[k1].r
int Mrg(int k1, int k2){
	if(!k1 || !k2) return (k1 + k2);
	if(p[k1].val < p[k2].val) swap(k1, k2);
	rs = Mrg(rs, k2);
	if(p[ls].d < p[rs].d) swap(ls, rs);
	if(!rs)	p[k1].d = 0;
	else	p[k1].d = p[rs].d + 1;
	return k1;
}
void pop(int k){ int k1 = rt[k]; rt[k] = Mrg(ls, rs);}
void push(int k1, int a){rt[k1] = Mrg(rt[k1], a);}
#undef ls
#undef rs
int main(){
	scanf("%d %d", &n, &m);
	//ans先设定为f(0)再逐步向右推出答案 
	for(int i = 2; i <= n + m; i++){
		scanf("%d %d", &pr[i], &c[i]);
		cnt[pr[i]]++, ans += c[i];
	}
	for(int i = n + m; i >= 2; i--){//根据p[i] < i的性质可以直接这样从下到上遍历树 
		//提取出斜率为零的那一段
		//printf("%d\n", i);
		long long l, r;
		l = r = 0;
		if(i <= n){//非叶节点 
			//弹出后面点, 同时完成将后面斜率修成1
			while(cnt[i] >= 2) pop(i), cnt[i]--;
			r = p[rt[i]].val; pop(i);
			l = p[rt[i]].val; pop(i);
		}
		//右移斜率为零的那一段
		p[++cur].val = l + c[i], push(i, cur);
		p[++cur].val = r + c[i], push(i, cur);
		//合并儿子 
		push(pr[i], rt[i]);
	}
	while(cnt[1] >= 1) pop(1), cnt[1]--;
	//从左向右减推出答案
	while(rt[1]) ans -= p[rt[1]].val, pop(1);//每一次的点在它后面还会再减，从而满足斜率	
	printf("%lld\n", ans); 
	return 0;
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d %d", &pr[i], &c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 860 KB Output is correct
41 Correct 1 ms 860 KB Output is correct
42 Correct 2 ms 592 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 2 ms 600 KB Output is correct
46 Correct 2 ms 600 KB Output is correct
47 Correct 2 ms 600 KB Output is correct
48 Correct 2 ms 604 KB Output is correct
49 Correct 2 ms 796 KB Output is correct
50 Correct 2 ms 604 KB Output is correct
51 Correct 2 ms 604 KB Output is correct
52 Correct 2 ms 604 KB Output is correct
53 Correct 2 ms 604 KB Output is correct
54 Correct 2 ms 604 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 860 KB Output is correct
41 Correct 1 ms 860 KB Output is correct
42 Correct 2 ms 592 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 2 ms 600 KB Output is correct
46 Correct 2 ms 600 KB Output is correct
47 Correct 2 ms 600 KB Output is correct
48 Correct 2 ms 604 KB Output is correct
49 Correct 2 ms 796 KB Output is correct
50 Correct 2 ms 604 KB Output is correct
51 Correct 2 ms 604 KB Output is correct
52 Correct 2 ms 604 KB Output is correct
53 Correct 2 ms 604 KB Output is correct
54 Correct 2 ms 604 KB Output is correct
55 Correct 4 ms 1372 KB Output is correct
56 Correct 13 ms 4048 KB Output is correct
57 Correct 22 ms 6748 KB Output is correct
58 Correct 35 ms 8540 KB Output is correct
59 Correct 40 ms 11256 KB Output is correct
60 Correct 61 ms 13972 KB Output is correct
61 Correct 68 ms 15956 KB Output is correct
62 Correct 67 ms 17500 KB Output is correct
63 Correct 85 ms 20908 KB Output is correct
64 Correct 92 ms 22352 KB Output is correct
65 Correct 50 ms 23888 KB Output is correct
66 Correct 48 ms 23892 KB Output is correct
67 Correct 52 ms 23904 KB Output is correct
68 Correct 96 ms 23212 KB Output is correct
69 Correct 106 ms 23124 KB Output is correct
70 Correct 106 ms 23244 KB Output is correct
71 Correct 159 ms 22100 KB Output is correct
72 Correct 158 ms 22096 KB Output is correct
73 Correct 180 ms 22096 KB Output is correct
74 Correct 195 ms 21848 KB Output is correct
75 Correct 177 ms 21588 KB Output is correct
76 Correct 188 ms 21840 KB Output is correct
77 Correct 191 ms 21560 KB Output is correct
78 Correct 204 ms 21584 KB Output is correct
79 Correct 268 ms 21568 KB Output is correct