Submission #1306072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306072		thelegendary08	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	599 ms	125652 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
#define int long long 
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define dout(x); cout<<x<<' '<<#x<<endl;
#define dout2(x,y); cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v); for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
const int inf = 1e9+5; 
int id = 0; 
vector<set<int>>adj; vi vis, cc; 
void dfs(int node){
	vis[node] = 1; cc[node] = id;
	for(auto u : adj[node]){
		if(vis[u])continue; 
		dfs(u);
	}
}
struct DSU{
	vi par, sz;
	DSU(int n){
		par.resize(n); sz.resize(n); f0r(i,n)par[i]=i,sz[i]=1;
	}
	int find(int x){
		if(x == par[x])return x; return par[x] = find(par[x]);
	}
	void unite(int a, int b){
		a = find(a); b = find(b); if(a==b)return;
		if(sz[a] < sz[b])swap(a,b); 
		sz[a] += sz[b]; 
		par[b] = a; 
	}
};
long long plan_roller_coaster(std::vector<signed> s, std::vector<signed> t) {
	int ans = 0; 
    s.pb(inf); t.pb(1); int n = s.size(); vpii w(n); f0r(i,n)w[i].first=s[i],w[i].second=t[i]; map<int,int> cmp; set<int>gg; 
    for(auto [a,b] : w)gg.insert(a),gg.insert(b); vi g; for(auto u : gg)g.pb(u); f0r(i,g.size())cmp[g[i]]=i; 
	int m = g.size(); adj.resize(m); vi d(m); for(auto [x,y] : w){
		int a = cmp[x], b = cmp[y]; adj[a].insert(b); int dif = 1; if(a > b)swap(a,b),dif=-1;
		d[a]+=dif; d[b]-=dif; 
	}

	int cur = 0; vi cr(m-1); f0r(i,m-1){
		cur += d[i]; cr[i] = cur; if(cr[i] > 0){
			ans += (g[i+1] - g[i]) * cr[i]; adj[i+1].insert(i);
		}
		if(cr[i] < 0){
			adj[i].insert(i+1);
		}
	}
	vis.resize(m); cc.resize(m); 
	f0r(i,m)if(!vis[i]){
		dfs(i); 
		id++;
	}
	int k = id; vector<pair<int,pii>>edges; DSU D = DSU(k); 
	f0r(i,m-1)if(cc[i] != cc[i+1]){
		edges.pb(mp(g[i+1] - g[i], mp(cc[i], cc[i+1])));
	}
	sort(edges.begin(),edges.end()); f0r(i,edges.size()){
		int w = edges[i].first; int a = edges[i].second.first, b = edges[i].second.second;
		if(D.find(a)==D.find(b))continue;
		ans+=w; D.unite(a,b); 
	}
	return ans;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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