oj.uz

Submission #698445

# Submission time Handle Problem Language Result Execution time Memory
698445 2023-02-13T13:30:15 Z vjudge1 Fireworks (APIO16_fireworks) C++17
100 / 100
 391 ms 150896 KB 
    #include<bits/stdc++.h>
    #define maxn 1000000
    using namespace std;
    int n,m;
    vector<int> a[maxn];
    int p[maxn];
    int c[maxn];
    long long ans;
    multiset<long long> x[maxn];
    long long t[maxn];
    int pt[maxn];
    vector<long long> cur;
    void dfs(int u) {
    	if(a[u].size()==0) {
    		x[u].insert(c[u]);
    		x[u].insert(c[u]);
    		pt[u]=u;
    		t[u]=c[u];
    		return;
    	}
    	for(auto v:a[u]) {
    		dfs(v);
    	}
    	pt[u]=0;
    	for(auto v:a[u]) {
    		if(x[pt[v]].size()>x[pt[u]].size()) {
    			pt[u]=pt[v];
    		}
    	}
    	for(auto v:a[u]) {
    		if(pt[u]!=pt[v]) {
    			for(auto c:x[pt[v]]) {
    				x[pt[u]].insert(c);
    			}
    		}
    	}
    	int sz=a[u].size();
    	long long sum=0;
    	for(int i=0;i<sz-1;i++) {
    		sum+=(*x[pt[u]].rbegin());
    		x[pt[u]].erase(--x[pt[u]].end());
    	}
    	long long p1=(*x[pt[u]].rbegin());
    	x[pt[u]].erase(--x[pt[u]].end());
    	long long p2=(*x[pt[u]].rbegin());
    	x[pt[u]].erase(--x[pt[u]].end());
    	x[pt[u]].insert(p1+c[u]);
    	x[pt[u]].insert(p2+c[u]);
    	t[u]=p1+c[u];
    	ans+=(sum-(sz-1)*p1);
    	for(auto v:a[u]) {
    		ans+=(p1-t[v]);
    	}
    }
    int main() {
    	scanf("%d %d",&n,&m);
    	for(int i=2;i<=n+m;i++) {
    		scanf("%d %d",&p[i],&c[i]);
    		a[p[i]].push_back(i);
    	}
    	dfs(1);
    	printf("%lld\n",ans);
    	return 0;
    }

