oj.uz

Submission #637138

# Submission time Handle Problem Language Result Execution time Memory
637138 2022-08-31T16:10:14 Z ggoh Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 342 ms 45052 KB 
//after read editorial :cry:
#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;

int v[400004],deg[400004];
vector<int>G[400004];
int col,par[400004];
int find(int p)
{
  if(p==par[p])return p;
  else return par[p]=find(par[p]);
}
void uni(int p,int q)
{
  p=find(p);q=find(q);
  if(p!=q)par[p]=q;
}
void dfs(int p)
{
  v[p]=col;
  for(auto &k:G[p])if(!v[k])dfs(k);
}
lint plan_roller_coaster(vector<int> s, vector<int> t) {

    int n = sz(s);
    lint ans=0;
    vector<int>X;
    for(int i=0;i<n;i++)X.push_back(s[i]);
    for(int i=0;i<n;i++)X.push_back(t[i]);
    sort(X.begin(),X.end());
    X.erase(unique(X.begin(),X.end()),X.end());
    int m=sz(X);
    for(int i=0;i<n;i++)
    {
      int p,q;
      p=lower_bound(X.begin(),X.end(),s[i])-X.begin();
      q=lower_bound(X.begin(),X.end(),t[i])-X.begin();
      deg[p]++;
      deg[q]--;
      G[p].push_back(q);
    }
    deg[0]--;
    deg[m-1]++;
    int cha=0;
    int ch=0;
    for(int i=0;i<m-1;i++)
    {
      deg[i]+=cha;
      cha=deg[i];
      if(deg[i]<0)
      {
        G[i].push_back(i+1);
      }
      else if(deg[i]>0)
      {
        G[i+1].push_back(i);
        ans+=1ll*deg[i]*(X[i+1]-X[i]);
      }
    }
    col=0;
    for(int i=0;i<m;i++)
    {
      if(!v[i])
      {
        col++;
        dfs(i);
      }
    }
    for(int i=1;i<=col;i++)par[i]=i;
    priority_queue<pii>P;
    for(int i=0;i<m-1;i++)P.push({-(X[i+1]-X[i]),i});
    while(!P.empty())
    {
      pii p=P.top();P.pop();
      if(find(v[p.second])!=find(v[p.second+1]))
      {
        uni(v[p.second],v[p.second+1]);
        ans+=-p.first;
      }
    }
    return ans;
}

Compilation message

railroad.cpp: In function 'lint plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:49:9: warning: unused variable 'ch' [-Wunused-variable]
   49 |     int ch=0;
      |         ^~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 41172 KB n = 199999
