제출 #588228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588228		SlavicG	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	232 ms	12492 KiB

railroad

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

using namespace std;

const int N = 4e5 + 10;
int p[N];
int get(int a) {
    return p[a] = (p[a] == a ? a : get(p[a]));
}
int uni(int a, int b) {
    a = get(a), b = get(b);
    if(a == b) return 0;
    p[a] = b;
    return 1;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    for(int i = 0; i < N; ++i) p[i] = i;
    s.push_back((int)1e9);
    t.push_back(1);
    vector<int> c, balance(s.size() * 2 + 1, 0);
    for(int i = 0; i < s.size(); ++i) {
        c.push_back(s[i]), c.push_back(t[i]);
    }
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    for(int i = 0; i < (int)s.size(); ++i) {
        s[i] = lower_bound(c.begin(), c.end(), s[i]) - c.begin();
        t[i] = lower_bound(c.begin(), c.end(), t[i]) - c.begin();

        ++balance[s[i]];
        --balance[t[i]];
        uni(s[i], t[i]);
    }
    for(int i = 1; i < s.size() * 2 + 1; ++i) balance[i] += balance[i - 1];
    long long ans = 0;

    vector<pair<int, int>> edges;
    for(int i = 0; i + 1 < (int)c.size(); ++i) {
        if(1LL * (c[i + 1] - c[i]) * balance[i] > 0) {
            ans += 1LL * (c[i + 1] - c[i]) * balance[i];
            uni(i, i + 1);
        } else {
            edges.push_back({c[i + 1] - c[i], i});
        }
    }
    sort(edges.begin(), edges.end());
    for(auto [c, i] : edges) {
        if(uni(i, i + 1)) {
            ans += c;
        }
    }
    return ans;
}
/*
4
1 7
4 3
5 8
6 6
*/

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

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

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