CSES - APIO 2014

CSES - APIO 2014 - Results

Submission details
Task:	Beads and wires
Sender:	Olli
Submission time:	2019-03-24 17:39:21 +0200
Language:	C++
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0
#4	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.02 s	1, 2, 3, 4	details
#2	ACCEPTED	0.02 s	1, 2, 3, 4	details
#3	ACCEPTED	0.03 s	1, 2, 3, 4	details
#4	ACCEPTED	0.02 s	1, 2, 3, 4	details
#5	ACCEPTED	0.03 s	1, 2, 3, 4	details
#6	ACCEPTED	0.03 s	1, 2, 3, 4	details
#7	WRONG ANSWER	0.01 s	1, 2, 3, 4	details
#8	ACCEPTED	0.02 s	1, 2, 3, 4	details
#9	ACCEPTED	0.02 s	1, 2, 3, 4	details
#10	ACCEPTED	0.02 s	1, 2, 3, 4	details
#11	ACCEPTED	0.02 s	1, 2, 3, 4	details
#12	ACCEPTED	0.03 s	1, 2, 3, 4	details
#13	WRONG ANSWER	0.03 s	2, 3, 4	details
#14	WRONG ANSWER	0.02 s	2, 3, 4	details
#15	WRONG ANSWER	0.03 s	2, 3, 4	details
#16	WRONG ANSWER	0.03 s	2, 3, 4	details
#17	WRONG ANSWER	0.02 s	2, 3, 4	details
#18	WRONG ANSWER	0.02 s	2, 3, 4	details
#19	WRONG ANSWER	0.02 s	2, 3, 4	details
#20	WRONG ANSWER	0.02 s	2, 3, 4	details
#21	WRONG ANSWER	0.04 s	2, 3, 4	details
#22	WRONG ANSWER	0.03 s	2, 3, 4	details
#23	WRONG ANSWER	0.03 s	3, 4	details
#24	WRONG ANSWER	0.03 s	3, 4	details
#25	WRONG ANSWER	0.03 s	3, 4	details
#26	WRONG ANSWER	0.04 s	3, 4	details
#27	WRONG ANSWER	0.04 s	3, 4	details
#28	WRONG ANSWER	0.05 s	3, 4	details
#29	WRONG ANSWER	0.04 s	3, 4	details
#30	WRONG ANSWER	0.04 s	3, 4	details
#31	WRONG ANSWER	0.04 s	3, 4	details
#32	WRONG ANSWER	0.10 s	4	details
#33	WRONG ANSWER	0.10 s	4	details
#34	WRONG ANSWER	0.10 s	4	details
#35	WRONG ANSWER	0.37 s	4	details
#36	WRONG ANSWER	0.38 s	4	details
#37	WRONG ANSWER	0.38 s	4	details
#38	WRONG ANSWER	0.35 s	4	details
#39	WRONG ANSWER	0.34 s	4	details
#40	WRONG ANSWER	0.35 s	4	details
#41	WRONG ANSWER	0.38 s	4	details

Compiler report

