답안 #47704 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47704	2018-05-06T10:54:53 Z	E869120	Fireworks (APIO16_fireworks)	C++14	26 / 100	20 ms	19912 KB

fireworks

#include <iostream>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

struct Node {
	int num, l, r;
};

class SugoyDataStructure {
public:
	vector<Node>vec; int size_ = 0; long long sum = 0;

	void init() {
		vec.push_back(Node{ 0,-1,-1 });
		size_ = 1;
	}
	void add(long long pos, int x) {
		int cx = 0; pos -= sum;
		for (int i = 49; i >= 0; i--) {
			vec[cx].num += x;
			if (pos >= (1LL << i)) {
				if (vec[cx].r >= 0) cx = vec[cx].r;
				else { vec.push_back(Node{ 0,-1,-1 }); vec[cx].r = size_; cx = size_; size_++; }
				pos -= (1LL << i);
			}
			else {
				if (vec[cx].l >= 0) cx = vec[cx].l;
				else { vec.push_back(Node{ 0,-1,-1 }); vec[cx].l = size_; cx = size_; size_++; }
			}
		}
		vec[cx].num += x;
	}
	int getsize() {
		return vec[0].num;
	}
	int getvalue(int p) {
		int cx = 0; long long D = 0;
		for (int i = 49; i >= 0; i--) {
			if (vec[cx].l >= 0 && p < vec[vec[cx].l].num) cx = vec[cx].l;
			else { if (vec[cx].l >= 0) { p -= vec[vec[cx].l].num; } cx = vec[cx].r; D += (1LL << i); }
		}
		return D + sum;
	}
	void AddToSum(long long x) {
		sum += x;
	}
};

long long N, M, A[300009], B[300009], dist[300009], rem; vector<pair<long long, long long>>G[300009];
long long P[300009]; SugoyDataStructure F[300009];

int main() {
	cin >> N >> M;
	for (int i = 2; i <= N + M; i++) { scanf("%lld%lld", &A[i], &B[i]); rem += B[i]; G[A[i]].push_back(make_pair(i, B[i])); }
	for (int i = 1; i <= N + M; i++) { for (int j = 0; j < G[i].size(); j++) dist[G[i][j].first] += dist[i] + G[i][j].second; }

	for (int i = N + M; i >= 1; i--) {
		if (G[i].size() == 0) {
			F[i].init(); P[i] = i;
			F[i].add(dist[i], 2);
		}
		else {
			vector<pair<long long, long long>>A; long long res = 0;
			for (int j = 0; j < G[i].size(); j++) {
				int to = G[i][j].first, L = F[P[to]].getsize();
				A.push_back(make_pair(L, P[to])); res += L;
			}
			sort(A.begin(), A.end(), greater<pair<long long, long long>>());

			int S = A[0].second;
			if (i == 1) { S = 1; F[S].init(); }
			P[i] = S;
			for (int j = 0; j < G[i].size(); j++) {
				int to = G[i][j].first, v = P[to];
				if (v == S) continue;

				for (int k = 0; k < F[v].getsize(); k++) F[S].add(F[v].getvalue(k), 1);
			}
			for (int j = 0; j < G[i].size() - 1; j++) { long long v1 = F[S].getvalue(F[S].getsize() - 1); F[S].add(v1, -1); }
			long long D = F[S].getsize();
			long long v1 = F[S].getvalue(D - 2), v2 = F[S].getvalue(D - 1);

			F[S].AddToSum(-B[i]);
			F[S].add(v1 - B[i], -1); F[S].add(v1, 1);
			F[S].add(v2 - B[i], -1); F[S].add(v2, 1);
		}
		//cout << i << ": "; for (int j = 0; j < F[P[i]].getsize(); j++) cout << F[P[i]].getvalue(j) << " "; cout << endl;
	}
	long long LastAnswer = rem, cx = 0;
	for (int i = 0; i < F[1].getsize() - 1; i++) {
		long long val = F[1].getvalue(i); //cout << val << endl;
		LastAnswer -= (F[1].getsize() - i - 1)*(val - cx); cx = val;
	}
	cout << LastAnswer << endl;
	return 0;
}

Compilation message

fireworks.cpp:7:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
fireworks.cpp: In function 'int main()':
fireworks.cpp:59:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= N + M; i++) { for (int j = 0; j < G[i].size(); j++) dist[G[i][j].first] += dist[i] + G[i][j].second; }
                                                     ~~^~~~~~~~~~~~~
fireworks.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[i].size(); j++) {
                    ~~^~~~~~~~~~~~~
fireworks.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[i].size(); j++) {
                    ~~^~~~~~~~~~~~~
fireworks.cpp:83:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[i].size() - 1; j++) { long long v1 = F[S].getvalue(F[S].getsize() - 1); F[S].add(v1, -1); }
                    ~~^~~~~~~~~~~~~~~~~