Compilation message

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70740 KB Output is correct
2 Correct 35 ms 70792 KB Output is correct
3 Correct 32 ms 70672 KB Output is correct
4 Correct 34 ms 70712 KB Output is correct
5 Correct 33 ms 70740 KB Output is correct
6 Correct 35 ms 70784 KB Output is correct
7 Correct 34 ms 70744 KB Output is correct
8 Correct 34 ms 70728 KB Output is correct
9 Correct 33 ms 70704 KB Output is correct
10 Correct 33 ms 70764 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70732 KB Output is correct
2 Correct 32 ms 70768 KB Output is correct
3 Correct 34 ms 70736 KB Output is correct
4 Correct 34 ms 70744 KB Output is correct
5 Correct 33 ms 70756 KB Output is correct
6 Correct 34 ms 70740 KB Output is correct
7 Correct 32 ms 70768 KB Output is correct
8 Correct 32 ms 70760 KB Output is correct
9 Correct 33 ms 70784 KB Output is correct
10 Correct 37 ms 70780 KB Output is correct
11 Correct 33 ms 70712 KB Output is correct
12 Correct 32 ms 70756 KB Output is correct
13 Correct 34 ms 70764 KB Output is correct
14 Correct 40 ms 70792 KB Output is correct
15 Correct 34 ms 70760 KB Output is correct
16 Correct 33 ms 70752 KB Output is correct
17 Correct 32 ms 70776 KB Output is correct
18 Correct 33 ms 70748 KB Output is correct
19 Correct 33 ms 70716 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70740 KB Output is correct
2 Correct 35 ms 70792 KB Output is correct
3 Correct 32 ms 70672 KB Output is correct
4 Correct 34 ms 70712 KB Output is correct
5 Correct 33 ms 70740 KB Output is correct
6 Correct 35 ms 70784 KB Output is correct
7 Correct 34 ms 70744 KB Output is correct
8 Correct 34 ms 70728 KB Output is correct
9 Correct 33 ms 70704 KB Output is correct
10 Correct 33 ms 70764 KB Output is correct
11 Correct 34 ms 70732 KB Output is correct
12 Correct 32 ms 70768 KB Output is correct
13 Correct 34 ms 70736 KB Output is correct
14 Correct 34 ms 70744 KB Output is correct
15 Correct 33 ms 70756 KB Output is correct
16 Correct 34 ms 70740 KB Output is correct
17 Correct 32 ms 70768 KB Output is correct
18 Correct 32 ms 70760 KB Output is correct
19 Correct 33 ms 70784 KB Output is correct
20 Correct 37 ms 70780 KB Output is correct
21 Correct 33 ms 70712 KB Output is correct
22 Correct 32 ms 70756 KB Output is correct
23 Correct 34 ms 70764 KB Output is correct
24 Correct 40 ms 70792 KB Output is correct
25 Correct 34 ms 70760 KB Output is correct
26 Correct 33 ms 70752 KB Output is correct
27 Correct 32 ms 70776 KB Output is correct
28 Correct 33 ms 70748 KB Output is correct
29 Correct 33 ms 70716 KB Output is correct
30 Correct 34 ms 70740 KB Output is correct
31 Correct 32 ms 70868 KB Output is correct
32 Correct 39 ms 70860 KB Output is correct
33 Correct 42 ms 71092 KB Output is correct
34 Correct 40 ms 71148 KB Output is correct
35 Correct 37 ms 71140 KB Output is correct
36 Correct 34 ms 71244 KB Output is correct
37 Correct 36 ms 71380 KB Output is correct
38 Correct 36 ms 71388 KB Output is correct
39 Correct 37 ms 71372 KB Output is correct
40 Correct 35 ms 71800 KB Output is correct
41 Correct 35 ms 71756 KB Output is correct
42 Correct 34 ms 71024 KB Output is correct
43 Correct 37 ms 71812 KB Output is correct
44 Correct 36 ms 71604 KB Output is correct
45 Correct 36 ms 71524 KB Output is correct
46 Correct 36 ms 71792 KB Output is correct
47 Correct 38 ms 71860 KB Output is correct
48 Correct 39 ms 71628 KB Output is correct
49 Correct 42 ms 71800 KB Output is correct
50 Correct 35 ms 71620 KB Output is correct
51 Correct 35 ms 71736 KB Output is correct
52 Correct 46 ms 71760 KB Output is correct
53 Correct 37 ms 71772 KB Output is correct
54 Correct 39 ms 71776 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70740 KB Output is correct
2 Correct 35 ms 70792 KB Output is correct
3 Correct 32 ms 70672 KB Output is correct
4 Correct 34 ms 70712 KB Output is correct
5 Correct 33 ms 70740 KB Output is correct
6 Correct 35 ms 70784 KB Output is correct
7 Correct 34 ms 70744 KB Output is correct
8 Correct 34 ms 70728 KB Output is correct
9 Correct 33 ms 70704 KB Output is correct
10 Correct 33 ms 70764 KB Output is correct
11 Correct 34 ms 70732 KB Output is correct
12 Correct 32 ms 70768 KB Output is correct
13 Correct 34 ms 70736 KB Output is correct
14 Correct 34 ms 70744 KB Output is correct
15 Correct 33 ms 70756 KB Output is correct
16 Correct 34 ms 70740 KB Output is correct
17 Correct 32 ms 70768 KB Output is correct
18 Correct 32 ms 70760 KB Output is correct
19 Correct 33 ms 70784 KB Output is correct
20 Correct 37 ms 70780 KB Output is correct
21 Correct 33 ms 70712 KB Output is correct
22 Correct 32 ms 70756 KB Output is correct
23 Correct 34 ms 70764 KB Output is correct
24 Correct 40 ms 70792 KB Output is correct
25 Correct 34 ms 70760 KB Output is correct
26 Correct 33 ms 70752 KB Output is correct
27 Correct 32 ms 70776 KB Output is correct
28 Correct 33 ms 70748 KB Output is correct
29 Correct 33 ms 70716 KB Output is correct
30 Correct 34 ms 70740 KB Output is correct
31 Correct 32 ms 70868 KB Output is correct
32 Correct 39 ms 70860 KB Output is correct
33 Correct 42 ms 71092 KB Output is correct
34 Correct 40 ms 71148 KB Output is correct
35 Correct 37 ms 71140 KB Output is correct
36 Correct 34 ms 71244 KB Output is correct
37 Correct 36 ms 71380 KB Output is correct
38 Correct 36 ms 71388 KB Output is correct
39 Correct 37 ms 71372 KB Output is correct
40 Correct 35 ms 71800 KB Output is correct
41 Correct 35 ms 71756 KB Output is correct
42 Correct 34 ms 71024 KB Output is correct
43 Correct 37 ms 71812 KB Output is correct
44 Correct 36 ms 71604 KB Output is correct
45 Correct 36 ms 71524 KB Output is correct
46 Correct 36 ms 71792 KB Output is correct
47 Correct 38 ms 71860 KB Output is correct
48 Correct 39 ms 71628 KB Output is correct
49 Correct 42 ms 71800 KB Output is correct
50 Correct 35 ms 71620 KB Output is correct
51 Correct 35 ms 71736 KB Output is correct
52 Correct 46 ms 71760 KB Output is correct
53 Correct 37 ms 71772 KB Output is correct
54 Correct 39 ms 71776 KB Output is correct
55 Correct 40 ms 72548 KB Output is correct
56 Correct 80 ms 78080 KB Output is correct
57 Correct 99 ms 83712 KB Output is correct
58 Correct 123 ms 87600 KB Output is correct
59 Correct 166 ms 93160 KB Output is correct
60 Correct 209 ms 98900 KB Output is correct
61 Correct 230 ms 102756 KB Output is correct
62 Correct 252 ms 106568 KB Output is correct
63 Correct 347 ms 114380 KB Output is correct
64 Correct 328 ms 115228 KB Output is correct
65 Correct 184 ms 133128 KB Output is correct
66 Correct 157 ms 133044 KB Output is correct
67 Correct 156 ms 91092 KB Output is correct
68 Correct 247 ms 128328 KB Output is correct
69 Correct 282 ms 125088 KB Output is correct
70 Correct 353 ms 125052 KB Output is correct
71 Correct 307 ms 150764 KB Output is correct
72 Correct 322 ms 150896 KB Output is correct
73 Correct 316 ms 138308 KB Output is correct
74 Correct 324 ms 138308 KB Output is correct
75 Correct 329 ms 137764 KB Output is correct
76 Correct 329 ms 137988 KB Output is correct
77 Correct 368 ms 135668 KB Output is correct
78 Correct 337 ms 132956 KB Output is correct
79 Correct 391 ms 137560 KB Output is correct