oj.uz

Submission #278830

# Submission time Handle Problem Language Result Execution time Memory
278830 2020-08-22T00:24:08 Z mjkocijan Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 1476 ms 142900 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> ip;
#define MAXN 800200
#define INF 1001001001001001001LL

//ll dp[1 << MAXN][LOG], reza = INF;

unordered_map<int, int> mp;

vector<int> g[MAXN], in[MAXN];

set<int> s2;
vector<int> s, z;
int ss[MAXN];

ll reza = 0;

int zip(int x)
{
	if (mp.count(x)) return mp[x];
	
	return mp[x] = mp.size();
}

int bio[MAXN];
int rt[MAXN], sz[MAXN];
set<int> co;

void dfs(int cv, int kor)
{
	if (bio[cv]) return;
	bio[cv] = 1;
	rt[cv] = kor;
	co.insert(kor);
	
	for (int i: g[cv])
		dfs(i, kor);
	for (int i: in[cv])
		dfs(i, kor);
}

int fn(int cv)
{
	if (cv == rt[cv]) return cv;
	
	return rt[cv] = fn(rt[cv]);
}

void merg(int x, int y)
{
	x = fn(x);
	y = fn(y);
	
	if (x == y) return;
	
	if (sz[x] > sz[y]) swap(x, y);
	
	rt[x] = y;
	co.erase(x);
	if (sz[x] == sz[y]) sz[y]++;
}

vector<ii> es;

