제출 #1236426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236426		PlayVoltz	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	164 ms	12740 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

vector<int> dsu, ord;

int id(int a){
	return lower_bound(ord.begin(), ord.end(), a)-ord.begin();
}

int fp(int a){
	if (dsu[a]==-1)return a;
	return dsu[a]=fp(dsu[a]);
}

bool merge(int a, int b){
	a=fp(a), b=fp(b);
	if (a==b)return 0;
	dsu[a]=b;
	return 1;
}

long long plan_roller_coaster(vector<int> s, vector<int> t){
	ord.resize(2, 1);
	ord[1]=1000000005;
	for (int i=0; i<s.size(); ++i)ord.pb(s[i]), ord.pb(t[i]);
	sort(ord.begin(), ord.end());
	ord.erase(unique(ord.begin(), ord.end()), ord.end());
	vector<int> psum(ord.size(), 0);
	--psum[0], ++psum[ord.size()-1];
	dsu.resize(ord.size(), -1);
	merge(0, ord.size()-1);
	for (int i=0; i<s.size(); ++i)++psum[id(s[i])], --psum[id(t[i])], merge(id(s[i]), id(t[i]));
	vector<pair<int, pii> > edges;
	long long ans=0;
	for (int i=1; i<ord.size(); ++i){
		psum[i]+=psum[i-1];
		if (psum[i-1])merge(i, i-1);
		else edges.pb(mp(ord[i]-ord[i-1], mp(i, i-1)));
		ans+=max(0ll, 1ll*psum[i-1]*(ord[i]-ord[i-1]));
	}
	sort(edges.begin(), edges.end());
	for (auto c:edges)if (merge(c.se.fi, c.se.se))ans+=c.fi;
	return ans;
}

컴파일 시 표준 에러 (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