제출 #434408

#제출 시각아이디문제언어결과실행 시간메모리
43440879brueRoller Coaster Railroad (IOI16_railroad)C++14
100 / 100
877 ms88636 KiB
#include <bits/stdc++.h> #include "railroad.h" using namespace std; typedef long long ll; struct Edge{ int x, y; ll z; Edge(){} Edge(int x, int y, ll z): x(x), y(y), z(z){} bool operator<(const Edge &r)const{ return z > r.z; } }; int n, k; vector<int> vec; map<int, int> idx; vector<int> link[500002]; vector<int> revLink[500002]; ll ans; int par[500002]; int find(int x){ if(x == par[x]) return x; return par[x] = find(par[x]); } void merge(int x, int y){ x = find(x), y = find(y); par[x] = y; } ll plan_roller_coaster(vector<int> s, vector<int> t) { n = (int)s.size(); for(int i=0; i<n; i++){ vec.push_back(s[i]); vec.push_back(t[i]); } vec.push_back(1); vec.push_back(1e9); sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); k = (int)vec.size(); for(int i=0; i<k; i++) idx[vec[i]] = i; for(int i=0; i<n; i++){ s[i] = idx[s[i]]; t[i] = idx[t[i]]; link[s[i]].push_back(t[i]); revLink[t[i]].push_back(s[i]); } link[k-1].push_back(0); revLink[0].push_back(k-1); int need = 0; for(int i=0; i<k; i++){ need += (int)link[i].size(); need -= (int)revLink[i].size(); if(need < 0){ link[i].push_back(i+1); revLink[i+1].push_back(i); need++; } else if(need > 0){ link[i+1].push_back(i); revLink[i].push_back(i+1); ans += ll(vec[i+1] - vec[i]) * need; need--; } } for(int i=0; i<k; i++) par[i] = i; for(int i=0; i<k; i++){ for(auto x: link[i]){ merge(i, x); } } priority_queue<Edge> pq; for(int i=0; i<k-1; i++){ pq.push(Edge(i, i+1, vec[i+1] - vec[i])); } while(!pq.empty()){ Edge tmp = pq.top(); pq.pop(); if(find(tmp.x) == find(tmp.y)) continue; ans += tmp.z; merge(tmp.x, tmp.y); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...