Submission #332429

#	Time	Username	Problem	Language	Result	Execution time	Memory
332429		a14789654	Roller Coaster Railroad (IOI16_railroad)	C++17	Compilation error	0 ms	0 KiB

railroad

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 7;

int par[MAXN], n, in[MAXN], out[MAXN], a[MAXN], b[MAXN];
vector <int> V;

int pos(int x)
{
    return lower_bound(V.begin(), V.end(), x) - V.begin() + 1;
}

int root(int u)
{
    return par[u] < 0 ? u : par[u] = root(par[u]);
}

void join(int u, int v)
{
    if ((u = root(u)) == (v = root(v))) return;
    if (par[u] > par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
}

int main()
{
    if (fopen("tst.inp", "r"))
    {
        freopen("tst.inp", "r", stdin);
        freopen("tst.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i] >> b[i];
        V.push_back(a[i]);
        V.push_back(b[i]);
    }
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());

    for (int i = 1; i <= V.size(); ++i) par[i] = - 1;
    ++out[V.size()];
    ++in[1];
    join(1, V.size());
    for (int i = 1; i <= n; ++i)
    {
        int x = pos(a[i]), y = pos(b[i]);
        join(x, y);
        ++out[x];
        ++in[y];
    }

    vector <pair <int, pair <int, int> > > E;
    int last = - 1;
    long long ans = 0;
    bool ok = 0;
    for (int i = V.size(); i > 1; --i)
    {
        int diff = abs(out[i] - in[i]);
        if (!diff)
        {
            ok = 1;
            continue;
        }
        if (ok && last != - 1)
        {
//            cerr << V[last - 1] << ' ' << V[i - 1] << '\n';
            E.push_back({V[last - 1] - V[i - 1], {last, i}});
//            E.push_back({0, {i, last}});
        }
        ok = 0;
        if (out[i] > in[i]) in[i] += diff, out[i - 1] += diff;
        else out[i] += diff, in[i - 1] += diff, ans += 1LL * diff;
        join(i, i - 1);
        last = i - 1;
    }

    sort(E.begin(), E.end());
    for (auto x: E)
    {
        int r1 = root(x.second.first);
        int r2 = root(x.second.second);
        if (r1 != r2) ans += 1LL * x.first, join(r1, r2);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

railroad.cpp: In function 'int main()':
railroad.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 1; i <= V.size(); ++i) par[i] = - 1;
      |                     ~~^~~~~~~~~~~
railroad.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   32 |         freopen("tst.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
railroad.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   33 |         freopen("tst.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccgvleyx.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc4SF2fG.o:railroad.cpp:(.text.startup+0x0): first defined here
/tmp/ccgvleyx.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