fireworks.cpp:58:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 2; i <= N + M; i++) { scanf("%lld%lld", &A[i], &B[i]); rem += B[i]; G[A[i]].push_back(make_pair(i, B[i])); }
                                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	19192 KB	Output is correct
2	Correct	19 ms	19192 KB	Output is correct
3	Correct	16 ms	19372 KB	Output is correct
4	Correct	16 ms	19372 KB	Output is correct
5	Correct	16 ms	19500 KB	Output is correct
6	Correct	16 ms	19520 KB	Output is correct
7	Correct	16 ms	19520 KB	Output is correct
8	Correct	16 ms	19520 KB	Output is correct
9	Correct	16 ms	19520 KB	Output is correct
10	Correct	17 ms	19520 KB	Output is correct

Subtask #2
19.0 / 19.0

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

Subtask #3
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	19192 KB	Output is correct
2	Correct	19 ms	19192 KB	Output is correct
3	Correct	16 ms	19372 KB	Output is correct
4	Correct	16 ms	19372 KB	Output is correct
5	Correct	16 ms	19500 KB	Output is correct
6	Correct	16 ms	19520 KB	Output is correct
7	Correct	16 ms	19520 KB	Output is correct
8	Correct	16 ms	19520 KB	Output is correct
9	Correct	16 ms	19520 KB	Output is correct
10	Correct	17 ms	19520 KB	Output is correct
11	Correct	16 ms	19520 KB	Output is correct
12	Correct	16 ms	19520 KB	Output is correct
13	Correct	16 ms	19520 KB	Output is correct
14	Correct	16 ms	19520 KB	Output is correct
15	Correct	16 ms	19520 KB	Output is correct
16	Correct	17 ms	19520 KB	Output is correct
17	Correct	17 ms	19520 KB	Output is correct
18	Correct	17 ms	19520 KB	Output is correct
19	Correct	18 ms	19520 KB	Output is correct
20	Correct	16 ms	19520 KB	Output is correct
21	Correct	17 ms	19520 KB	Output is correct
22	Correct	17 ms	19520 KB	Output is correct
23	Correct	17 ms	19520 KB	Output is correct
24	Correct	16 ms	19520 KB	Output is correct
25	Correct	17 ms	19520 KB	Output is correct
26	Correct	17 ms	19540 KB	Output is correct
27	Correct	18 ms	19604 KB	Output is correct
28	Correct	19 ms	19652 KB	Output is correct
29	Correct	18 ms	19652 KB	Output is correct
30	Incorrect	20 ms	19912 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	19192 KB	Output is correct
2	Correct	19 ms	19192 KB	Output is correct
3	Correct	16 ms	19372 KB	Output is correct
4	Correct	16 ms	19372 KB	Output is correct
5	Correct	16 ms	19500 KB	Output is correct
6	Correct	16 ms	19520 KB	Output is correct
7	Correct	16 ms	19520 KB	Output is correct
8	Correct	16 ms	19520 KB	Output is correct
9	Correct	16 ms	19520 KB	Output is correct
10	Correct	17 ms	19520 KB	Output is correct
11	Correct	16 ms	19520 KB	Output is correct
12	Correct	16 ms	19520 KB	Output is correct
13	Correct	16 ms	19520 KB	Output is correct
14	Correct	16 ms	19520 KB	Output is correct
15	Correct	16 ms	19520 KB	Output is correct
16	Correct	17 ms	19520 KB	Output is correct
17	Correct	17 ms	19520 KB	Output is correct
18	Correct	17 ms	19520 KB	Output is correct
19	Correct	18 ms	19520 KB	Output is correct
20	Correct	16 ms	19520 KB	Output is correct
21	Correct	17 ms	19520 KB	Output is correct
22	Correct	17 ms	19520 KB	Output is correct
23	Correct	17 ms	19520 KB	Output is correct
24	Correct	16 ms	19520 KB	Output is correct
25	Correct	17 ms	19520 KB	Output is correct
26	Correct	17 ms	19540 KB	Output is correct
27	Correct	18 ms	19604 KB	Output is correct
28	Correct	19 ms	19652 KB	Output is correct
29	Correct	18 ms	19652 KB	Output is correct
30	Incorrect	20 ms	19912 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

답안 #47704

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 19.0 / 19.0

Subtask #3 0 / 29.0

Subtask #4 0 / 45.0

Subtask #1
7.0 / 7.0

Subtask #2
19.0 / 19.0

Subtask #3
0 / 29.0

Subtask #4
0 / 45.0