제출 #1232670

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

railroad

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

using ll = long long;
using tri = tuple<int, int, int>;

const int MXN = 2e5+5;

int dsu[MXN<<1];

int find(int v) { return v==dsu[v] ? v : dsu[v] = find(dsu[v]); }

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int) s.size();
    vector<int> cmp;
    cmp.push_back(1);
    cmp.push_back(1e9);
    for(int i=0; i<n; i++) cmp.push_back(s[i]), cmp.push_back(t[i]);
    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end())-cmp.begin());
    auto GI = [&](int x) -> int {
        return lower_bound(cmp.begin(), cmp.end(), x)-cmp.begin();
    };
    iota(dsu, dsu+cmp.size(), 0);
    vector<int> p(cmp.size(), 0);
    p[cmp.size()-1]++;
    p[0]--;
    dsu[find(0)] = find(cmp.size()-1);
    for(int i=0; i<n; i++) p[GI(s[i])]++, p[GI(t[i])]--, dsu[find(GI(s[i]))] = find(GI(t[i]));
    vector<tri> E;
    ll ans = 0;
    for(int i=0; i+1<p.size(); i++) {
        if(i) p[i] += p[i-1];
        if(p[i])
            dsu[find(i)] = find(i+1);
        else E.push_back({cmp[i+1]-cmp[i], i, i+1});
        if(p[i]>0)
            ans += 1ll*p[i]*(cmp[i+1]-cmp[i]);
    }
    sort(E.begin(), E.end(), [&](tri x, tri y) { return get<0>(x)<get<0>(y); });
    for(tri e : E) {
        int u = find(get<1>(e)), v = find(get<2>(e));
        if(u!=v) {
            ans += get<0>(e);
            dsu[u] = v;
        }
    }
    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