oj.uz

Submission #119228

# Submission time Handle Problem Language Result Execution time Memory
119228 2019-06-20T16:59:45 Z patrikpavic2 Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 1790 ms 68088 KB 
#include "railroad.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>

#define X first
#define Y second
#define PB push_back

using namespace __gnu_pbds;
using namespace std;

typedef vector < int > vi;
typedef long long ll;
typedef pair < int , int > pii;
typedef vector < pii > vp;

const int INF = 0x3f3f3f3f;
const int N = 4e5 + 500;

bool cmp(pii A, pii B){
	if(A.X - A.Y == B.X - B.Y) return A.X < A.Y;
	return A.X - A.Y > B.X - B.Y;
}

int n, m;
vector < int > v;
vector < pii > e;
gp_hash_table < int , int > deg, par, out;

int pr(int x){
	if(!par[x]) return par[x] = x;
	if(x == par[x]) return x;
	return par[x] = pr(par[x]);
}

void mrg(int x,int y){
	par[pr(x)] = pr(y);
}

ll plan_roller_coaster(vi s, vi t) {
	n = s.size();
	for(int i = 0;i < n;i++){
		deg[s[i]]++; deg[t[i]]--;
		v.PB(s[i]), v.PB(t[i]);
		mrg(s[i], t[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	n = (int)v.size();
	ll sol = 0;
	for(int i = 0;i < n;i++){
		out[v[i]] = out[v[i - 1]] - deg[v[i]] + (i == 0) - (i == n - 1);
		if(out[v[i]] < 0 && i != n - 1){
			mrg(v[i], v[i + 1]);
			sol -= (ll)(v[i + 1] - v[i]) * out[v[i]];
		}
		if(out[v[i]] == 0 && i != n - 1){
			e.PB({v[i], v[i + 1]});
		}
		if(out[v[i]] > 0 && i != n - 1){
			mrg(v[i], v[i + 1]);
		}
		//printf("OUT %d je %d\n:", v[i], out[v[i]]);
	}
	//printf("SOL	= %lld\n", sol);
	sort(e.begin(), e.end(), cmp);
	for(int i = 0;i < e.size();i++){
		if(pr(e[i].X) != pr(e[i].Y)){
			mrg(e[i].X, e[i].Y);
			sol += e[i].Y - e[i].X;
		}
	}
	return sol;
}

Compilation message

railroad.cpp: In function 'll plan_roller_coaster(vi, vi)':
railroad.cpp:72:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < e.size();i++){
                ~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 2
2 Correct 2 ms 384 KB n = 2
3 Correct 2 ms 384 KB n = 2
4 Correct 2 ms 256 KB n = 2
5 Correct 2 ms 256 KB n = 2
6 Correct 2 ms 384 KB n = 2
7 Correct 2 ms 256 KB n = 3
8 Correct 2 ms 384 KB n = 3
9 Correct 2 ms 384 KB n = 3
10 Correct 2 ms 384 KB n = 8
11 Correct 2 ms 384 KB n = 8
12 Correct 2 ms 384 KB n = 8
13 Correct 2 ms 384 KB n = 8
14 Correct 2 ms 384 KB n = 8
15 Correct 2 ms 384 KB n = 8
16 Correct 2 ms 384 KB n = 8
17 Correct 2 ms 384 KB n = 8
18 Correct 2 ms 384 KB n = 8
19 Correct 2 ms 256 KB n = 3
20 Correct 2 ms 256 KB n = 7
21 Correct 2 ms 384 KB n = 8
22 Correct 2 ms 256 KB n = 8
23 Correct 2 ms 384 KB n = 8
24 Correct 1 ms 384 KB n = 8
25 Correct 2 ms 384 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 2
2 Correct 2 ms 384 KB n = 2
3 Correct 2 ms 384 KB n = 2
4 Correct 2 ms 256 KB n = 2
5 Correct 2 ms 256 KB n = 2
6 Correct 2 ms 384 KB n = 2
7 Correct 2 ms 256 KB n = 3
8 Correct 2 ms 384 KB n = 3
9 Correct 2 ms 384 KB n = 3
10 Correct 2 ms 384 KB n = 8
11 Correct 2 ms 384 KB n = 8
12 Correct 2 ms 384 KB n = 8
13 Correct 2 ms 384 KB n = 8
14 Correct 2 ms 384 KB n = 8
15 Correct 2 ms 384 KB n = 8
16 Correct 2 ms 384 KB n = 8
17 Correct 2 ms 384 KB n = 8
18 Correct 2 ms 384 KB n = 8
19 Correct 2 ms 256 KB n = 3
20 Correct 2 ms 256 KB n = 7
21 Correct 2 ms 384 KB n = 8
22 Correct 2 ms 256 KB n = 8
23 Correct 2 ms 384 KB n = 8
24 Correct 1 ms 384 KB n = 8
25 Correct 2 ms 384 KB n = 8
26 Correct 2 ms 300 KB n = 8
27 Correct 2 ms 384 KB n = 8
28 Correct 2 ms 384 KB n = 8
29 Correct 2 ms 256 KB n = 16
30 Correct 2 ms 256 KB n = 16
31 Correct 1 ms 256 KB n = 16
32 Correct 2 ms 384 KB n = 16
33 Correct 2 ms 384 KB n = 16
34 Correct 2 ms 384 KB n = 16
35 Correct 2 ms 384 KB n = 16
36 Correct 2 ms 384 KB n = 15
37 Correct 2 ms 384 KB n = 8
38 Correct 2 ms 256 KB n = 16
39 Correct 2 ms 384 KB n = 16
40 Correct 2 ms 384 KB n = 9
41 Correct 2 ms 384 KB n = 16
42 Correct 2 ms 384 KB n = 16
43 Correct 2 ms 384 KB n = 16
44 Correct 2 ms 256 KB n = 9
45 Correct 2 ms 384 KB n = 15
46 Correct 2 ms 256 KB n = 16
47 Correct 2 ms 256 KB n = 16
48 Correct 2 ms 384 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 54740 KB n = 199999
2 Correct 433 ms 54848 KB n = 199991
3 Correct 428 ms 54976 KB n = 199993
4 Correct 346 ms 53824 KB n = 152076
5 Correct 199 ms 27488 KB n = 93249
6 Correct 258 ms 54756 KB n = 199910
7 Correct 321 ms 54864 KB n = 199999
8 Correct 248 ms 54756 KB n = 199997
9 Correct 379 ms 54352 KB n = 171294
10 Correct 327 ms 53460 KB n = 140872
11 Correct 258 ms 54992 KB n = 199886
12 Correct 335 ms 55828 KB n = 199996
13 Correct 326 ms 56016 KB n = 200000
14 Correct 1247 ms 57700 KB n = 199998
15 Correct 1790 ms 60004 KB n = 200000
16 Correct 703 ms 60236 KB n = 199998
17 Correct 501 ms 68056 KB n = 200000
18 Correct 397 ms 58964 KB n = 190000
19 Correct 348 ms 65984 KB n = 177777
20 Correct 196 ms 29544 KB n = 100000
21 Correct 405 ms 58856 KB n = 200000
22 Correct 487 ms 58704 KB n = 200000
23 Correct 501 ms 58688 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 2
2 Correct 2 ms 384 KB n = 2
3 Correct 2 ms 384 KB n = 2
4 Correct 2 ms 256 KB n = 2
5 Correct 2 ms 256 KB n = 2
6 Correct 2 ms 384 KB n = 2
7 Correct 2 ms 256 KB n = 3
8 Correct 2 ms 384 KB n = 3
9 Correct 2 ms 384 KB n = 3
10 Correct 2 ms 384 KB n = 8
11 Correct 2 ms 384 KB n = 8
12 Correct 2 ms 384 KB n = 8
13 Correct 2 ms 384 KB n = 8
14 Correct 2 ms 384 KB n = 8
15 Correct 2 ms 384 KB n = 8
16 Correct 2 ms 384 KB n = 8
17 Correct 2 ms 384 KB n = 8
18 Correct 2 ms 384 KB n = 8
19 Correct 2 ms 256 KB n = 3
20 Correct 2 ms 256 KB n = 7
21 Correct 2 ms 384 KB n = 8
22 Correct 2 ms 256 KB n = 8
23 Correct 2 ms 384 KB n = 8
24 Correct 1 ms 384 KB n = 8
25 Correct 2 ms 384 KB n = 8
26 Correct 2 ms 300 KB n = 8
27 Correct 2 ms 384 KB n = 8
28 Correct 2 ms 384 KB n = 8
29 Correct 2 ms 256 KB n = 16
30 Correct 2 ms 256 KB n = 16
31 Correct 1 ms 256 KB n = 16
32 Correct 2 ms 384 KB n = 16
33 Correct 2 ms 384 KB n = 16
34 Correct 2 ms 384 KB n = 16
35 Correct 2 ms 384 KB n = 16
36 Correct 2 ms 384 KB n = 15
37 Correct 2 ms 384 KB n = 8
38 Correct 2 ms 256 KB n = 16
39 Correct 2 ms 384 KB n = 16
40 Correct 2 ms 384 KB n = 9
41 Correct 2 ms 384 KB n = 16
42 Correct 2 ms 384 KB n = 16
43 Correct 2 ms 384 KB n = 16
44 Correct 2 ms 256 KB n = 9
45 Correct 2 ms 384 KB n = 15
46 Correct 2 ms 256 KB n = 16
47 Correct 2 ms 256 KB n = 16
48 Correct 2 ms 384 KB n = 16
49 Correct 409 ms 54740 KB n = 199999
50 Correct 433 ms 54848 KB n = 199991
51 Correct 428 ms 54976 KB n = 199993
52 Correct 346 ms 53824 KB n = 152076
53 Correct 199 ms 27488 KB n = 93249
54 Correct 258 ms 54756 KB n = 199910
55 Correct 321 ms 54864 KB n = 199999
56 Correct 248 ms 54756 KB n = 199997
57 Correct 379 ms 54352 KB n = 171294
58 Correct 327 ms 53460 KB n = 140872
59 Correct 258 ms 54992 KB n = 199886
60 Correct 335 ms 55828 KB n = 199996
61 Correct 326 ms 56016 KB n = 200000
62 Correct 1247 ms 57700 KB n = 199998
63 Correct 1790 ms 60004 KB n = 200000
64 Correct 703 ms 60236 KB n = 199998
65 Correct 501 ms 68056 KB n = 200000
66 Correct 397 ms 58964 KB n = 190000
67 Correct 348 ms 65984 KB n = 177777
68 Correct 196 ms 29544 KB n = 100000
69 Correct 405 ms 58856 KB n = 200000
70 Correct 487 ms 58704 KB n = 200000
71 Correct 501 ms 58688 KB n = 200000
72 Correct 455 ms 58816 KB n = 200000
73 Correct 448 ms 58744 KB n = 200000
74 Correct 437 ms 58836 KB n = 200000
75 Correct 368 ms 58688 KB n = 200000
76 Correct 364 ms 58824 KB n = 200000
77 Correct 203 ms 33520 KB n = 200000
78 Correct 259 ms 33664 KB n = 200000
79 Correct 382 ms 57976 KB n = 184307
80 Correct 155 ms 28516 KB n = 76040
81 Correct 246 ms 57576 KB n = 199981
82 Correct 381 ms 59712 KB n = 199994
83 Correct 354 ms 59104 KB n = 199996
84 Correct 1207 ms 61644 KB n = 199998
85 Correct 1738 ms 59216 KB n = 200000
86 Correct 691 ms 59720 KB n = 199998
87 Correct 426 ms 68068 KB n = 200000
88 Correct 415 ms 60728 KB n = 200000
89 Correct 391 ms 68088 KB n = 200000
90 Correct 377 ms 58816 KB n = 200000
91 Correct 475 ms 58780 KB n = 200000
92 Correct 474 ms 58688 KB n = 200000