Submission #256146

#	Time	Username	Problem	Language	Result	Execution time	Memory
256146		mode149256	Islands (IOI08_islands)	C++14	100 / 100	1216 ms	131072 KiB

islands

/*input
400
245 1112000
273 44035120
242 48964512
17 30894509
127 70417999
169 28820774
370 62498770
167 26683980
208 61785405
340 17785921
341 91950134
345 76191742
124 89707749
138 37204040
157 93178791
64 67293709
140 8918158
330 25757968
308 62811196
29 85524584
219 26078757
116 14778021
134 10002523
150 26882859
222 60355055
256 78623003
82 44244421
303 28583419
214 84315280
243 31475944
238 52643431
57 29600906
76 29681499
141 93641309
144 65868129
39 20647631
375 18845770
24 87194216
234 18244187
55 38150014
248 32330809
334 20957846
258 70531529
60 18622031
38 42054529
163 64457665
152 93980212
282 38749254
362 58947440
266 40393727
288 36683306
310 49467289
394 52230283
372 50376232
211 20845228
297 80511277
390 2013682
59 53517159
301 60050632
397 16358186
263 25725447
108 12529940
398 31233496
268 96284606
122 76257606
321 41005554
391 52932835
220 51166078
399 30338253
257 29831288
68 1617903
275 60066568
51 43235686
154 76934494
388 88033674
164 47462815
166 32049482
395 75630378
5 23654983
63 99386745
139 98599175
195 87635946
95 58401755
159 58061127
118 94313664
284 35646267
43 45873511
249 74649884
90 8251012
367 34128230
111 88615048
179 57319643
371 38527780
389 92528183
361 14700419
246 37811953
46 67688791
132 9361666
306 57104962
66 63455256
364 65771064
93 87979113
255 21271935
71 17681409
396 57882042
14 63140119
176 4918849
27 18893993
31 16011269
81 31969365
62 38400583
313 61348937
377 64741733
15 21059359
329 44825105
239 25257041
192 52910242
215 29369632
137 89128424
135 88170698
296 30657656
153 64388056
112 81998915
386 15981573
194 46808110
21 28545866
128 73491236
289 17431367
328 47524729
325 48629899
96 74804439
223 47756709
213 26446221
146 21380952
236 56422735
186 54756027
378 96024556
319 36798212
203 26578215
115 74319357
253 73253022
158 87438256
12 92223064
121 93406109
92 66345971
56 97009394
133 56624444
374 95329232
291 87186247
155 72536887
142 83391033
22 90577351
67 23256128
77 95571667
354 92675844
10 35997280
295 84273980
285 88139767
170 23309976
382 3229205
48 27294919
33 23912376
254 4432934
42 20723358
49 81971177
188 72718379
119 37821494
337 99222306
102 17590518
366 72523963
106 72274388
168 21091358
129 21921174
226 40814775
187 34469230
348 58442874
237 83567599
11 6902949
200 65053888
324 73872198
218 5753914
356 45791616
270 19076724
7 56227928
232 32552164
143 23167238
290 44638732
323 60073430
379 14311560
86 84699142
180 73796421
25 20786815
65 20807546
189 80484266
105 38070303
174 76402627
183 32349969
199 79056837
332 1589903
358 75269335
221 14432413
74 84529918
336 68190153
318 43299458
247 39765345
161 14920087
363 25882996
101 32210831
393 86899525
97 72588832
315 53965794
113 99596507
99 89219951
292 17780579
298 9272718
125 54519651
58 37353943
376 13004702
339 23788147
342 18029511
109 88457635
184 33009705
227 89895998
4 62153572
228 9653039
114 86682283
72 43435953
156 52465225
349 74923540
204 22076916
347 53950479
85 1895222
126 94004687
274 49581455
369 65404127
277 41735865
387 58342872
217 32253895
381 18882709
34 40025556
287 47510689
250 54250697
148 2876017
272 6374712
193 66400577
196 87671530
338 81730568
182 69816729
259 59744787
73 85600162
212 65093182
269 69598329
172 69926996
94 6067997
360 55876454
276 96249408
279 48400342
343 35933597
224 36603142
54 33491883
206 50526709
251 17845677
123 61535093
147 9858879
307 15626657
278 37686743
41 34048428
383 27377901
37 92210544
107 32654030
346 67803423
190 84704557
241 82924475
230 78270075
331 74593315
202 34836248
293 7359133
280 972677
89 45962457
271 49438947
80 20625202
317 24382056
327 8002287
30 47047388
352 70786484
173 4729932
351 11354417
185 42692910
45 36307104
365 17517312
131 78379551
355 49850880
130 95680437
151 90422902
304 88849111
300 75949165
20 60512077
120 68310861
2 34704892
78 71482299
16 75881353
264 9499066
302 17476074
165 54395964
160 1895500
98 60747331
197 11816291
235 95382011
91 4168347
79 65086089
265 47162509
359 71521295
53 76342044
149 3077678
385 96623541
87 58699985
322 50760553
350 43158883
104 5197343
52 83260368
305 1462309
35 86997042
175 5474548
335 79334027
252 55487172
225 6746067
392 91468499
312 11475901
299 15258530
40 88289379
231 97762085
201 73068414
26 80724854
368 8928155
110 56467649
240 82435945
36 41769441
75 68727410
117 68472274
314 74326614
191 34817703
88 10761747
50 65683480
181 47804786
261 6430487
8 51620054
326 31049316
13 27913379
309 74995176
198 96789780
61 66697989
267 96035093
320 46466387
229 592111
162 67527341
207 59954083
205 82441854
311 88399731
6 42076897
209 43733908
216 17220083
3 96290004
244 18483373
70 5050576
353 8964597
103 63561275
69 39964507
294 63565814
178 61916874
333 45059857
1 69619565
262 9497203
283 27989948
145 70832238
100 50832083
373 52104178
28 93293062
400 15106373
136 56409678
9 3664384
19 32705112
23 1075890
171 55101854
47 6004178
44 64969722
233 70907359
84 8283577
177 99578149
281 91034974
286 20113403
210 11901358
384 46589313
380 31191973
260 91656204
316 75873032
32 78267262
344 58922271
83 70009188
18 4294289
357 74891255

*/
#include <bits/stdc++.h>
using namespace std;

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 1000010;

