제출 #1021363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021363		Issa	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	180 ms	16040 KiB

railroad

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int inf = 1e9 + 100;
const ll INF = 1e18 + 100;
const int maxn = 4e5 + 100;

int n;
ll dp[1<<16][16];
int a[maxn];
int b[maxn];
vector<int> s;
int pref[maxn];
int p[maxn];

int get(int v){
	if(p[v] == v) return v;
	return p[v] = get(p[v]);
}

void join(int a, int b){
	p[get(a)] = get(b);
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t){
	n = s.size();
	for(int i = 0; i < n; i++){
		a[i] = s[i];
		b[i] = t[i];
	}
	if(n <= 16){
		for(int x = 0; x < (1<<n); x++){
			fill(dp[x], dp[x] + n, INF);
			if(!x) continue;
			if(__builtin_popcount(x) == 1){
				for(int i = 0; i < n; i++){
					if(x & (1<<i)) dp[x][i] = 0;
				}
			} else{
				for(int i = 0; i < n; i++){
					if(x & (1<<i)){
						int y = x ^ (1<<i);
						for(int j = 0; j < n; j++){
							if(y & (1<<j)){
								dp[x][i] = min(dp[x][i], dp[y][j] + max(0, t[j] - s[i]));
							}
						}
					}
				}
			}
		}
		return *min_element(dp[(1<<n)-1], dp[(1<<n)-1] + n);
	} else{
		for(int i = 0; i < n; i++){
			s.push_back(a[i]);
			s.push_back(b[i]);
		}
		sort(s.begin(), s.end());
		s.resize(unique(s.begin(), s.end()) - s.begin());
		for(int i = 1; i <= s.size(); i++){
			p[i] = i;
		}
		for(int i = 0; i < n; i++){
			a[i] = lower_bound(s.begin(), s.end(), a[i]) - s.begin() + 1;
			b[i] = lower_bound(s.begin(), s.end(), b[i]) - s.begin() + 1;
			join(a[i], b[i]);
		}
		a[n] = s.size(); b[n] = 1;
		join(s.size(), 1);
		for(int i = 0; i <= n; i++){
			pref[a[i]]++;
			pref[b[i]]--;
		}
		for(int i = 1; i <= s.size(); i++){
			pref[i] += pref[i-1];
			if(pref[i] < 0){
				join(i, i + 1);
			}
		}
		vector<tuple<int, int, int>> v;
		for(int i = 1; i < s.size(); i++){
			if(get(i) != get(i+1)){
				v.push_back({s[i+1] - s[i], i, i + 1});
			}
		}
		sort(v.begin(), v.end());
		ll ans = 0;
		for(auto [x, a, b]: v){
			if(get(a) != get(b)){
				ans += x;
				join(a, b);
			}
		}
		return ans;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int i = 1; i <= s.size(); i++){
      |                  ~~^~~~~~~~~~~
railroad.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i = 1; i <= s.size(); i++){
      |                  ~~^~~~~~~~~~~
railroad.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int i = 1; i < s.size(); i++){
      |                  ~~^~~~~~~~~~

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