input/code.cpp: In function 'void dfs(int)':
input/code.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < g[i].size(); ++j) {
                 ~~^~~~~~~~~~~~~
input/code.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < g[i].size(); ++j) {
                 ~~^~~~~~~~~~~~~
input/code.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < g[i].size(); ++j) {
                 ~~^~~~~~~~~~~~~
input/code.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~
input/code.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~
input/code.cpp:126:21: warning: comparison be...

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_map>
#include <math.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5 + 5;
const ll INF = 1e18;
vector<pll> g[N];

int p[N];
bool z[N];

ll maxMissOne[N];
ll noUse[N];
ll mayUse[N];
ll indParent[N];

void dfs(int i) {
	if(z[i]) return;
	z[i] = true;
	for(int j = 0; j < g[i].size(); ++j) {
		int k = g[i][j].first;
		if(p[k] == 0) {
			p[k] = i;
			dfs(k);
		} else {
			indParent[i] = j;
		}
	}
	if(g[i].size() == 1 && i != 1) {
		noUse[i] = 0;
		mayUse[i] = 0;
		maxMissOne[i] = -INF;
		return;
	}

	//Calculate noUse
	int maxInd = -1;
	ll maxProf = -INF;
	for(int j = 0; j < g[i].size(); ++j) {
		int k = g[i][j].first;
		ll prof = mayUse[k] - noUse[k];
		if(prof >= maxProf) {
			maxInd = j;
			maxProf = prof;
		}
	}

	ll noUs = 0;
	for(int j = 0; j < g[i].size(); ++j) {
		int k = g[i][j].first;
		if(p[i] == k) continue;
		ll cand1 = mayUse[k];
		ll cand2 = maxMissOne[k] + g[i][j].second;
		if(j == maxInd) {
			noUs += max(cand1, cand2);
		} else {
			cand1 = noUse[k];
			noUs += max(cand1, cand2);
		}
	}
	noUse[i] = noUs;
	//Calculate mayUse
	mayUse[i] = noUs;
	/*
	We may give two kinds of rewards: neighbor and mayUse
	Case 1. Overlap
		The remaining neighbor can be easily determined (the one suffering least from not getting maxMissOne[k] + g[i, k])
	Case 2. No overlap
		The neighboring nodes can be easily determined (the ones ...)		
	*/
	ll child = g[i].size() - 1; if(i == 1) child+=1;
	if(child >= 2) {

		//Case 1.
		vector<pll> suffer;
		vector<ll> term;
		ll sum = 0;
		for(int j = 0; j < g[i].size(); ++j) {
			int k = g[i][j].first;
			if(k == p[i]) {
				term.push_back(-INF);
				continue;
			}
			ll suff = max(maxMissOne[k] + g[i][j].second, noUse[k]) - (noUse[k] + g[i][j].second);
			suffer.push_back({suff, j});
			ll te = max(noUse[k], maxMissOne[k] + g[i][j].second);
			sum += te;
			term.push_back(te);
		}
		sort(suffer.begin(), suffer.end());

		for(int j = 0; j < g[i].size(); ++j) {
			int k = g[i][j].first;
			if(k == p[i]) continue;
			//Give overlap to node k

			ll ans = sum;
			ans -= term[j];
			ans += g[i][j].second + mayUse[k];
			ll fir = suffer[0].second;
			if(g[i][fir].first == k) {
				fir = suffer[1].second;
			}
			ans -= term[fir];
			ll nodeFir = g[i][fir].first;
			ans += g[nodeFir][indParent[nodeFir]].second + noUse[nodeFir];
			if(i == 1) {
//				cout << k << " " << ans << " .\n";
//				cout << sum << " " << term[j] << " " << g[i][j].second + mayUse[k] << "\n";
//				cout << fir << " " << nodeFir << " " << term[fir] << " " << g[nodeFir][indParent[nodeFir]].second + noUse[nodeFir] << "\n\n";
			}
			mayUse[i] = max(mayUse[i], ans);
		}
		//Case 2.
		if(child >= 3) {

			for(int j = 0; j < g[i].size(); ++j) {
				int k = g[i][j].first;
				if(k == p[i]) continue;
				//Give mayUse to k - "must" use
				ll ans = sum;
				ans -= term[j];
				ans += mayUse[k];
				ll fir = suffer[0].second;
				if(g[i][fir].first == k) {
					fir = suffer[1].second;
				}
				ll sec = suffer[1].second;
				if(sec == fir || g[i][sec].first == k) {
					sec = suffer[2].second;
				}

				ans -= term[fir];
				ans -= term[sec];
				fir = g[i][fir].first;
				sec = g[i][sec].first;
				ans += g[fir][indParent[fir]].second + noUse[fir];
				ans += g[sec][indParent[sec]].second + noUse[sec];
				mayUse[i] = max(mayUse[i], ans);
			}
		}

	}

	//Calculate maxMissOne

	ll sumChildren = 0;
	for(int j = 0; j < g[i].size(); ++j) {
		int k = g[i][j].first;
		if(p[i] == k) continue;
		sumChildren += max(mayUse[k], maxMissOne[k] + g[i][j].second);
	}

	for(int j = 0; j < g[i].size(); ++j) {
		int k = g[i][j].first;
		if(p[i] == k) continue;
		ll cand = sumChildren - max(mayUse[k], maxMissOne[k] + g[i][j].second) + g[i][j].second + mayUse[k];
		maxMissOne[i] = max(maxMissOne[i], cand);
	}
}

int main() {
	int n;
	cin >> n;
	for(int i = 1; i< n; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a].push_back(pii{b, c});
		g[b].push_back(pii{a, c});
	}

	p[1] = -1;
	dfs(1);

	for(int i = 1; i <= n; ++i) {
//		cout << i << " " << noUse[i] << " " << mayUse[i] << " " << maxMissOne[i] << "\n";
	}


	cout << mayUse[1] << "\n";
}

