Submission #915295

#	Time	Username	Problem	Language	Result	Execution time	Memory
915295		winter0101	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	895 ms	40380 KiB

railroad

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=4e5+9;
int f[maxn];
int fs(int u){
if (f[u]<0)return u;
return f[u]=fs(f[u]);
}
map<int,int>ns;
int unite(int u,int v,int w){
u=ns[u],v=ns[v];
u=fs(u),v=fs(v);
if (u==v)return 0;
if (f[u]>f[v])swap(u,v);
f[u]+=f[v];
f[v]=u;
return w;
}
int a[maxn];//i to i+1
void add(int u,int v){
u=ns[u],v=ns[v];
if (u>v){
a[v]--;
a[u]++;
}
else {
a[u]++;
a[v]--;
}
}
const int inf=1e9;
struct edg{
int u,v,w;
};
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    vector<int>b;
    b.pb(1),b.pb(inf);
    for1(i,0,n-1){
    b.pb(s[i]);
    b.pb(t[i]);
    }
    sort(all(b));
    b.resize(distance(b.begin(),unique(all(b))));
    for1(i,0,sz(b)-1)ns[b[i]]=i+1;
    int m=sz(b);
    for1(i,1,m)f[i]=-1;
    unite(1,inf,0);
    add(inf,1);
    for1(i,0,n-1){
    add(s[i],t[i]);
    unite(s[i],t[i],0);
    }
    for1(i,1,m)a[i]+=a[i-1];
    long long ans=0;
    for1(i,1,m-1){
    if (a[i]>0){
    ans+=1ll*a[i]*(b[i]-b[i-1]);
    }
    if (a[i]!=0){
    unite(b[i-1],b[i],0);
    }
    }
    vector<edg>temp;
    for1(i,1,m-1){
    temp.pb({b[i-1],b[i],b[i]-b[i-1]});
    }
    sort(all(temp),[](const edg p,const edg q){
    return p.w<q.w;
    });
    for(auto v:temp){
    ans+=unite(v.u,v.v,v.w);
    }
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36