Submission #429136

#	Time	Username	Problem	Language	Result	Execution time	Memory
429136		Antekb	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	1149 ms	62136 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int N=4e5+5;
vector<int> E[N];
int r[N];
int find(int v){
	if(r[v]==v)return v;
	return r[v]=find(r[v]);
}
void Union(int u, int v){
	r[u]=v;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	iota(r, r+N, 0);
    int n = (int) s.size();
    n++;
    s.push_back(2e9);
    t.push_back(1);
    vector<pair<int, int> > V;
    map<int, int> M;
    int wsk=0;
    for(int i=0; i<n; i++){
    	if(M.find(t[i])==M.end())M[t[i]]=wsk++;
    	if(M.find(s[i])==M.end())M[s[i]]=wsk++;
    	V.push_back({s[i], -1});
    	V.push_back({t[i], 1});
    	//cout<<M[s[i]]<<" "<<M[t[i]]<<" "<<s[i]<<" "<<t[i]<<"\n";
    	E[M[s[i]]].push_back(M[t[i]]);
    	E[M[t[i]]].push_back(M[s[i]]);
    }
    //cout<<"\n";
    //for(auto i:M)cout<<i.st<<" "<<i.nd<<"\n";
    //cout<<"\n";
    sort(V.begin(), V.end());
    long long ans=0;
    int ile=0;
    vector<pair<int, pair<int, int>>> edg;
    for(int i=0; i<V.size(); i++){
    	ile+=V[i].nd;
		if(ile<0 && V[i+1].st!=V[i].st){
			E[M[V[i].st]].push_back(M[V[i+1].st]);
			E[M[V[i+1].st]].push_back(M[V[i].st]);
			ans+=-ile*(long long)(V[i+1].st-V[i].st);
		}
		if(ile>0 && V[i+1].st!=V[i].st){
			E[M[V[i].st]].push_back(M[V[i+1].st]);
			E[M[V[i+1].st]].push_back(M[V[i].st]);
		}
		if(i+1<V.size() && V[i].st!=V[i+1].st){
			edg.push_back({V[i+1].st-V[i].st, {M[V[i].st], M[V[i+1].st]}});
		}
    }
    /*int cnt=1;
    for(int i=0; i<n; i++){
    	if(!vis[M[s[i]]])dfs(M[s[i]], wsk++);
    	if(!vis[M[t[i]]])dfs(M[t[i]], wsk++);
    }*/
    for(int i=0; i<wsk; i++){
    	for(int j:E[i]){
    		//cout<<i<<" "<<j<<"\n";
    		Union(find(i), find(j));
    	}
    }
    sort(edg.begin(), edg.end());
    for(int i=0; i<edg.size(); i++){
    	
    	int u=find(edg[i].nd.st), v=find(edg[i].nd.nd);
    	if(u!=v){
    		ans+=edg[i].st;
    		Union(u, v);
    	}
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0; i<V.size(); i++){
      |                  ~^~~~~~~~~
railroad.cpp:53:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   if(i+1<V.size() && V[i].st!=V[i+1].st){
      |      ~~~^~~~~~~~~
railroad.cpp:69:19: 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]
   69 |     for(int i=0; i<edg.size(); i++){
      |                  ~^~~~~~~~~~~

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