Test details

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`5 1 2 10 1 3 40 1 4 15 1 5 20` view save

correct output
`60` view save

user output
`60` view save

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 4 10 2 1 2 21 1 3 13 6 7 1 ...` view save

correct output
`140` view save

user output
`140` view save

Test 3

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 4 10 5 1 10 7 3 10 10 3 9 10 ...` view save

correct output
`61` view save

user output
`61` view save

Test 4

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 7 10 1 2 7 3 6 7 5 1 9 5 ...` view save

correct output
`30` view save

user output
`30` view save

Test 5

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 3 10 6 3 7 6 8 9 3 1 5 1 ...` view save

correct output
`44` view save

user output
`44` view save

Test 6

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 5 6 9 2 3 5 1 10 8 4 5 9 ...` view save

correct output
`62` view save

user output
`62` view save

Test 7

Group: 1, 2, 3, 4

Verdict: WRONG ANSWER

input
`10 2 3 7 6 9 7 2 10 6 4 9 2 ...` view save

correct output
`41` view save

user output
`47` view save

Test 8

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 7 9 1 3 5 9 1 6 3 5 9 3 ...` view save

correct output
`53` view save

user output
`53` view save

Test 9

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 3 6 9 2 5 5 2 4 1 4 9 2 ...` view save

correct output
`43` view save

user output
`43` view save

Test 10

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 2 3 4 4 8 9 1 8 2 2 4 6 ...` view save

correct output
`39` view save

user output
`39` view save

Test 11

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 1 8 4 2 3 7 3 10 4 2 4 7 ...` view save

correct output
`48` view save

user output
`48` view save

Test 12

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 8 9 7 2 3 8 2 6 5 2 9 1 ...` view save

correct output
`35` view save

user output
`35` view save

Test 13

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`100 48 93 4 12 87 1 27 72 10 3 43 2 ...` view save

correct output
`441` view save

user output
`469` view save

Test 14

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`100 38 97 8 26 29 9 62 73 7 13 62 8 ...` view save

correct output
`498` view save

user output
`521` view save

Test 15

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`100 13 54 5 7 94 5 9 39 7 52 53 8 ...` view save

correct output
`460` view save

user output
`486` view save

Test 16

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`200 147 182 33 101 186 14 7 66 10 73 180 33 ...` view save

correct output
`4537` view save

user output
`4845` view save

Test 17

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`200 33 93 17 63 114 24 19 93 42 151 168 9 ...` view save

correct output
`4605` view save

user output
`4887` view save

Test 18

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`200 25 94 45 143 166 19 24 103 16 133 200 43 ...` view save

correct output
`4695` view save

user output
`5032` view save

Test 19

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`200 74 191 24 74 171 19 2 74 50 27 74 42 ...` view save

correct output
`546` view save

user output
`585` view save

Test 20

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`200 98 200 12 12 87 47 19 98 31 9 87 14 ...` view save

correct output
`233` view save

user output
`292` view save

Test 21

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`200 47 130 8 25 47 15 47 172 33 6 47 45 ...` view save

correct output
`1202` view save

user output
`1216` view save

Test 22

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`200 56 174 43 28 56 22 26 112 21 56 119 44 ...` view save

correct output
`3349` view save

user output
`3414` view save

Test 23

Group: 3, 4

Verdict: WRONG ANSWER

input
`5000 2198 4992 964 2521 2711 961 3408 4585 975 2746 3304 974 ...` view save

correct output
`3848169` view save

user output
`4140711` view save

Test 24

Group: 3, 4

Verdict: WRONG ANSWER

input
`5000 1926 2920 933 565 1093 993 1894 4373 930 1713 3978 916 ...` view save

correct output
`3789162` view save

user output
`4136641` view save

