제출 #595271

#제출 시각아이디문제언어결과실행 시간메모리
595271LucppRoller Coaster Railroad (IOI16_railroad)C++17
34 / 100
2039 ms46120 KiB
#include "railroad.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<int> par; void init(int n){ par.resize(n); for(int i = 0; i < n; i++) par[i] = i; } int find(int i){ if(par[i] == i) return i; else return par[i] = find(par[i]); } void merge(int a, int b){ a = find(a), b = find(b); par[a] = b; } vector<vector<int>> g; vector<int> comp; int dfs_cnt = 0; void dfs(int u){ comp[u] = dfs_cnt; for(int v : g[u]){ if(comp[v] == -1) dfs(v); } } ll plan_roller_coaster(vector<int> s, vector<int> t) { s.push_back(int(1e9+1)); t.push_back(1); int n = (int)s.size(); vector<pair<int, int>> v; vector<pair<int, int>> edges; for(int i = 0; i < n; i++){ v.emplace_back(s[i], 1); v.emplace_back(t[i], -1); edges.emplace_back(s[i], t[i]); } sort(v.begin(), v.end()); int last = 1; int sum = 0; ll ans = 0; for(auto [p, change] : v){ if(p != last){ if(sum != 0) edges.emplace_back(last, p), edges.emplace_back(p, last); ans += (ll)max(0, sum)*(p-last); last = p; } sum += change; } set<int> nodes; for(auto [u, v] : edges) nodes.insert(u), nodes.insert(v); vector<int> vnode(nodes.begin(), nodes.end()); n = (int)nodes.size(); g.resize(n); for(auto [u, v] : edges){ int a = int(find(vnode.begin(), vnode.end(), u)-vnode.begin()); int b = int(find(vnode.begin(), vnode.end(), v)-vnode.begin()); g[a].push_back(b); } comp.resize(n, -1); for(int i = 0; i < n; i++){ if(comp[i] == -1) dfs(i), dfs_cnt++; } vector<tuple<int, int, int>> ed; for(int i = 1; i < n; i++){ if(comp[i] != comp[i-1]){ ed.emplace_back(vnode[i]-vnode[i-1], comp[i], comp[i-1]); } } sort(ed.begin(), ed.end()); init(dfs_cnt); for(auto [c, a, b] : ed){ if(find(a) != find(b)){ ans += c; merge(a, b); } } 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...