/*
PROG: ioi08d
LANG: C++11
_____
.' '.
/ 0 0 \
| ^ |
| \ / |
\ '---' /
'._____.'
*/
#include <bits/stdc++.h>
using namespace std;
template<class T>
void readi(T &x)
{
T input = 0;
bool negative = false;
char c = ' ';
while (c < '-')
{
c = getchar();
}
if (c == '-')
{
negative = true;
c = getchar();
}
while (c >= '0')
{
input = input * 10 + (c - '0');
c = getchar();
}
if (negative)
{
input = -input;
}
x = input;
}
template<class T>
void printi(T output)
{
if (output == 0)
{
putchar('0');
return;
}
if (output < 0)
{
putchar('-');
output = -output;
}
int aout[20];
int ilen = 0;
while(output)
{
aout[ilen] = ((output % 10));
output /= 10;
ilen++;
}
for (int i = ilen - 1; i >= 0; i--)
{
putchar(aout[i] + '0');
}
return;
}
template<class T>
void ckmin(T &a, T b)
{
a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
a = max(a, b);
}
long long randomize(long long mod)
{
return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;
#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 2000013
long long normalize(long long x, long long mod = INF)
{
return (((x % mod) + mod) % mod);
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int N, K;
pii coor[MAXN];
vector<int> compress;
int edge[MAXN];
int dsu[MAXN];
int sz[MAXN];
int cur;
vector<int> sizes;
int find_parent(int u)
{
if (u == dsu[u]) return u;
dsu[u] = find_parent(dsu[u]);
return dsu[u];
}
void merge(int u, int v)
{
u = find_parent(u);
v = find_parent(v);
if (u == v)
{
return;
}
if (sz[u] > sz[v])
{
swap(u, v);
}
sz[v] += sz[u];
sz[u] = 0;
dsu[u] = v;
return;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
srand(time(0));
// cout << fixed << setprecision(10);
// cerr << fixed << setprecision(10);
if (fopen("ioi08d.in", "r"))
{
freopen ("ioi08d.in", "r", stdin);
// freopen ("ioi08d.out", "w", stdout);
}
cin >> N >> K;
for (int i = 0; i < N; i++)
{
cin >> coor[i].fi >> coor[i].se;
compress.PB(coor[i].fi); compress.PB(coor[i].se);
}
sort(compress.begin(), compress.end());
compress.erase(unique(compress.begin(), compress.end()), compress.end());
for (int i = 0; i < N; i++)
{
coor[i].fi = LB(compress.begin(), compress.end(), coor[i].fi) - compress.begin();
coor[i].se = LB(compress.begin(), compress.end(), coor[i].se) - compress.begin();
coor[i].fi++; coor[i].se++;
}
for (int i = 0; i < N; i++)
{
int u = coor[i].fi, v = coor[i].se;
// cerr << u << "--" << v << endl;
edge[u] = v + 1;
edge[v] = u + 1;
}
edge[0] = 1;
edge[2 * N + 1] = 0;
for (int i = 0; i <= 2 * N + 1; i++)
{
dsu[i] = i;
sz[i] = 1;
}
for (int i = 0; i <= 2 * N + 1; i++)
{
merge(i, edge[i]);
}
for (int i = 0; i <= 2 * N + 1; i++)
{
if (find_parent(i) != i)
{
continue;
}
if (i == find_parent(0))
{
cur = sz[i];
}
else
{
sizes.PB(sz[i]);
}
}
// cerr << cur << endl;
// for (int i = 0; i <= 2 * N + 1; i++)
// {
// cerr << i << ' ' << edge[i] << endl;
// }
sort(sizes.begin(), sizes.end());
for (int i = 0; i < K; i++)
{
if (sizes.empty())
{
sizes.PB(1);
cur += 1;
}
else
{
cur += (sizes.back() + 2);
sizes.pop_back();
}
}
cout << cur - 2 << '\n';
//if they're in different components, then
//when you add x...y
//0, 1, 5, 7, so it's pure x/2
// cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
return 0;
}
Compilation message
teleporters.cpp: In function 'int32_t main()':
teleporters.cpp:156:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen ("ioi08d.in", "r", stdin);
~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
748 KB |
Output is correct |
2 |
Correct |
11 ms |
1204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1204 KB |
Output is correct |
2 |
Correct |
14 ms |
1664 KB |
Output is correct |
3 |
Correct |
27 ms |
2572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
2572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
2572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
6756 KB |
Output is correct |
2 |
Correct |
337 ms |
13984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
13984 KB |
Output is correct |
2 |
Correct |
642 ms |
26328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
844 ms |
35916 KB |
Output is correct |
2 |
Correct |
931 ms |
52072 KB |
Output is correct |
3 |
Runtime error |
968 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1095 ms |
66560 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1090 ms |
66560 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |