제출 #157088

#제출 시각아이디문제언어결과실행 시간메모리
157088youngyojunTeleporters (IOI08_teleporters)C++11
85 / 100
751 ms65540 KiB
#include <bits/stdc++.h> #define eb emplace_back #define sz(V) ((int)(V).size()) #define allv(V) ((V).begin()),((V).end()) #define sorv(V) sort(allv(V)) #define upmax(a,b) (a)=max((a),(b)) #define upmin(a,b) (a)=min((a),(b)) using namespace std; typedef long long ll; const int MAXN = 1000005; const int MAXX = 2000005; priority_queue<int> PQ; vector<int> VX; int C[MAXX]; int LI[MAXX], RI[MAXX]; int A[MAXN], B[MAXN]; bitset<MAXX> chk; int N, M, Ans; void f(vector<int> &V, int i) { chk[i] = true; V.eb(i); i = C[i]; if(!i || chk[i]) return; f(V, i); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M; for(int i = 1; i <= N; i++) cin >> A[i] >> B[i]; VX.eb(0); VX.eb(MAXX-1); for(int i = 1; i <= N; i++) { VX.eb(A[i]); VX.eb(B[i]); } sorv(VX); LI[0] = 0; RI[MAXX-1] = sz(VX)-1; for(int i = 1; i + 1 < sz(VX); i++) { RI[VX[i]] = i; LI[VX[i]] = i+1; } for(int i = 1; i <= N; i++) { C[RI[A[i]]] = LI[B[i]]; C[RI[B[i]]] = LI[A[i]]; } { vector<int> V; f(V, 1); Ans = sz(V)-1; } for(int i = 1, n = sz(VX); i < n; i++) { if(chk[i]) continue; vector<int> V; f(V, i); PQ.push(sz(V)); } for(; M--;) { if(!PQ.empty()) { Ans += PQ.top() + 2; PQ.pop(); } else { Ans++; PQ.push(1); } } cout << Ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...