제출 #1307994

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

railroad

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

using namespace std;
using ll = long long;

vector<ll> rep, sizes;

ll find(ll u){
    if (u == rep[u]) return u;
    rep[u] = find(rep[u]);
    return rep[u];
}

bool uni(ll a, ll b){
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (sizes[a] < sizes[b]) swap(a, b);
    rep[b] = a;
    sizes[a] += sizes[b];
    return true;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    s.push_back(1e9);
    t.push_back(1);
    ll n = (ll) s.size();
    set<ll> points;
    ll np = 0;
    vector<ll> v;
    map<ll, ll> idx;
    for (ll i=0; i<n; i++){
        points.insert(s[i]);
        points.insert(t[i]);
    }
    for (ll x : points){
        v.push_back(x);
        idx[x] = np++;
    }
    //for (int x : v) cerr << x << " ";
    //cerr << endl;
    //vector<vector<ll>> graph(np);
    rep = sizes = vector<ll>(np);
    iota(rep.begin(), rep.end(), 0);
    //multiset<pair<ll, bool>> segment_ends; // speed, begin(1)/end(0)
    vector<ll> balance_change(np);
    vector<pair<ll, ll>> edges;
    for (ll i=0; i<n; i++){
        edges.push_back({idx[s[i]], idx[t[i]]});
        uni(idx[s[i]], idx[t[i]]);
        balance_change[idx[s[i]]]++;
        balance_change[idx[t[i]]]--;
    }
    /*for (auto[k, v] : idx) cerr << k << ": " << v << endl;

    for (ll x : balance_change) cerr << x << " ";
    cerr << endl;

    for (ll i=0; i<np; i++) cerr << find(i) << " ";
    cerr << endl;

    for (auto[u, v] : edges) cerr << u << " " << v << endl;*/

    ll res = 0;
    ll balance = balance_change[0]; // zu viele nach rechts: positiv, zu viele nach links: negativ
    vector<tuple<ll, ll, ll>> possible_edges;

    for (ll i=1; i<np; i++){
        //cerr << i << ": " << balance << endl;
        if (balance > 0){
            res += (balance * (v[i] - v[i-1]));
            edges.push_back({i, i-1});
            uni(i, i-1);
        }
        if (balance < 0){
            edges.push_back({i-1, i});
            uni(i, i-1);
        }
        possible_edges.push_back({v[i] - v[i-1], i, i-1});
        
        balance += balance_change[i];
    }

    //cerr << "res: " << res << endl;

    sort(possible_edges.begin(), possible_edges.end());

    for (auto[c, a, b] : possible_edges){
        //cerr << c << " " << a << " " << b << endl;
        res += c * uni(a, b);
    }

    //for (ll i=0; i<np; i++) cerr << find(i) << " ";
    //cerr << endl;

    //cerr << endl;
    //for (auto[u, v] : edges) cerr << u << " " << v << endl;
    
    return res;
}

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