Submission #404570

#	Time	Username	Problem	Language	Result	Execution time	Memory
404570		MDario	Roller Coaster Railroad (IOI16_railroad)	C++11	100 / 100	1364 ms	103044 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int) s.size();
    vector<pair<ll, ll>> v1, v, g[400003];
    for(int i=0; i<n; i++){
        v1.push_back({s[i], 1});
        v1.push_back({t[i], -1});
    }
    v1.push_back({1, -1});
    v1.push_back({1e9, 1});
    sort(v1.begin(), v1.end());
    for(int i=0; i<v1.size(); i++){
        if(i==0||v1[i].F!=v1[i-1].F)v.push_back({v1[i].F, 0ll});
        v.back().S+=v1[i].S;
    }
    map<ll, ll> m;
    for(int i=0; i<v.size(); i++){
        m[v[i].F]=i;
    }
    ll r=0;
    for(int i=0; i<v.size()-1; i++){
        if(i!=0)v[i].S+=v[i-1].S;
        r+=(v[i+1].F-v[i].F)*max(0ll, v[i].S);
        if(v[i].S==0){
            g[i].push_back({i+1, (v[i+1].F-v[i].F)});
            g[i+1].push_back({i, (v[i+1].F-v[i].F)});
        }
        else{
            g[i].push_back({i+1, 0});
            g[i+1].push_back({i, 0});
        }
    }
    for(int i=0; i<n; i++){
        g[m[s[i]]].push_back({m[t[i]], 0});
        g[m[t[i]]].push_back({m[s[i]], 0});
    }
    g[m[1]].push_back({m[1e9], 0});
    g[m[1e9]].push_back({m[1], 0});
    priority_queue<pair<ll, ll>> q;
    ll a=v.size();
    bool b[a+1];
    for(int i=0; i<=a; i++){
        b[i]=0;
    }
    q.push({0, 0});
    pair<ll, ll> t1;
    while(!q.empty()){
        t1=q.top();
        q.pop();
        if(b[t1.S])continue;
        b[t1.S]=1;
        r-=t1.F;
        for(auto i : g[t1.S]){
            q.push({-i.S, i.F});
        }
    }
    return r;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0; i<v1.size(); i++){
      |                  ~^~~~~~~~~~
railroad.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~
railroad.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0; i<v.size()-1; i++){
      |                  ~^~~~~~~~~~~

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