fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include "railroad.h"
  3. #define ff first
  4. #define ss second
  5. using namespace std;
  6.  
  7. long long plan_roller_coaster(vector<int> s, vector<int> t) {
  8. 	int N =s.size();
  9. 	map<int,int> comp;
  10. 	for(int i =0; i < N; i++) comp[s[i]] =comp[t[i]] =0;
  11. 	int m =0;
  12. 	for(auto it =comp.begin(); it != comp.end(); it++) it->ss =m++;
  13. 	vector<int> dif(m,0),pos(m);
  14. 	for(auto it =comp.begin(); it != comp.end(); it++) pos[it->ss] =it->ff;
  15. 	for(int i =0; i < N; i++) {
  16. 		dif[comp[s[i]]]--;
  17. 		dif[comp[t[i]]]++;}
  18.  
  19. 	vector< vector< pair<int,int> > > G(m);
  20. 	int x =1;
  21. 	long long ans =0;
  22. 	for(int i =0; i < m-1; i++) {
  23. 		x +=dif[i];
  24. 		if(x < 0) {
  25. 			ans +=1LL*(-x)*(pos[i+1]-pos[i]);
  26. 			G[i+1].push_back(make_pair(0,i));}
  27. 		if(x > 0) G[i].push_back(make_pair(0,i+1));
  28. 		G[i+1].push_back(make_pair(pos[i+1]-pos[i],i));
  29. 		G[i].push_back(make_pair(pos[i+1]-pos[i],i+1));}
  30. 	for(int i =0; i < N; i++) G[comp[s[i]]].push_back(make_pair(0,comp[t[i]]));
  31.  
  32. 	priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > q;
  33. 	vector<int> vis(m,0);
  34. 	vis[0] =1;
  35. 	for(auto p:G[0]) q.push(p);
  36. 	while(!q.empty()) {
  37. 		pair<int,int> p =q.top();
  38. 		q.pop();
  39. 		if(vis[p.ss]) continue;
  40. 		for(auto r:G[p.ss]) q.push(r);
  41. 		vis[p.ss] =1;
  42. 		ans +=p.ff;}
  43.  
  44.     return ans;}
  45.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:2:22: fatal error: railroad.h: No such file or directory
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/tSkR7h
IOI 2016 railroad
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!