int N;
vpi edges(MX);
vpii edgesVisos(MX);
vb been(MX, false);

vl circle; // lens
vi circleV;
vb inCircle(MX, false);

ll ats = 0;
ll proc = 0;
ll maxDis = 0;
int kur;

void fill(int x) {
	been[x] = true;

	for (auto u : edgesVisos[x])
		if (!been[u.x])
			fill(u.x);
}

// -1 ner rato
int find_circle(int x) {
	been[x] = true;

	auto u = edges[x];
	if (been[u.x]) {
		// printf("x = %d, u = %d %d\n", x, u.x, u.y);
		circleV.emplace_back(x);
		circle.emplace_back(u.y);
		been[x] = false;
		return u.x;
	}

	int k = find_circle(u.x);

	if (k == x) {
		// printf("x = %d, u = %d %d\n", x, u.x, u.y);
		circleV.emplace_back(x);
		circle.emplace_back(u.y);
		been[x] = false;
		return -1;
	}
	else if (k != -1) {
		// printf("x = %d, u = %d %d\n", x, u.x, u.y);
		circleV.emplace_back(x);
		circle.emplace_back(u.y);
		been[x] = false;
		return k;
	}

	been[x] = false;
	return -1;
}

void longest(int x, int p, ll dis) {
	if (dis > maxDis) {
		maxDis = dis;
		kur = x;
	}

	for (auto u : edgesVisos[x]) {
		if (u.x == p or inCircle[u.x]) continue;
		longest(u.x, x, dis + u.y);
	}
}

void solve() {
	proc = 0;
	for (auto u : circleV)
		inCircle[u] = true;

	int C = (int)circleV.size();

	vl D(C, 0);

	for (int i = 0; i < C; ++i)
	{
		int x = circleV[i];
		vl kokie;

		for (auto u : edgesVisos[x]) {
			if (inCircle[u.x]) continue;
			maxDis = 0;
			longest(u.x, x, u.y);
			proc = max(proc, maxDis);
			kokie.push_back(maxDis);

			D[i] = max(D[i], maxDis);

			maxDis = 0;
			longest(kur, -1, 0);
			proc = max(proc, maxDis);

			// printf("i = %d, d = %d\n", i, D[i]);
		}

		if (kokie.size() >= 2) {
			sort(kokie.rbegin(), kokie.rend());
			proc = max(proc, kokie[0] + kokie[1]);
		}
	}

	// for (int i = 0; i < C; ++i) printf("v = %d, dis = %lld\n", circleV[i]+1, D[i]);

	deque<pl> dq;
	ll viso = 0;
	for (int i = 0; i < C; ++i) viso += circle[i];

	{
		for (int i = 1; i < C; ++i)
		{
			circle[i] += circle[i - 1];
			ll newVal = circle[i - 1] + D[i];

			while (dq.size() and dq.back().x <= newVal)
				dq.pop_back();

			dq.push_back({newVal, i});
		}

		for (int i = 0; i < C; ++i)
		{
			while (dq.size() and dq.front().y <= i) {
				dq.pop_front();
			}

			assert(dq.size());
			// printf("dq = %lld, circle = %lld\n", dq.front().x, (i ? circle[i - 1] : 0));
			proc = max(proc, dq.front().x + D[i] - (i ? circle[i - 1] : 0));

			ll newVal = D[i] + viso + (i ? circle[i - 1] : 0);
			while (dq.size() and dq.back().x <= newVal)
				dq.pop_back();

			dq.push_back({newVal, i + C});
		}
	}

	ats += proc;
	// printf("cnt = %d, proc = %lld ", C, proc);
	// for(auto u: circle) printf("%lld ", u);
	// printf("%lld %lld\n", D[0], D[1]);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int a, w;
		cin >> a >> w; a--;

		// edges[a].emplace_back(i, w);
		edges[i] = {a, w};

		// printf("%d %d %d\n", i, a, w);
		edgesVisos[i].emplace_back(a, w);
		edgesVisos[a].emplace_back(i, w);
	}


	for (int i = 0; i < N; ++i)
	{
		if (been[i]) continue;

		circle.clear();
		circleV.clear();

		find_circle(i);
		fill(i);
		reverse(circle.begin(), circle.end());
		reverse(circleV.begin(), circleV.end());

		// for (auto u : circleV)
		// 	printf("%d ", u + 1);
		// printf("\n");
		// for (auto u : circle)
		// 	printf("%lld ", u);
		// printf("\n");

		solve();
	}

	printf("%lld\n", ats);
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10