Submission #637138

#	Time	Username	Problem	Language	Result	Execution time	Memory
637138		ggoh	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	342 ms	45052 KiB

railroad

//after read editorial :cry:
#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;

int v[400004],deg[400004];
vector<int>G[400004];
int col,par[400004];
int find(int p)
{
  if(p==par[p])return p;
  else return par[p]=find(par[p]);
}
void uni(int p,int q)
{
  p=find(p);q=find(q);
  if(p!=q)par[p]=q;
}
void dfs(int p)
{
  v[p]=col;
  for(auto &k:G[p])if(!v[k])dfs(k);
}
lint plan_roller_coaster(vector<int> s, vector<int> t) {

    int n = sz(s);
    lint ans=0;
    vector<int>X;
    for(int i=0;i<n;i++)X.push_back(s[i]);
    for(int i=0;i<n;i++)X.push_back(t[i]);
    sort(X.begin(),X.end());
    X.erase(unique(X.begin(),X.end()),X.end());
    int m=sz(X);
    for(int i=0;i<n;i++)
    {
      int p,q;
      p=lower_bound(X.begin(),X.end(),s[i])-X.begin();
      q=lower_bound(X.begin(),X.end(),t[i])-X.begin();
      deg[p]++;
      deg[q]--;
      G[p].push_back(q);
    }
    deg[0]--;
    deg[m-1]++;
    int cha=0;
    int ch=0;
    for(int i=0;i<m-1;i++)
    {
      deg[i]+=cha;
      cha=deg[i];
      if(deg[i]<0)
      {
        G[i].push_back(i+1);
      }
      else if(deg[i]>0)
      {
        G[i+1].push_back(i);
        ans+=1ll*deg[i]*(X[i+1]-X[i]);
      }
    }
    col=0;
    for(int i=0;i<m;i++)
    {
      if(!v[i])
      {
        col++;
        dfs(i);
      }
    }
    for(int i=1;i<=col;i++)par[i]=i;
    priority_queue<pii>P;
    for(int i=0;i<m-1;i++)P.push({-(X[i+1]-X[i]),i});
    while(!P.empty())
    {
      pii p=P.top();P.pop();
      if(find(v[p.second])!=find(v[p.second+1]))
      {
        uni(v[p.second],v[p.second+1]);
        ans+=-p.first;
      }
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'lint plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:49:9: warning: unused variable 'ch' [-Wunused-variable]
   49 |     int ch=0;
      |         ^~

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