Submission #1171542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171542		Hanksburger	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	609 ms	67180 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll revmp[400005], num[400005], visited[400005], par[400005];
vector<pair<ll, pair<ll, ll> > > edges;
vector<pair<ll, ll> > adj[400005];
map<ll, ll> mp;
queue<ll> q;
ll findPar(ll u)
{
    return par[u]==u?u:(par[u]=findPar(par[u]));
}
ll plan_roller_coaster(vector<int> a, vector<int> b)
{
    a.push_back(1e9);
    b.push_back(1);
    ll n=a.size(), cnt=0, sz=0, ans=0;
    for (ll i=0; i<n; i++)
        mp[a[i]]=mp[b[i]]=1;
    for (auto it=mp.begin(); it!=mp.end(); it++)
        it->second=(++cnt), revmp[cnt]=it->first;
    for (ll i=0; i<n; i++)
        num[mp[a[i]]]++, num[mp[b[i]]]--;
    for (ll i=1; i<=cnt; i++)
    {
        num[i]+=num[i-1];
        if (num[i]>0)
        {
            adj[i+1].push_back({i, num[i]});
            ans+=(revmp[i+1]-revmp[i])*num[i];
        }
        else if (num[i]<0)
            adj[i].push_back({i+1, -num[i]});
    }
    for (ll i=0; i<n; i++)
        adj[mp[a[i]]].push_back({mp[b[i]], 1});
    for (ll i=1; i<=cnt; i++)
    {
        if (visited[i])
            continue;
        q.push(i);
        visited[i]=(++sz);
        while (!q.empty())
        {
            ll u=q.front();
            q.pop();
            for (ll j=0; j<adj[u].size(); j++)
            {
                ll v=adj[u][j].first;
                if (!visited[v])
                {
                    q.push(v);
                    visited[v]=sz;
                }
            }
        }
    }
    for (ll i=1; i<cnt; i++)
        if (visited[i]!=visited[i+1])
            edges.push_back({revmp[i+1]-revmp[i], {visited[i], visited[i+1]}});
    sort(edges.begin(), edges.end());
    for (ll i=1; i<=sz; i++)
        par[i]=i;
    for (ll i=0; i<edges.size(); i++)
    {
        ll u=edges[i].second.first, v=edges[i].second.second;
        if (findPar(u)!=findPar(v))
        {
            par[par[u]]=par[v];
            ans+=edges[i].first;
        }
    }
    return ans;
}

Compilation message (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