2 Correct 342 ms 37244 KB n = 199991
3 Correct 324 ms 41032 KB n = 199993
4 Correct 235 ms 31424 KB n = 152076
5 Correct 142 ms 22656 KB n = 93249
6 Correct 271 ms 33196 KB n = 199910
7 Correct 291 ms 37196 KB n = 199999
8 Correct 290 ms 34272 KB n = 199997
9 Correct 284 ms 33916 KB n = 171294
10 Correct 229 ms 30200 KB n = 140872
11 Correct 255 ms 33488 KB n = 199886
12 Correct 322 ms 37252 KB n = 199996
13 Correct 252 ms 35032 KB n = 200000
14 Correct 305 ms 38920 KB n = 199998
15 Correct 278 ms 37436 KB n = 200000
16 Correct 335 ms 37988 KB n = 199998
17 Correct 280 ms 37692 KB n = 200000
18 Correct 288 ms 36732 KB n = 190000
19 Correct 263 ms 38236 KB n = 177777
20 Correct 140 ms 23420 KB n = 100000
21 Correct 329 ms 37260 KB n = 200000
22 Correct 299 ms 34768 KB n = 200000
23 Correct 308 ms 41224 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9684 KB n = 2
2 Correct 5 ms 9684 KB n = 2
3 Correct 5 ms 9684 KB n = 2
4 Correct 5 ms 9684 KB n = 2
5 Correct 5 ms 9684 KB n = 2
6 Correct 5 ms 9684 KB n = 2
7 Correct 6 ms 9684 KB n = 3
8 Correct 5 ms 9684 KB n = 3
9 Correct 6 ms 9684 KB n = 3
10 Correct 5 ms 9684 KB n = 8
11 Correct 5 ms 9684 KB n = 8
12 Correct 5 ms 9684 KB n = 8
13 Correct 5 ms 9716 KB n = 8
14 Correct 5 ms 9684 KB n = 8
15 Correct 5 ms 9684 KB n = 8
16 Correct 5 ms 9660 KB n = 8
17 Correct 5 ms 9684 KB n = 8
18 Correct 6 ms 9600 KB n = 8
19 Correct 7 ms 9660 KB n = 3
20 Correct 7 ms 9684 KB n = 7
21 Correct 7 ms 9600 KB n = 8
22 Correct 6 ms 9612 KB n = 8
23 Correct 5 ms 9684 KB n = 8
24 Correct 5 ms 9684 KB n = 8
25 Correct 5 ms 9668 KB n = 8
26 Correct 5 ms 9684 KB n = 8
27 Correct 6 ms 9684 KB n = 8
28 Correct 5 ms 9684 KB n = 8
29 Correct 5 ms 9684 KB n = 16
30 Correct 6 ms 9684 KB n = 16
31 Correct 5 ms 9684 KB n = 16
32 Correct 5 ms 9684 KB n = 16
33 Correct 6 ms 9684 KB n = 16
34 Correct 5 ms 9684 KB n = 16
35 Correct 5 ms 9684 KB n = 16
36 Correct 5 ms 9684 KB n = 15
37 Correct 5 ms 9684 KB n = 8
38 Correct 6 ms 9684 KB n = 16
39 Correct 5 ms 9684 KB n = 16
40 Correct 6 ms 9668 KB n = 9
41 Correct 5 ms 9684 KB n = 16
42 Correct 6 ms 9684 KB n = 16
43 Correct 5 ms 9684 KB n = 16
44 Correct 6 ms 9684 KB n = 9
45 Correct 5 ms 9712 KB n = 15
46 Correct 6 ms 9684 KB n = 16
47 Correct 8 ms 9712 KB n = 16
48 Correct 6 ms 9684 KB n = 16
49 Correct 300 ms 41172 KB n = 199999
50 Correct 342 ms 37244 KB n = 199991
51 Correct 324 ms 41032 KB n = 199993
52 Correct 235 ms 31424 KB n = 152076
53 Correct 142 ms 22656 KB n = 93249
54 Correct 271 ms 33196 KB n = 199910
55 Correct 291 ms 37196 KB n = 199999
56 Correct 290 ms 34272 KB n = 199997
57 Correct 284 ms 33916 KB n = 171294
58 Correct 229 ms 30200 KB n = 140872
59 Correct 255 ms 33488 KB n = 199886
60 Correct 322 ms 37252 KB n = 199996
61 Correct 252 ms 35032 KB n = 200000
62 Correct 305 ms 38920 KB n = 199998
63 Correct 278 ms 37436 KB n = 200000
64 Correct 335 ms 37988 KB n = 199998
65 Correct 280 ms 37692 KB n = 200000
66 Correct 288 ms 36732 KB n = 190000
67 Correct 263 ms 38236 KB n = 177777
68 Correct 140 ms 23420 KB n = 100000
69 Correct 329 ms 37260 KB n = 200000
70 Correct 299 ms 34768 KB n = 200000
71 Correct 308 ms 41224 KB n = 200000
72 Correct 302 ms 42784 KB n = 200000
73 Correct 338 ms 38888 KB n = 200000
74 Correct 311 ms 41920 KB n = 200000
75 Correct 279 ms 42860 KB n = 200000
76 Correct 301 ms 42816 KB n = 200000
77 Correct 236 ms 30332 KB n = 200000
78 Correct 202 ms 29860 KB n = 200000
79 Correct 301 ms 37988 KB n = 184307
80 Correct 111 ms 22192 KB n = 76040
81 Correct 261 ms 36236 KB n = 199981
82 Correct 324 ms 40516 KB n = 199994
83 Correct 264 ms 37880 KB n = 199996
84 Correct 289 ms 41844 KB n = 199998
85 Correct 288 ms 40560 KB n = 200000
86 Correct 292 ms 41276 KB n = 199998
87 Correct 298 ms 41704 KB n = 200000
88 Correct 302 ms 41792 KB n = 200000
89 Correct 287 ms 45052 KB n = 200000
90 Correct 310 ms 41124 KB n = 200000
91 Correct 278 ms 38636 KB n = 200000
92 Correct 315 ms 45040 KB n = 200000