long long plan_roller_coaster(std::vector<int> _s, std::vector<int> t) {
  int n = (int) _s.size();
  _s.pb(1001001001); t.pb(1); n++;
  
  for (int i = 0; i < n; i++) {
  	int _sz = zip(_s[i]), tz = zip(t[i]);
  	g[_sz].pb(tz);
  	in[tz].pb(_sz);
  	s2.insert(_s[i]);
  	s2.insert(t[i]);
  	ss[_sz]++;
  	ss[tz]--;
  }
  
  for (int i: s2) { s.pb(i); z.pb(zip(i)); }
  
  int suma = 0;
  for (int j = 0; j < s.size() - 1; j++) {
  	int i = s[j];
  	int ni = s[j + 1];
  	suma += ss[z[j]];
  	if (suma > 0) {
  		reza += ll(suma) * ll(ni - i);
  		i = z[j];
  		ni = z[j + 1];
  		g[ni].pb(i);
  		in[i].pb(ni);
  		//cout<<i<<' '<<ni<<'='<<suma<<endl;
  	}
  	if (suma < 0) {
  		i = z[j];
  		ni = z[j + 1];
  		g[ni].pb(i);
  		in[i].pb(ni);
  	}
  }
  
  for (int j = 0; j < s.size(); j++) {
  	int i = s[j];
  	dfs(z[j], z[j]);
  	//cout << i<<' '<<rt[zip(i)]<<endl;
  }
  
  for (int j = 0; j < s.size() - 1; j++) {
  	int i = s[j];
  	int ni = s[j + 1];
  	es.pb({ll(ni) - i, j});//cout<<ll(ni)-i<<' '<<i<<'.'<<ni<<' '<<zip(i)<<'.'<<zip(ni)<<endl;
  }
  
  sort(es.begin(), es.end());
  
  int kk = 0;
  
  while (co.size() > 1) {
  	ii cu = es[kk];//cout<<cu.X<<' '<<cu.Y.X<<'.'<<cu.Y.Y<<endl;
  	kk++;//cout<<cu.X<<' '<<cu.Y.X<<'.'<<cu.Y.Y<<' '<<co.size()<<','<<reza<<endl;
  	int pre = co.size();
  	merg(z[cu.Y], z[cu.Y + 1]);
  	int nov = co.size();
  	if (nov < pre) reza += cu.X;
  }
  
  return reza;
}

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int j = 0; j < s.size() - 1; j++) {
      |                   ~~^~~~~~~~~~~~~~
railroad.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (int j = 0; j < s.size(); j++) {
      |                   ~~^~~~~~~~~~
railroad.cpp:110:8: warning: unused variable 'i' [-Wunused-variable]
  110 |    int i = s[j];
      |        ^
railroad.cpp:115:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for (int j = 0; j < s.size() - 1; j++) {
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37888 KB n = 2
2 Correct 26 ms 37888 KB n = 2
3 Correct 26 ms 37888 KB n = 2
4 Correct 26 ms 37888 KB n = 2
5 Correct 26 ms 38016 KB n = 2
6 Correct 25 ms 37888 KB n = 2
7 Correct 26 ms 37888 KB n = 3
8 Correct 26 ms 37888 KB n = 3
9 Correct 26 ms 37880 KB n = 3
10 Correct 26 ms 37888 KB n = 8
11 Correct 26 ms 37888 KB n = 8
12 Correct 28 ms 37888 KB n = 8
13 Correct 26 ms 37888 KB n = 8
14 Correct 27 ms 38016 KB n = 8
15 Correct 28 ms 37888 KB n = 8
16 Correct 26 ms 37888 KB n = 8
17 Correct 29 ms 37888 KB n = 8
18 Correct 27 ms 37888 KB n = 8
19 Correct 28 ms 37888 KB n = 3
20 Correct 25 ms 37888 KB n = 7
21 Correct 28 ms 37880 KB n = 8
22 Correct 27 ms 37924 KB n = 8
23 Correct 25 ms 37888 KB n = 8
24 Correct 29 ms 37888 KB n = 8
25 Correct 28 ms 37880 KB n = 8

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1386 ms 134808 KB n = 199999
2 Correct 1402 ms 134308 KB n = 199991
3 Correct 1454 ms 138504 KB n = 199993
4 Correct 1061 ms 117536 KB n = 152076
5 Correct 577 ms 85012 KB n = 93249
6 Correct 1110 ms 115792 KB n = 199910
7 Correct 1257 ms 129024 KB n = 199999
8 Correct 1062 ms 117876 KB n = 199997
9 Correct 1174 ms 121724 KB n = 171294
10 Correct 937 ms 113524 KB n = 140872
11 Correct 1090 ms 117796 KB n = 199886
12 Correct 1172 ms 129700 KB n = 199996
13 Correct 1039 ms 120924 KB n = 200000
14 Correct 1052 ms 130980 KB n = 199998
15 Correct 1036 ms 128912 KB n = 200000
16 Correct 1108 ms 131348 KB n = 199998
17 Correct 1306 ms 142756 KB n = 200000
18 Correct 1248 ms 133748 KB n = 190000
19 Correct 1089 ms 133076 KB n = 177777
20 Correct 553 ms 85792 KB n = 100000
21 Correct 1254 ms 134436 KB n = 200000
22 Correct 1299 ms 117512 KB n = 200000
23 Correct 1236 ms 130468 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37888 KB n = 2
2 Correct 26 ms 37888 KB n = 2
3 Correct 26 ms 37888 KB n = 2
4 Correct 26 ms 37888 KB n = 2
5 Correct 26 ms 38016 KB n = 2
6 Correct 25 ms 37888 KB n = 2
7 Correct 26 ms 37888 KB n = 3
8 Correct 26 ms 37888 KB n = 3
9 Correct 26 ms 37880 KB n = 3
10 Correct 26 ms 37888 KB n = 8
11 Correct 26 ms 37888 KB n = 8
12 Correct 28 ms 37888 KB n = 8
13 Correct 26 ms 37888 KB n = 8
14 Correct 27 ms 38016 KB n = 8
15 Correct 28 ms 37888 KB n = 8
16 Correct 26 ms 37888 KB n = 8
17 Correct 29 ms 37888 KB n = 8
18 Correct 27 ms 37888 KB n = 8
19 Correct 28 ms 37888 KB n = 3
20 Correct 25 ms 37888 KB n = 7
21 Correct 28 ms 37880 KB n = 8
22 Correct 27 ms 37924 KB n = 8
23 Correct 25 ms 37888 KB n = 8
24 Correct 29 ms 37888 KB n = 8
25 Correct 28 ms 37880 KB n = 8
26 Correct 26 ms 37888 KB n = 8
27 Correct 26 ms 37888 KB n = 8
28 Correct 26 ms 37888 KB n = 8
29 Correct 26 ms 37888 KB n = 16
30 Correct 26 ms 37880 KB n = 16
31 Correct 26 ms 37888 KB n = 16
32 Correct 26 ms 37880 KB n = 16
33 Correct 26 ms 37988 KB n = 16
34 Correct 26 ms 37888 KB n = 16
35 Correct 25 ms 37880 KB n = 16
36 Correct 26 ms 37888 KB n = 15
37 Correct 25 ms 37888 KB n = 8
38 Correct 26 ms 37888 KB n = 16
39 Correct 26 ms 37880 KB n = 16
40 Correct 26 ms 37888 KB n = 9
41 Correct 26 ms 38016 KB n = 16
42 Correct 27 ms 37888 KB n = 16
43 Correct 26 ms 37888 KB n = 16
44 Correct 27 ms 37888 KB n = 9
45 Correct 28 ms 38008 KB n = 15
46 Correct 26 ms 37888 KB n = 16
47 Correct 26 ms 37888 KB n = 16
48 Correct 25 ms 37888 KB n = 16
49 Correct 1386 ms 134808 KB n = 199999
50 Correct 1402 ms 134308 KB n = 199991
51 Correct 1454 ms 138504 KB n = 199993
52 Correct 1061 ms 117536 KB n = 152076
53 Correct 577 ms 85012 KB n = 93249
54 Correct 1110 ms 115792 KB n = 199910
55 Correct 1257 ms 129024 KB n = 199999
56 Correct 1062 ms 117876 KB n = 199997
57 Correct 1174 ms 121724 KB n = 171294
58 Correct 937 ms 113524 KB n = 140872
59 Correct 1090 ms 117796 KB n = 199886
60 Correct 1172 ms 129700 KB n = 199996
61 Correct 1039 ms 120924 KB n = 200000
62 Correct 1052 ms 130980 KB n = 199998
63 Correct 1036 ms 128912 KB n = 200000
64 Correct 1108 ms 131348 KB n = 199998
65 Correct 1306 ms 142756 KB n = 200000
66 Correct 1248 ms 133748 KB n = 190000
67 Correct 1089 ms 133076 KB n = 177777
68 Correct 553 ms 85792 KB n = 100000
69 Correct 1254 ms 134436 KB n = 200000
70 Correct 1299 ms 117512 KB n = 200000
71 Correct 1236 ms 130468 KB n = 200000
72 Correct 1476 ms 138636 KB n = 200000
73 Correct 1422 ms 138148 KB n = 200000
74 Correct 1370 ms 138456 KB n = 200000
75 Correct 1352 ms 142884 KB n = 200000
76 Correct 1251 ms 142884 KB n = 200000
77 Correct 724 ms 93948 KB n = 200000
78 Correct 871 ms 93692 KB n = 200000
79 Correct 1278 ms 126372 KB n = 184307
80 Correct 447 ms 77528 KB n = 76040
81 Correct 1072 ms 117668 KB n = 199981
82 Correct 1285 ms 129756 KB n = 199994
83 Correct 1091 ms 120868 KB n = 199996
84 Correct 1069 ms 130980 KB n = 199998
85 Correct 1030 ms 128932 KB n = 200000
86 Correct 1096 ms 131492 KB n = 199998
87 Correct 1229 ms 142900 KB n = 200000
88 Correct 1241 ms 138020 KB n = 200000
89 Correct 1265 ms 142772 KB n = 200000
90 Correct 1324 ms 134448 KB n = 200000
91 Correct 1415 ms 117464 KB n = 200000
92 Correct 1259 ms 130168 KB n = 200000