# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
906806 | 2024-01-15T02:52:21 Z | mathnetic | Roller Coaster Railroad (IOI16_railroad) | C++17 | 505 ms | 33172 KB |
#include <cassert> #include <cstdio> #include <algorithm> #include <unordered_map> #include "railroad.h" using namespace std; typedef pair<int,int> ii; typedef long long ll; unordered_map<int, int> uf; int fnd(int x){ if(uf[x]==0) uf[x]=x; if(x==uf[x]) return x; else return uf[x]=fnd(uf[x]); } void un(int x, int y){ uf[fnd(x)]=fnd(y); } bool cmp(ii a, ii b){ return (a.second-a.first)<(b.second-b.first); } ll plan_roller_coaster(vector<int> s, vector<int> t){ ll sol=0; s.push_back(1e9); t.push_back(1); int n = (int) s.size(); vector<ii> e, ed; for(int i=0;i<n;++i){ un(s[i], t[i]); e.emplace_back(s[i], 1); e.emplace_back(t[i], -1); } sort(e.begin(), e.end()); int b=0; for(int i=0, j=0;i<e.size();i=j){ for(;j<e.size() && e[j].first==e[i].first;++j){ b+=e[j].second; } if(j<e.size()){ if(b>0){ sol+=(ll)b*(e[j].first-e[i].first); } if(b==0){ ed.emplace_back(e[i].first, e[j].first); }else{ un(e[j].first, e[i].first); } } } sort(ed.begin(), ed.end(), cmp); for(auto i:ed){ if(fnd(i.first)!=fnd(i.second)){ sol+=i.second-i.first; un(i.first, i.second); } } return sol; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | n = 2 |
2 | Correct | 0 ms | 348 KB | n = 2 |
3 | Correct | 0 ms | 348 KB | n = 2 |
4 | Correct | 0 ms | 348 KB | n = 2 |
5 | Correct | 0 ms | 348 KB | n = 2 |
6 | Correct | 0 ms | 348 KB | n = 2 |
7 | Correct | 0 ms | 348 KB | n = 3 |
8 | Correct | 0 ms | 348 KB | n = 3 |
9 | Correct | 0 ms | 348 KB | n = 3 |
10 | Correct | 1 ms | 348 KB | n = 8 |
11 | Correct | 1 ms | 348 KB | n = 8 |
12 | Correct | 1 ms | 348 KB | n = 8 |
13 | Correct | 0 ms | 348 KB | n = 8 |
14 | Correct | 0 ms | 348 KB | n = 8 |
15 | Correct | 0 ms | 420 KB | n = 8 |
16 | Correct | 1 ms | 348 KB | n = 8 |
17 | Correct | 0 ms | 348 KB | n = 8 |
18 | Correct | 0 ms | 348 KB | n = 8 |
19 | Correct | 1 ms | 348 KB | n = 3 |
20 | Correct | 0 ms | 348 KB | n = 7 |
21 | Correct | 1 ms | 348 KB | n = 8 |
22 | Correct | 1 ms | 348 KB | n = 8 |
23 | Correct | 0 ms | 348 KB | n = 8 |
24 | Correct | 0 ms | 348 KB | n = 8 |
25 | Correct | 0 ms | 348 KB | n = 8 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | n = 2 |
2 | Correct | 0 ms | 348 KB | n = 2 |
3 | Correct | 0 ms | 348 KB | n = 2 |
4 | Correct | 0 ms | 348 KB | n = 2 |
5 | Correct | 0 ms | 348 KB | n = 2 |
6 | Correct | 0 ms | 348 KB | n = 2 |
7 | Correct | 0 ms | 348 KB | n = 3 |
8 | Correct | 0 ms | 348 KB | n = 3 |
9 | Correct | 0 ms | 348 KB | n = 3 |
10 | Correct | 1 ms | 348 KB | n = 8 |
11 | Correct | 1 ms | 348 KB | n = 8 |
12 | Correct | 1 ms | 348 KB | n = 8 |
13 | Correct | 0 ms | 348 KB | n = 8 |
14 | Correct | 0 ms | 348 KB | n = 8 |
15 | Correct | 0 ms | 420 KB | n = 8 |
16 | Correct | 1 ms | 348 KB | n = 8 |
17 | Correct | 0 ms | 348 KB | n = 8 |
18 | Correct | 0 ms | 348 KB | n = 8 |
19 | Correct | 1 ms | 348 KB | n = 3 |
20 | Correct | 0 ms | 348 KB | n = 7 |
21 | Correct | 1 ms | 348 KB | n = 8 |
22 | Correct | 1 ms | 348 KB | n = 8 |
23 | Correct | 0 ms | 348 KB | n = 8 |
24 | Correct | 0 ms | 348 KB | n = 8 |
25 | Correct | 0 ms | 348 KB | n = 8 |
26 | Correct | 1 ms | 348 KB | n = 8 |
27 | Correct | 1 ms | 348 KB | n = 8 |
28 | Correct | 0 ms | 348 KB | n = 8 |
29 | Correct | 1 ms | 348 KB | n = 16 |
30 | Correct | 1 ms | 348 KB | n = 16 |
31 | Correct | 0 ms | 348 KB | n = 16 |
32 | Correct | 0 ms | 348 KB | n = 16 |
33 | Correct | 1 ms | 348 KB | n = 16 |
34 | Correct | 0 ms | 348 KB | n = 16 |
35 | Correct | 0 ms | 348 KB | n = 16 |
36 | Correct | 0 ms | 348 KB | n = 15 |
37 | Correct | 1 ms | 348 KB | n = 8 |
38 | Correct | 0 ms | 348 KB | n = 16 |
39 | Correct | 0 ms | 348 KB | n = 16 |
40 | Correct | 1 ms | 348 KB | n = 9 |
41 | Correct | 0 ms | 360 KB | n = 16 |
42 | Correct | 1 ms | 360 KB | n = 16 |
43 | Correct | 1 ms | 360 KB | n = 16 |
44 | Correct | 1 ms | 436 KB | n = 9 |
45 | Correct | 1 ms | 348 KB | n = 15 |
46 | Correct | 0 ms | 348 KB | n = 16 |
47 | Correct | 1 ms | 348 KB | n = 16 |
48 | Correct | 1 ms | 348 KB | n = 16 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 394 ms | 30684 KB | n = 199999 |
2 | Correct | 358 ms | 30184 KB | n = 199991 |
3 | Correct | 379 ms | 29512 KB | n = 199993 |
4 | Correct | 156 ms | 21464 KB | n = 152076 |
5 | Correct | 88 ms | 14456 KB | n = 93249 |
6 | Correct | 238 ms | 23008 KB | n = 199910 |
7 | Correct | 261 ms | 28880 KB | n = 199999 |
8 | Correct | 288 ms | 23392 KB | n = 199997 |
9 | Correct | 236 ms | 22980 KB | n = 171294 |
10 | Correct | 270 ms | 20780 KB | n = 140872 |
11 | Correct | 189 ms | 22476 KB | n = 199886 |
12 | Correct | 301 ms | 28900 KB | n = 199996 |
13 | Correct | 237 ms | 24168 KB | n = 200000 |
14 | Correct | 411 ms | 32284 KB | n = 199998 |
15 | Correct | 464 ms | 32760 KB | n = 200000 |
16 | Correct | 449 ms | 33172 KB | n = 199998 |
17 | Correct | 401 ms | 30504 KB | n = 200000 |
18 | Correct | 291 ms | 29492 KB | n = 190000 |
19 | Correct | 266 ms | 29720 KB | n = 177777 |
20 | Correct | 95 ms | 14752 KB | n = 100000 |
21 | Correct | 321 ms | 29460 KB | n = 200000 |
22 | Correct | 497 ms | 32296 KB | n = 200000 |
23 | Correct | 464 ms | 32356 KB | n = 200000 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | n = 2 |
2 | Correct | 0 ms | 348 KB | n = 2 |
3 | Correct | 0 ms | 348 KB | n = 2 |
4 | Correct | 0 ms | 348 KB | n = 2 |
5 | Correct | 0 ms | 348 KB | n = 2 |
6 | Correct | 0 ms | 348 KB | n = 2 |
7 | Correct | 0 ms | 348 KB | n = 3 |
8 | Correct | 0 ms | 348 KB | n = 3 |
9 | Correct | 0 ms | 348 KB | n = 3 |
10 | Correct | 1 ms | 348 KB | n = 8 |
11 | Correct | 1 ms | 348 KB | n = 8 |
12 | Correct | 1 ms | 348 KB | n = 8 |
13 | Correct | 0 ms | 348 KB | n = 8 |
14 | Correct | 0 ms | 348 KB | n = 8 |
15 | Correct | 0 ms | 420 KB | n = 8 |
16 | Correct | 1 ms | 348 KB | n = 8 |
17 | Correct | 0 ms | 348 KB | n = 8 |
18 | Correct | 0 ms | 348 KB | n = 8 |
19 | Correct | 1 ms | 348 KB | n = 3 |
20 | Correct | 0 ms | 348 KB | n = 7 |
21 | Correct | 1 ms | 348 KB | n = 8 |
22 | Correct | 1 ms | 348 KB | n = 8 |
23 | Correct | 0 ms | 348 KB | n = 8 |
24 | Correct | 0 ms | 348 KB | n = 8 |
25 | Correct | 0 ms | 348 KB | n = 8 |
26 | Correct | 1 ms | 348 KB | n = 8 |
27 | Correct | 1 ms | 348 KB | n = 8 |
28 | Correct | 0 ms | 348 KB | n = 8 |
29 | Correct | 1 ms | 348 KB | n = 16 |
30 | Correct | 1 ms | 348 KB | n = 16 |
31 | Correct | 0 ms | 348 KB | n = 16 |
32 | Correct | 0 ms | 348 KB | n = 16 |
33 | Correct | 1 ms | 348 KB | n = 16 |
34 | Correct | 0 ms | 348 KB | n = 16 |
35 | Correct | 0 ms | 348 KB | n = 16 |
36 | Correct | 0 ms | 348 KB | n = 15 |
37 | Correct | 1 ms | 348 KB | n = 8 |
38 | Correct | 0 ms | 348 KB | n = 16 |
39 | Correct | 0 ms | 348 KB | n = 16 |
40 | Correct | 1 ms | 348 KB | n = 9 |
41 | Correct | 0 ms | 360 KB | n = 16 |
42 | Correct | 1 ms | 360 KB | n = 16 |
43 | Correct | 1 ms | 360 KB | n = 16 |
44 | Correct | 1 ms | 436 KB | n = 9 |
45 | Correct | 1 ms | 348 KB | n = 15 |
46 | Correct | 0 ms | 348 KB | n = 16 |
47 | Correct | 1 ms | 348 KB | n = 16 |
48 | Correct | 1 ms | 348 KB | n = 16 |
49 | Correct | 394 ms | 30684 KB | n = 199999 |
50 | Correct | 358 ms | 30184 KB | n = 199991 |
51 | Correct | 379 ms | 29512 KB | n = 199993 |
52 | Correct | 156 ms | 21464 KB | n = 152076 |
53 | Correct | 88 ms | 14456 KB | n = 93249 |
54 | Correct | 238 ms | 23008 KB | n = 199910 |
55 | Correct | 261 ms | 28880 KB | n = 199999 |
56 | Correct | 288 ms | 23392 KB | n = 199997 |
57 | Correct | 236 ms | 22980 KB | n = 171294 |
58 | Correct | 270 ms | 20780 KB | n = 140872 |
59 | Correct | 189 ms | 22476 KB | n = 199886 |
60 | Correct | 301 ms | 28900 KB | n = 199996 |
61 | Correct | 237 ms | 24168 KB | n = 200000 |
62 | Correct | 411 ms | 32284 KB | n = 199998 |
63 | Correct | 464 ms | 32760 KB | n = 200000 |
64 | Correct | 449 ms | 33172 KB | n = 199998 |
65 | Correct | 401 ms | 30504 KB | n = 200000 |
66 | Correct | 291 ms | 29492 KB | n = 190000 |
67 | Correct | 266 ms | 29720 KB | n = 177777 |
68 | Correct | 95 ms | 14752 KB | n = 100000 |
69 | Correct | 321 ms | 29460 KB | n = 200000 |
70 | Correct | 497 ms | 32296 KB | n = 200000 |
71 | Correct | 464 ms | 32356 KB | n = 200000 |
72 | Correct | 358 ms | 29296 KB | n = 200000 |
73 | Correct | 386 ms | 29344 KB | n = 200000 |
74 | Correct | 452 ms | 29404 KB | n = 200000 |
75 | Correct | 433 ms | 29412 KB | n = 200000 |
76 | Correct | 384 ms | 30432 KB | n = 200000 |
77 | Correct | 121 ms | 19500 KB | n = 200000 |
78 | Correct | 163 ms | 23524 KB | n = 200000 |
79 | Correct | 288 ms | 30048 KB | n = 184307 |
80 | Correct | 81 ms | 10512 KB | n = 76040 |
81 | Correct | 176 ms | 22848 KB | n = 199981 |
82 | Correct | 350 ms | 28816 KB | n = 199994 |
83 | Correct | 196 ms | 24124 KB | n = 199996 |
84 | Correct | 420 ms | 32352 KB | n = 199998 |
85 | Correct | 379 ms | 31780 KB | n = 200000 |
86 | Correct | 480 ms | 32876 KB | n = 199998 |
87 | Correct | 388 ms | 30280 KB | n = 200000 |
88 | Correct | 382 ms | 29412 KB | n = 200000 |
89 | Correct | 338 ms | 29412 KB | n = 200000 |
90 | Correct | 328 ms | 29924 KB | n = 200000 |
91 | Correct | 505 ms | 32436 KB | n = 200000 |
92 | Correct | 481 ms | 32804 KB | n = 200000 |