oj.uz

답안 #139335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
139335 2019-07-31T14:58:02 Z KLPP Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 350 ms 33880 KB 
#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
class DSU{
  int parent[1000000];
  int size[1000000];
public:
  void init(int n){
    rep(i,0,n){
      parent[i]=i;
      size[i]=1;
    }
  }
  int root(int node){
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
  }
  bool merge(int a, int b){
    a=root(a);
    b=root(b);
    if(a==b)return false;
    if(size[b]>size[a])swap(a,b);
    parent[b]=a;
    size[a]+=size[b];
    return true;
  }
};
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  s.push_back(1000000001);
  t.push_back(1);
  int n = (int) s.size();
  vector<lld >v;
  rep(i,0,n){
    v.push_back(s[i]);
    v.push_back(t[i]);
  }
  sort(v.begin(),v.end());
  vector<lld> comp;
  rep(i,0,v.size()){
    if(comp.size()==0 || v[i]!=comp[comp.size()-1]){
      comp.push_back(v[i]);
    }
  }
  /*rep(i,0,comp.size())cout<<comp[i]<<" ";
  cout<<endl;*/
  lld edges[n][2];
  lld sections[comp.size()];
  rep(i,0,comp.size())sections[i]=0;
  rep(i,0,n){
    int lo,hi;
    lo=-1;hi=comp.size();
    while(hi-lo>1){
      int mid=(hi+lo)/2;
      if(comp[mid]<=s[i])lo=mid;
      else hi=mid;
    }
    edges[i][0]=lo;
    lo=-1;hi=comp.size();
    while(hi-lo>1){
      int mid=(hi+lo)/2;
      if(comp[mid]<=t[i])lo=mid;
      else hi=mid;
    }
    edges[i][1]=lo;
    rep(j,0,2){
      if(edges[i][j]>0){
	sections[edges[i][j]-1]+=1-2*j;
      }
    }
    //cout<<edges[i][0]<<" "<<edges[i][1]<<endl;
  }
  for(int i=comp.size()-1;i>0;i--){
    sections[i-1]+=sections[i];
  }
  vector<pii> edgelist;
  lld ans=0;
  DSU *D=new DSU();
  D->init(comp.size());
  rep(i,0,comp.size()-1){
    if(sections[i]==0){
      edgelist.push_back(pii(comp[i+1]-comp[i],i));
    }else D->merge(i,i+1);
    
    if(sections[i]<0){
      ans-=(comp[i+1]-comp[i])*sections[i];
    }
  }
  rep(i,0,n){
    D->merge(edges[i][0],edges[i][1]);
  }
  //cout<<ans<<endl;
  sort(edgelist.begin(),edgelist.end());
  rep(i,0,edgelist.size()){
    
    if(D->merge(edgelist[i].second,edgelist[i].second+1)){
      ans+=edgelist[i].first;
    }
  }
  return ans;
}

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
railroad.cpp:44:7:
   rep(i,0,v.size()){
       ~~~~~~~~~~~~               
railroad.cpp:44:3: note: in expansion of macro 'rep'
   rep(i,0,v.size()){
   ^~~
railroad.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
railroad.cpp:53:7:
   rep(i,0,comp.size())sections[i]=0;
       ~~~~~~~~~~~~~~~            
railroad.cpp:53:3: note: in expansion of macro 'rep'
   rep(i,0,comp.size())sections[i]=0;
   ^~~
railroad.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
railroad.cpp:84:7:
   rep(i,0,comp.size()-1){
       ~~~~~~~~~~~~~~~~~          
railroad.cpp:84:3: note: in expansion of macro 'rep'
   rep(i,0,comp.size()-1){
   ^~~
railroad.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
railroad.cpp:98:7:
   rep(i,0,edgelist.size()){
       ~~~~~~~~~~~~~~~~~~~        
railroad.cpp:98:3: note: in expansion of macro 'rep'
   rep(i,0,edgelist.size()){
   ^~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8184 KB n = 2
2 Correct 9 ms 8184 KB n = 2
3 Correct 9 ms 8184 KB n = 2
4 Correct 9 ms 8184 KB n = 2
5 Correct 8 ms 8184 KB n = 2
6 Correct 9 ms 8184 KB n = 2
7 Correct 8 ms 8184 KB n = 3
8 Correct 9 ms 8184 KB n = 3
9 Correct 8 ms 8184 KB n = 3
10 Correct 9 ms 8184 KB n = 8
11 Correct 9 ms 8188 KB n = 8
12 Correct 9 ms 8184 KB n = 8
13 Correct 8 ms 8184 KB n = 8
14 Correct 8 ms 8184 KB n = 8
15 Correct 9 ms 8188 KB n = 8
16 Correct 8 ms 8184 KB n = 8
17 Correct 8 ms 8184 KB n = 8
18 Correct 9 ms 8184 KB n = 8
19 Correct 9 ms 8184 KB n = 3
20 Correct 9 ms 8184 KB n = 7
21 Correct 9 ms 8184 KB n = 8
22 Correct 9 ms 8184 KB n = 8
23 Correct 9 ms 8184 KB n = 8
24 Correct 9 ms 8184 KB n = 8
25 Correct 9 ms 8184 KB n = 8

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8184 KB n = 2
2 Correct 9 ms 8184 KB n = 2
3 Correct 9 ms 8184 KB n = 2
4 Correct 9 ms 8184 KB n = 2
5 Correct 8 ms 8184 KB n = 2
6 Correct 9 ms 8184 KB n = 2
7 Correct 8 ms 8184 KB n = 3
8 Correct 9 ms 8184 KB n = 3
9 Correct 8 ms 8184 KB n = 3
10 Correct 9 ms 8184 KB n = 8
11 Correct 9 ms 8188 KB n = 8
12 Correct 9 ms 8184 KB n = 8
13 Correct 8 ms 8184 KB n = 8
14 Correct 8 ms 8184 KB n = 8
15 Correct 9 ms 8188 KB n = 8
16 Correct 8 ms 8184 KB n = 8
17 Correct 8 ms 8184 KB n = 8
18 Correct 9 ms 8184 KB n = 8
19 Correct 9 ms 8184 KB n = 3
20 Correct 9 ms 8184 KB n = 7
21 Correct 9 ms 8184 KB n = 8
22 Correct 9 ms 8184 KB n = 8
23 Correct 9 ms 8184 KB n = 8
24 Correct 9 ms 8184 KB n = 8
25 Correct 9 ms 8184 KB n = 8
26 Correct 9 ms 8184 KB n = 8
27 Correct 9 ms 8184 KB n = 8
28 Correct 9 ms 8184 KB n = 8
29 Correct 9 ms 8184 KB n = 16
30 Correct 9 ms 8200 KB n = 16
31 Correct 9 ms 8184 KB n = 16
32 Correct 9 ms 8184 KB n = 16
33 Correct 9 ms 8312 KB n = 16
34 Correct 9 ms 8184 KB n = 16
35 Correct 9 ms 8184 KB n = 16
36 Correct 9 ms 8184 KB n = 15
37 Correct 8 ms 8184 KB n = 8
38 Correct 9 ms 8184 KB n = 16
39 Correct 9 ms 8184 KB n = 16
40 Correct 8 ms 8184 KB n = 9
41 Correct 9 ms 8184 KB n = 16
42 Correct 9 ms 8184 KB n = 16
43 Correct 9 ms 8184 KB n = 16
44 Correct 8 ms 8184 KB n = 9
45 Correct 8 ms 8188 KB n = 15
46 Correct 8 ms 8184 KB n = 16
47 Correct 10 ms 8184 KB n = 16
48 Correct 11 ms 8184 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 27796 KB n = 199999
2 Correct 275 ms 27848 KB n = 199991
3 Correct 278 ms 27976 KB n = 199993
4 Correct 188 ms 22820 KB n = 152076
5 Correct 113 ms 17452 KB n = 93249
6 Correct 228 ms 25672 KB n = 199910
7 Correct 235 ms 26976 KB n = 199999
8 Correct 253 ms 25708 KB n = 199997
9 Correct 224 ms 24872 KB n = 171294
10 Correct 183 ms 22044 KB n = 140872
11 Correct 236 ms 25644 KB n = 199886
12 Correct 247 ms 27696 KB n = 199996
13 Correct 241 ms 26652 KB n = 200000
14 Correct 273 ms 32916 KB n = 199998
15 Correct 263 ms 32748 KB n = 200000
16 Correct 280 ms 33460 KB n = 199998
17 Correct 271 ms 27804 KB n = 200000
18 Correct 262 ms 26792 KB n = 190000
19 Correct 284 ms 25688 KB n = 177777
20 Correct 115 ms 17984 KB n = 100000
21 Correct 258 ms 27976 KB n = 200000
22 Correct 303 ms 33880 KB n = 200000
23 Correct 312 ms 33824 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8184 KB n = 2
2 Correct 9 ms 8184 KB n = 2
3 Correct 9 ms 8184 KB n = 2
4 Correct 9 ms 8184 KB n = 2
5 Correct 8 ms 8184 KB n = 2
6 Correct 9 ms 8184 KB n = 2
7 Correct 8 ms 8184 KB n = 3
8 Correct 9 ms 8184 KB n = 3
9 Correct 8 ms 8184 KB n = 3
10 Correct 9 ms 8184 KB n = 8
11 Correct 9 ms 8188 KB n = 8
12 Correct 9 ms 8184 KB n = 8
13 Correct 8 ms 8184 KB n = 8
14 Correct 8 ms 8184 KB n = 8
15 Correct 9 ms 8188 KB n = 8
16 Correct 8 ms 8184 KB n = 8
17 Correct 8 ms 8184 KB n = 8
18 Correct 9 ms 8184 KB n = 8
19 Correct 9 ms 8184 KB n = 3
20 Correct 9 ms 8184 KB n = 7
21 Correct 9 ms 8184 KB n = 8
22 Correct 9 ms 8184 KB n = 8
23 Correct 9 ms 8184 KB n = 8
24 Correct 9 ms 8184 KB n = 8
25 Correct 9 ms 8184 KB n = 8
26 Correct 9 ms 8184 KB n = 8
27 Correct 9 ms 8184 KB n = 8
28 Correct 9 ms 8184 KB n = 8
29 Correct 9 ms 8184 KB n = 16
30 Correct 9 ms 8200 KB n = 16
31 Correct 9 ms 8184 KB n = 16
32 Correct 9 ms 8184 KB n = 16
33 Correct 9 ms 8312 KB n = 16
34 Correct 9 ms 8184 KB n = 16
35 Correct 9 ms 8184 KB n = 16
36 Correct 9 ms 8184 KB n = 15
37 Correct 8 ms 8184 KB n = 8
38 Correct 9 ms 8184 KB n = 16
39 Correct 9 ms 8184 KB n = 16
40 Correct 8 ms 8184 KB n = 9
41 Correct 9 ms 8184 KB n = 16
42 Correct 9 ms 8184 KB n = 16
43 Correct 9 ms 8184 KB n = 16
44 Correct 8 ms 8184 KB n = 9
45 Correct 8 ms 8188 KB n = 15
46 Correct 8 ms 8184 KB n = 16
47 Correct 10 ms 8184 KB n = 16
48 Correct 11 ms 8184 KB n = 16
49 Correct 271 ms 27796 KB n = 199999
50 Correct 275 ms 27848 KB n = 199991
51 Correct 278 ms 27976 KB n = 199993
52 Correct 188 ms 22820 KB n = 152076
53 Correct 113 ms 17452 KB n = 93249
54 Correct 228 ms 25672 KB n = 199910
55 Correct 235 ms 26976 KB n = 199999
56 Correct 253 ms 25708 KB n = 199997
57 Correct 224 ms 24872 KB n = 171294
58 Correct 183 ms 22044 KB n = 140872
59 Correct 236 ms 25644 KB n = 199886
60 Correct 247 ms 27696 KB n = 199996
61 Correct 241 ms 26652 KB n = 200000
62 Correct 273 ms 32916 KB n = 199998
63 Correct 263 ms 32748 KB n = 200000
64 Correct 280 ms 33460 KB n = 199998
65 Correct 271 ms 27804 KB n = 200000
66 Correct 262 ms 26792 KB n = 190000
67 Correct 284 ms 25688 KB n = 177777
68 Correct 115 ms 17984 KB n = 100000
69 Correct 258 ms 27976 KB n = 200000
70 Correct 303 ms 33880 KB n = 200000
71 Correct 312 ms 33824 KB n = 200000
72 Correct 270 ms 27848 KB n = 200000
73 Correct 297 ms 27768 KB n = 200000
74 Correct 263 ms 27820 KB n = 200000
75 Correct 279 ms 27808 KB n = 200000
76 Correct 263 ms 27848 KB n = 200000
77 Correct 200 ms 26576 KB n = 200000
78 Correct 240 ms 31824 KB n = 200000
79 Correct 244 ms 26068 KB n = 184307
80 Correct 115 ms 15764 KB n = 76040
81 Correct 235 ms 25672 KB n = 199981
82 Correct 350 ms 27720 KB n = 199994
83 Correct 344 ms 26568 KB n = 199996
84 Correct 308 ms 32908 KB n = 199998
85 Correct 269 ms 32840 KB n = 200000
86 Correct 295 ms 33472 KB n = 199998
87 Correct 256 ms 27848 KB n = 200000
88 Correct 262 ms 27976 KB n = 200000
89 Correct 280 ms 28096 KB n = 200000
90 Correct 252 ms 27848 KB n = 200000
91 Correct 315 ms 33836 KB n = 200000
92 Correct 326 ms 33836 KB n = 200000