제출 #289463

#제출 시각아이디문제언어결과실행 시간메모리
289463KastandaRoller Coaster Railroad (IOI16_railroad)C++11
34 / 100
2045 ms27584 KiB
// M #include<bits/stdc++.h> #include "railroad.h" using namespace std; typedef long long ll; int n; map < int , int > P; int Find(int v) { return (!P[v] ? 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) { n = (int)S.size(); vector < pair < int , int > > A; for (int i = 0; i < n; i ++) { A.push_back({S[i], 1}); A.push_back({T[i], -1}); Merge(S[i], T[i]); } A.push_back({(int)(1e9 + 9), 1}); A.push_back({1, -1}); 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 * (A[i + 1].first - 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 A[i + 1].first - A[i].first < A[j + 1].first - A[j].first;}); for (int i : R) if (Merge(A[i].first, A[i + 1].first)) tot += A[i + 1].first - 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...