제출 #289475

#제출 시각아이디문제언어결과실행 시간메모리
289475KastandaRoller Coaster Railroad (IOI16_railroad)C++11
100 / 100
380 ms19976 KiB
// M #include<bits/stdc++.h> #include "railroad.h" using namespace std; typedef long long ll; const int N = 200005 * 2; int n, P[N], S[N], T[N]; int Find(int v) { return (P[v] < 0 ? v : (P[v] = Find(P[v]))); } inline bool Merge(int v, int u) { v = Find(v); u = Find(u); if (v == u) return 0; P[v] = u; return 1; } long long plan_roller_coaster(vector < int > _S, vector < int > _T) { memset(P, -1, sizeof(P)); n = (int)_S.size(); for (int i = 0; i < n; i ++) S[i] = _S[i], T[i] = _T[i]; S[n] = (int)(1e9 + 9); T[n] = 1; vector < int > U; for (int i = 0; i <= n; i ++) { U.push_back(S[i]); U.push_back(T[i]); } sort(U.begin(), U.end()); U.resize(unique(U.begin(), U.end()) - U.begin()); vector < pair < int , int > > A; for (int i = 0; i <= n; i ++) { S[i] = (int)(lower_bound(U.begin(), U.end(), S[i]) - U.begin()); T[i] = (int)(lower_bound(U.begin(), U.end(), T[i]) - U.begin()); A.push_back({S[i], 1}); A.push_back({T[i], -1}); Merge(S[i], T[i]); } sort(A.begin(), A.end()); ll Cur = 0, tot = 0; for (int i = 0; i + 1 < (int)A.size(); i ++) { Cur += A[i].second; if (Cur > 0) tot += Cur * (U[A[i + 1].first] - U[A[i].first]); if (Cur) Merge(A[i].first, A[i + 1].first); } vector < int > R((int)A.size() - 1); iota(R.begin(), R.end(), 0); sort(R.begin(), R.end(), [&](int i, int j){return U[A[i + 1].first] - U[A[i].first] < U[A[j + 1].first] - U[A[j].first];}); for (int i : R) if (Merge(A[i].first, A[i + 1].first)) tot += U[A[i + 1].first] - U[A[i].first]; return tot; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...