# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
53994 |
2018-07-02T07:24:28 Z |
윤교준(#1456) |
Teleporters (IOI08_teleporters) |
C++11 |
|
898 ms |
110816 KB |
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <queue>
#define pb push_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;
int f(vector<int> &V, int i) {
chk[i] = true;
V.pb(i);
i = C[i];
if (!i) return 0;
if (chk[i]) return i;
return f(V, i);
}
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios::sync_with_stdio(false);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> A[i] >> B[i];
}
VX.pb(0); VX.pb(MAXX - 1);
for (int i = 1; i <= N; i++) {
VX.pb(A[i]);
VX.pb(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; i < sz(VX); i++) {
if (chk[i]) continue;
vector<int> V;
int t = f(V, i);
if (V[0] != t) {
puts("SEX");
}
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 time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
852 KB |
Output is correct |
2 |
Correct |
7 ms |
1492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1492 KB |
Output is correct |
2 |
Correct |
8 ms |
2004 KB |
Output is correct |
3 |
Correct |
25 ms |
4072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
4072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
4072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
11240 KB |
Output is correct |
2 |
Correct |
251 ms |
27052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
27052 KB |
Output is correct |
2 |
Correct |
397 ms |
41812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
527 ms |
41812 KB |
Output is correct |
2 |
Correct |
642 ms |
43456 KB |
Output is correct |
3 |
Correct |
628 ms |
65980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
823 ms |
65980 KB |
Output is correct |
2 |
Correct |
898 ms |
65980 KB |
Output is correct |
3 |
Correct |
792 ms |
109488 KB |
Output is correct |
4 |
Correct |
825 ms |
110816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
849 ms |
110816 KB |
Output is correct |
2 |
Correct |
849 ms |
110816 KB |
Output is correct |
3 |
Correct |
559 ms |
110816 KB |
Output is correct |
4 |
Correct |
808 ms |
110816 KB |
Output is correct |