oj.uz

Submission #77220

# Submission time Handle Problem Language Result Execution time Memory
77220 2018-09-24T03:14:28 Z shoemakerjo Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 1461 ms 158008 KB 
#include "railroad.h"
#include <bits/stdc++.h>
 
#define ll long long
using namespace std;
 
#define maxv 400010
#define mp make_pair
 
vector<ll> nums;
vector<int> adj[maxv];
int par[maxv];
 
const int inf = 1000000010;
 
int findset(int u) {
	if (par[u] == u) return u;
	return par[u] = findset(par[u]);
}
 
void unionset(int u, int v) {
	u = findset(u);
	v = findset(v);
	if (u != v) {
		if (rand() % 2) { //lazy dsu
			par[u] = v;
		}
		else par[v] = u;
	}
}
 
map<ll, int> indo;
int delt[maxv];
 
 
ll plan_roller_coaster(vector<int> s, vector<int> t) {
	srand(23);
    int n = (int) s.size();
    set<int> og;
    for (int v : s)  og.insert(v);
   	for (int v : t) og.insert(v);
   	og.insert(1);
   	og.insert(inf);
   	for (int v : og) nums.push_back(v);
 
   	for (int i = 0; i < nums.size(); i++) {
   		indo[nums[i]] = i;
   		par[i] = i; //setting up the dsu for later
   	}
 
   	// cout << "here 1" << endl; 
 
   	for (int i = 0; i < s.size(); i++) {
   		adj[indo[s[i]]].push_back(indo[t[i]]);
   		// cout << s[i] << " to " << t[i] << " is: " << endl;
   		// cout << "   " << indo[s[i]] << " to " << indo[t[i]] << endl;
   	}
   	adj[indo[inf]].push_back(indo[1]);
   	// cout << "last guy is " << indo[inf] << " to " << indo[1] << endl;
 
   	ll ans = 0LL;
 
   	// cout << "here 2 " << endl;
 
 
   	for (int i = 0; i < nums.size(); i++) {
   		for (int v : adj[i]) {
   			if (v >= i) {
   				delt[i]++;
   				delt[v]--;
 
   			}
   			else {
		   		delt[v]--;
		   		delt[i]++;
		   	}
   		}
   		
   	}
 
   	// cout << "here 3" << endl;
 
   	int curval = 0;
   	for (int i = 0; i < nums.size()-1; i++) {
   		curval += delt[i];
   		// cout << i << " " << nums[i] << " : " << curval << endl;
   		// cout << "    " << delt[i]  << endl;
 
   		if (curval > 0) {
   			// cout << i << " is positive! " << endl;
   			ans += curval * (nums[i+1]-nums[i]);
   			adj[i+1].push_back(i);
   		}
   		else if (curval < 0) {
   			adj[i].push_back(i+1);
   		}
   	}
 
   	vector<pair<ll, int>> edges; 
   	//the first is the lenght, the second is the starting guy
   	for (int i = 0; i < nums.size()-1; i++) {
   		edges.push_back(mp(nums[i+1]-nums[i], i));
   	}
   	sort(edges.begin(), edges.end());
 
   	for (int i = 0; i < nums.size(); i++) {
   		for (int v : adj[i]) unionset(i, v);
   	}
 
   	for (int i = 0; i < edges.size(); i++) {
   		if (findset(edges[i].second) != findset(edges[i].second+1)) {
   			unionset(edges[i].second, edges[i].second+1);
   			ans += edges[i].first;
   		}
   	}
 
    return ans;
}

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < nums.size(); i++) {
                     ~~^~~~~~~~~~~~~
railroad.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++) {
                     ~~^~~~~~~~~~
railroad.cpp:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < nums.size(); i++) {
                     ~~^~~~~~~~~~~~~
railroad.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < nums.size()-1; i++) {
                     ~~^~~~~~~~~~~~~~~
railroad.cpp:101:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < nums.size()-1; i++) {
                     ~~^~~~~~~~~~~~~~~
railroad.cpp:106:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < nums.size(); i++) {
                     ~~^~~~~~~~~~~~~
railroad.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < edges.size(); i++) {
                     ~~^~~~~~~~~~~~~~
railroad.cpp:38:9: warning: unused variable 'n' [-Wunused-variable]
     int n = (int) s.size();
         ^

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1269 ms 84520 KB n = 199999
2 Correct 1261 ms 84520 KB n = 199991
3 Correct 1201 ms 84520 KB n = 199993
4 Correct 832 ms 84520 KB n = 152076
5 Correct 473 ms 84520 KB n = 93249
6 Correct 1035 ms 84520 KB n = 199910
7 Correct 1138 ms 84520 KB n = 199999
8 Correct 1026 ms 84520 KB n = 199997
9 Correct 1074 ms 84520 KB n = 171294
10 Correct 825 ms 84520 KB n = 140872
11 Correct 1120 ms 84520 KB n = 199886
12 Correct 1146 ms 84520 KB n = 199996
13 Correct 1093 ms 84520 KB n = 200000
14 Correct 1130 ms 84520 KB n = 199998
15 Correct 1090 ms 84520 KB n = 200000
16 Correct 1128 ms 84520 KB n = 199998
17 Correct 1113 ms 84520 KB n = 200000
18 Correct 1141 ms 84520 KB n = 190000
19 Correct 964 ms 84520 KB n = 177777
20 Correct 477 ms 84520 KB n = 100000
21 Correct 1186 ms 84520 KB n = 200000
22 Correct 1189 ms 84520 KB n = 200000
23 Correct 1264 ms 84520 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9724 KB n = 2
2 Correct 10 ms 9772 KB n = 2
3 Correct 10 ms 9784 KB n = 2
4 Correct 11 ms 9988 KB n = 2
5 Correct 10 ms 9988 KB n = 2
6 Correct 9 ms 9988 KB n = 2
7 Correct 10 ms 9988 KB n = 3
8 Correct 10 ms 9988 KB n = 3
9 Correct 9 ms 9992 KB n = 3
10 Correct 9 ms 10124 KB n = 8
11 Correct 9 ms 10124 KB n = 8
12 Correct 10 ms 10124 KB n = 8
13 Correct 11 ms 10124 KB n = 8
14 Correct 10 ms 10124 KB n = 8
15 Correct 14 ms 10124 KB n = 8
16 Correct 10 ms 10124 KB n = 8
17 Correct 10 ms 10124 KB n = 8
18 Correct 10 ms 10236 KB n = 8
19 Correct 10 ms 10236 KB n = 3
20 Correct 10 ms 10236 KB n = 7
21 Correct 10 ms 10236 KB n = 8
22 Correct 10 ms 10236 KB n = 8
23 Correct 10 ms 10236 KB n = 8
24 Correct 10 ms 10236 KB n = 8
25 Correct 10 ms 10236 KB n = 8
26 Correct 11 ms 10236 KB n = 8
27 Correct 10 ms 10236 KB n = 8
28 Correct 10 ms 10236 KB n = 8
29 Correct 10 ms 10236 KB n = 16
30 Correct 10 ms 10236 KB n = 16
31 Correct 10 ms 10236 KB n = 16
32 Correct 10 ms 10236 KB n = 16
33 Correct 10 ms 10236 KB n = 16
34 Correct 10 ms 10236 KB n = 16
35 Correct 10 ms 10236 KB n = 16
36 Correct 9 ms 10276 KB n = 15
37 Correct 12 ms 10276 KB n = 8
38 Correct 12 ms 10276 KB n = 16
39 Correct 10 ms 10276 KB n = 16
40 Correct 9 ms 10276 KB n = 9
41 Correct 10 ms 10276 KB n = 16
42 Correct 10 ms 10276 KB n = 16
43 Correct 10 ms 10276 KB n = 16
44 Correct 10 ms 10276 KB n = 9
45 Correct 10 ms 10276 KB n = 15
46 Correct 10 ms 10276 KB n = 16
47 Correct 10 ms 10276 KB n = 16
48 Correct 10 ms 10316 KB n = 16
49 Correct 1269 ms 84520 KB n = 199999
50 Correct 1261 ms 84520 KB n = 199991
51 Correct 1201 ms 84520 KB n = 199993
52 Correct 832 ms 84520 KB n = 152076
53 Correct 473 ms 84520 KB n = 93249
54 Correct 1035 ms 84520 KB n = 199910
55 Correct 1138 ms 84520 KB n = 199999
56 Correct 1026 ms 84520 KB n = 199997
57 Correct 1074 ms 84520 KB n = 171294
58 Correct 825 ms 84520 KB n = 140872
59 Correct 1120 ms 84520 KB n = 199886
60 Correct 1146 ms 84520 KB n = 199996
61 Correct 1093 ms 84520 KB n = 200000
62 Correct 1130 ms 84520 KB n = 199998
63 Correct 1090 ms 84520 KB n = 200000
64 Correct 1128 ms 84520 KB n = 199998
65 Correct 1113 ms 84520 KB n = 200000
66 Correct 1141 ms 84520 KB n = 190000
67 Correct 964 ms 84520 KB n = 177777
68 Correct 477 ms 84520 KB n = 100000
69 Correct 1186 ms 84520 KB n = 200000
70 Correct 1189 ms 84520 KB n = 200000
71 Correct 1264 ms 84520 KB n = 200000
72 Correct 1461 ms 88244 KB n = 200000
73 Correct 1324 ms 92260 KB n = 200000
74 Correct 1357 ms 96196 KB n = 200000
75 Correct 1205 ms 100092 KB n = 200000
76 Correct 1168 ms 103824 KB n = 200000
77 Correct 800 ms 103824 KB n = 200000
78 Correct 774 ms 103824 KB n = 200000
79 Correct 1238 ms 109964 KB n = 184307
80 Correct 428 ms 109964 KB n = 76040
81 Correct 1052 ms 109964 KB n = 199981
82 Correct 1145 ms 121472 KB n = 199994
83 Correct 972 ms 121472 KB n = 199996
84 Correct 1010 ms 127088 KB n = 199998
85 Correct 1060 ms 129184 KB n = 200000
86 Correct 1089 ms 134596 KB n = 199998
87 Correct 1083 ms 138640 KB n = 200000
88 Correct 1258 ms 142620 KB n = 200000
89 Correct 1081 ms 146448 KB n = 200000
90 Correct 1137 ms 150292 KB n = 200000
91 Correct 1120 ms 154128 KB n = 200000
92 Correct 1171 ms 158008 KB n = 200000