| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 966378 | anango | Shortcut (IOI16_shortcut) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
class DSU {
private:
int n;
vector<int> parent;
vector<int> rank;
public:
DSU(int siz) {
n=siz;
parent=vector<int>(n,-1);
rank=vector<int>(n,0);
for (int i=0; i<n; i++) {
parent[i]=i;
}
}
int find(int node) {
if (node==parent[node]) {
return node;
}
return parent[node] = find(parent[node]);
}
void link(int u, int v) {
u=find(u);
v=find(v);
if (u==v) {
return;
}
if (rank[u]<rank[v]) {
swap(u,v);
}
if (rank[u]==rank[v]) {
rank[u]++;
}
parent[v]=u;
return;
}
vector<int> getpar() {
for (int i=0; i<n; i++) {
find(i);
}
return parent;
}
};
int plan_roller_coaster(vector<int32_t> s, vector<int32_t> t) {
int n = (int) s.size();
int INF=1000000007;
set<int> crucial;
for (int i=0; i<n; i++) {
crucial.insert(s[i]);
crucial.insert(t[i]);
}
crucial.insert(1);
crucial.insert(INF);
int cr = crucial.size();
map<int,int> rev;
vector<int> cval;
for (auto i:crucial) {
cval.push_back(i); //coordinate compression
}
// cout << "COMPRESSION" << endl;
for (int i=0; i<cr; i++) {
rev[cval[i]] = i;
// cout << rev[cval[i]] <<" " << cval[i] << endl;
}
for (int i=0; i<n; i++) {
s[i]=rev[s[i]];
t[i]=rev[t[i]]; //sorry for polluting the arrays given, check this does not cause a bug in the orange juice
}
// cout << "OR ARRAYS" << endl;
for (int i=0; i<n; i++) {
// cout << s[i] <<" " << t[i] << endl;
}
vector<int> deltadiffarray(cr+1,0); //sum of blubberisation coefficients up to cr[i], each is cr[i] to cr[i+1] delta
for (int i=0; i<n; i++) {
deltadiffarray[s[i]]++;
deltadiffarray[t[i]]--;
// cout << "+"<<s[i] <<" -"<< t[i] << endl;
}
deltadiffarray[0]--;
deltadiffarray[cr-1]++; //make the req val 1
vector<int> deltas(cr,0);
int su=0;
int operations = 0;
for (int i=0; i<cr-1; i++) {
su+=deltadiffarray[i];
deltas[i] = su;
if (deltas[i]>0) {
operations += deltas[i]*(cval[i+1] - cval[i]);
}
}
// cout << "DELTA DIFFS" << endl;
for (int i=0; i<cr; i++) {
// cout << i <<" " << deltadiffarray[i] << endl;
}
// cout << "DELTAS" << endl;
for (int i=0; i<cr; i++) {
// cout << i <<" " << deltas[i] << endl;
}
DSU comp(cr);
for (int i=0; i<n; i++) {
comp.link(s[i],t[i]);
// cout << "linking " << s[i] <<" " << t[i] << endl;
}
for (int i=0; i<cr-1; i++) {
if (deltas[i]!=0) {
comp.link(i,i+1);
}
}
vector<int> components = comp.getpar();
// cout << "COMPONENTS" << endl;
for (int i=0; i<cr; i++) {
// cout << i <<" " << components[i] << endl;
}
set<int> comps;
for (auto i:components) {
comps.insert(i);
}
vector<int> cvec;
vector<int> revvec(400000, -1);
for (auto i:comps) {
cvec.push_back(i);
}
int tau = cvec.size();
for (int i=0; i<tau; i++) {
revvec[cvec[i]] = i;
}
vector<vector<pair<int,int>>> adjlist(tau);
vector<vector<int>> edges;
for (int i=0; i<cr-1; i++) {
if (components[i] == components[i+1]) {
continue;
}
int dist = cval[i+1] - cval[i];
adjlist[revvec[components[i]]].push_back({revvec[components[i+1]],dist});
adjlist[revvec[components[i+1]]].push_back({revvec[components[i]],dist});
edges.push_back({revvec[components[i]],revvec[components[i+1]],dist});
}
//use the method of Kruskal, reusing the DSU, to find the component sum of min span tree
DSU K(tau);
sort(edges.begin(), edges.end(), [=](const vector<int> &v1, const vector<int> &v2) {
return v1[2] < v2[2];
});
int cost=0;
for (vector<int> edge:edges) {
int u,v,w;
u=edge[0];
v=edge[1];
w=edge[2];
if (K.find(u)==K.find(v)) {
continue;
}
K.link(u,v);
cost+=w;
}
return operations+cost;
}