Submission #915302

#	Time	Username	Problem	Language	Result	Execution time	Memory
915302		winter0101	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	821 ms	40084 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;
};
/*
voi 1 dap an thoa man thi ta se noi dinh cuoi them voi dinh s=1e9 t=1 cost se khong doi
nhan xet la neu ta dung do thi voi s->t thi xet i->i+1 thi so lan i->i+1 = so lan i+1->i vi neu khong se khong the tu 1 quay ve 1 duoc
thi ta nhan xet ta co the dung them so canh i->i+1 tuy y vi no tuong duong voi van toc hien tai dang <= s tiep theo thi ta tang no ngang=s cung duoc
con voi moi 1 canh i+1->i thi se +1 vao dap an vi no tuong duong duong ray giam toc do
neu do thi da thoa man dieu kien tren ma van chua lien thong thi ta co the add them 1 canh i->j va j->i voi i j thuoc 2 tplt khac nhau cost la abs(j-i)
tu day bai toan thanh tim mst cho do thi
*/
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