제출 #1138407

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

railroad

#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct dsu
{
	vector<int> par;
	int cnt;
	dsu (int sz)
	{
		cnt = sz;
		par = vector<int>(sz);
		for (int i = 0; i < sz; i++)
			par[i]=i;
	}
	int mnz(int x)
	{
		return par[x] = (x == par[x] ? x : mnz(par[x]));
	}
	void zd(int x, int y)
	{
		x=mnz(x);
		y=mnz(y);
		if (x==y)return;
		cnt--;
		par[y]=x;
	}
};

const ll inf = 1e9;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
	s.push_back(inf);
	t.push_back(1);
	int n = (int)s.size();
	vector<array<ll, 3>> a;
	for (int i = 0; i < n; i++)
	{
		a.push_back({s[i], 1, i});
		a.push_back({t[i], -1, i});
	}
	// a.push_back({1, -1, n});
	// a.push_back({0, -1, n});
	sort(a.begin(), a.end(), [](array<ll, 3>&p, array<ll, 3>&d){return p[0]<d[0];});
	ll rez = 0, st = 0;
	dsu ds(n);
	vector<array<ll, 3>> edges;
	for (int i = 0; i < 2*n-1; i++)
	{
		st+=a[i][1];
		rez+=max(0ll, st)*(a[i+1][0]-a[i][0]);
		edges.push_back({a[i+1][0]-a[i][0], a[i+1][2], a[i][2]});
		if (st || a[i+1][0]==a[i][0])
			ds.zd(a[i+1][2], a[i][2]);
	}
	sort((edges).begin(), edges.end(), [](array<ll, 3>&p, array<ll, 3>&d){return p[0]<d[0];});
	for (int i = 0; i < 2*n-1; i++)
	{
		if (ds.mnz(edges[i][2]) != ds.mnz(edges[i][1]))
		{
			ds.zd(edges[i][2], edges[i][1]);
			rez += edges[i][0];
		}
	}
	return rez;
}

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