Test 25

Group: 3, 4

Verdict: WRONG ANSWER

input
`5000 2488 4286 905 898 3460 995 3342 4660 963 38 1300 971 ...` view save

correct output
`3818444` view save

user output
`4169616` view save

Test 26

Group: 3, 4

Verdict: WRONG ANSWER

input
`10000 2751 6467 4918 3158 3563 4945 3261 6833 4929 2955 6313 4923 ...` view save

correct output
`40189502` view save

user output
`43370076` view save

Test 27

Group: 3, 4

Verdict: WRONG ANSWER

input
`10000 2180 7493 4923 5745 9205 4949 446 7909 4938 2787 8203 4921 ...` view save

correct output
`40070133` view save

user output
`43015333` view save

Test 28

Group: 3, 4

Verdict: WRONG ANSWER

input
`10000 3748 4584 4926 3748 7419 4990 1194 3748 4924 3748 6181 4996 ...` view save

correct output
`3991669` view save

user output
`4348086` view save

Test 29

Group: 3, 4

Verdict: WRONG ANSWER

input
`10000 1070 4104 4988 2982 3086 4963 7216 8547 4971 1070 7973 4941 ...` view save

correct output
`29901` view save

user output
`29988` view save

Test 30

Group: 3, 4

Verdict: WRONG ANSWER

input
`10000 7902 8933 4901 3764 6085 4995 1621 3537 4934 4050 8356 4996 ...` view save

correct output
`8971361` view save

user output
`8991368` view save

Test 31

Group: 3, 4

Verdict: WRONG ANSWER

input
`10000 3309 7441 4960 5499 9949 4978 339 5089 4928 4076 7951 4916 ...` view save

correct output
`29562255` view save

user output
`30892182` view save

Test 32

Group: 4

Verdict: WRONG ANSWER

input
`50000 22758 25880 990 917 25140 901 10537 30620 913 10368 14209 993 ...` view save

correct output
`38479584` view save

user output
`41605132` view save

Test 33

Group: 4

Verdict: WRONG ANSWER

input
`50000 3238 13619 998 16363 38824 982 27886 39526 947 11705 35966 934 ...` view save

correct output
`38503542` view save

user output
`41616527` view save

Test 34

Group: 4

Verdict: WRONG ANSWER

input
`50000 35799 44598 957 11590 25577 939 4784 35538 999 5004 9994 968 ...` view save

correct output
`38465202` view save

user output
`41595384` view save

Test 35

Group: 4

Verdict: WRONG ANSWER

input
`200000 30736 178178 9996 90079 171554 9980 25124 79152 9901 54905 96160 9925 ...` view save

correct output
`1605459774` view save

user output
`1736090653` view save

Test 36

Group: 4

Verdict: WRONG ANSWER

input
`200000 108342 138357 9984 110960 113525 9938 41108 45029 9990 55734 141188 9963 ...` view save

correct output
`1607393503` view save

user output
`1734714023` view save

Test 37

Group: 4

Verdict: WRONG ANSWER

input
`200000 126722 130360 9943 89278 168087 9902 119299 167497 9901 53594 131583 9919 ...` view save

correct output
`1606037984` view save

user output
`1733164534` view save

Test 38

Group: 4

Verdict: WRONG ANSWER

input
`200000 164755 181587 9909 108623 181587 9979 322 181587 9974 181138 181587 9946 ...` view save

correct output
`160485772` view save

user output
`172594227` view save

Test 39

Group: 4

Verdict: WRONG ANSWER

input
`200000 27257 170181 9998 27257 46336 9911 64710 109131 9958 47607 164375 9999 ...` view save

correct output
`59979` view save

user output
`60000` view save

Test 40

Group: 4

Verdict: WRONG ANSWER

input
`200000 100383 177661 9902 29890 102857 9905 4153 102857 9990 42390 177661 9901 ...` view save

correct output
`360716635` view save

user output
`361220469` view save

Test 41

Group: 4

Verdict: WRONG ANSWER

input
`200000 122137 172111 9908 53871 122137 9978 85117 168845 9993 3821 9227 9906 ...` view save

correct output
`1183642659` view save

user output
`1235231262` view save

APIO 2014

Beads and wires

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Tasks

Submissions (Olli)