Submission #562955

#	Time	Username	Problem	Language	Result	Execution time	Memory
562955		hoanghq2004	Roller Coaster Railroad (IOI16_railroad)	C++14	Compilation error	0 ms	0 KiB

railroad

#include <bits/stdc++.h>

using namespace std;

int n, m;
long long cost;
int in[400010], out[400010];

struct railroad {
    int s, t;
} r[200010];

vector <int> data;
vector <pair <int, pair <int, int> > > edge;

void compress() {
    for (int i = 1; i <= n; ++i) {
        data.push_back(r[i].s);
        data.push_back(r[i].t);
    }

    data.push_back(0);
    sort(data.begin(), data.end());
    data.erase(unique(data.begin(), data.end()), data.end());
    m = data.size() - 1;
    for (int i = 1; i <= n; ++i) {
        r[i].s = lower_bound(data.begin(), data.end(), r[i].s) - data.begin();
        r[i].t = lower_bound(data.begin(), data.end(), r[i].t) - data.begin();
    }
}

int l[400010], h[400010];
int cnt;

int Find(int u) {
    return (u == l[u] ? u : l[u] = Find(l[u]));
}

void Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return;
    if (h[u] < h[v]) swap(u, v);
    h[u] += h[v];
    l[v] = u;
    --cnt;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &r[i].s, &r[i].t);
    compress();
    for (int i = 1; i <= m; ++i) l[i] = i, h[i] = 1;
    cnt = m;
    for (int i = 1; i <= n; ++i) {
        Union(r[i].s, r[i].t);
        ++out[r[i].s], ++in[r[i].t];
    }
    Union(1, m);
    ++in[1], ++out[m];
    for (int i = m; i >= 2; --i) {
        int add = abs(in[i] - out[i]);
        if (add == 0) continue;
        Union(i, i - 1);
        if (in[i] > out[i]) {
            out[i] += add;
            in[i - 1] += add;
            cost += 1ll * add * (data[i] - data[i - 1]);
        }
        else {
            in[i] += add;
            out[i - 1] += add;
        }
    }
    for (int i = 1; i < m; ++i)
        if (Find(i) != Find(i + 1)) {
            edge.push_back({data[i + 1] - data[i], {i, i + 1}});
        }

    sort(edge.begin(), edge.end());
    for (int i = 0; i < edge.size(); ++i)
        if (Find(edge[i].second.first) != Find(edge[i].second.second)) cost += edge[i].first, Union(edge[i].second.first, edge[i].second.second);
    printf("%lld", cost);
}

Compilation message (stderr)

railroad.cpp: In function 'int main()':
railroad.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < edge.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
railroad.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
railroad.cpp:49:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     for (int i = 1; i <= n; ++i) scanf("%d%d", &r[i].s, &r[i].t);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccV9EmXC.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccHi90GB.o:railroad.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccV9EmXC.o: in function `main':
grader.cpp:(.text.startup+0xf4): undefined reference to `plan_roller_coaster(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status