oj.uz

Submission #910633

# Submission time Handle Problem Language Result Execution time Memory
910633 2024-01-18T06:32:37 Z josanneo22 Teleporters (IOI08_teleporters) C++17
100 / 100
 403 ms 48076 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)

struct node {
	int index, pos;
}a[2000005];
inline bool cmp(const node& A, const node& B) { return A.pos < B.pos; }
int nxt[2000005], N, M, sz[2000005], cnt;
bool vis[2000005];
void dfs(int u){
    if (vis[u]) return;
    vis[u] = true;
    sz[cnt]++;
    if (!vis[nxt[u]]) dfs(nxt[u]);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N >> M;
	L(i, 1, N) {
		int l, r; cin >> l >> r;
		a[i].index = i;
		a[i].pos = l;

		a[i + N].index = i + N;
		a[i + N].pos = r;
	}
	sort(a + 1, a + 2 * N + 1, cmp);
	L(i, 1, N * 2) {
		//cerr << a[i].index << ' ';
		if (a[i].index >= N + 1) {
			int x = a[i].index - N, y = a[i].index;
			a[i].index = y;
			a[i].pos = x;
		}
		else {
			int x = a[i].index, y = N + a[i].index;
			a[i].index = x;
			a[i].pos = y;
		}
		//cerr << a[i].left << ' ' << a[i].right << ' ';
	}
	//cerr << '\n';
	a[0].pos = 0;
	L(i, 1, 2 * N) nxt[a[i - 1].pos] = a[i].index;
	nxt[a[2 * N].pos] = 0;
	
	memset(vis, 0, sizeof(vis));
	memset(sz, 0, sizeof(sz));
	L(i, 0, 2 * N) {
		if (!vis[i]) {
			cnt++;
			sz[cnt] = 0;
			dfs(i);
		}
	}
	//~ L(i, 0, 2 * N){
		//~ cerr << i << " has neighbours : ";
		//~ for(auto & v : G[i]) cerr << v << ' ';
		//~ cerr << '\n';
	//~ }
	sort(sz + 2, sz + cnt + 1, greater<int>());
	int ans = sz[1] - 1;
	//~ cerr << "cycle: ";
	//~ for(auto & v: sz){
		//~ cerr << v << ' ';
	//~ }
	//~ cerr << '\n';
	L(i, 2, cnt) {
		if (M == 0) break;
		M--;
		ans += sz[i];
		ans += 2;
	}
	if (M & 1) { ans++; M--; }
	ans += 2 * M;
	cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12760 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 6 ms 12892 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12756 KB Output is correct
2 Correct 6 ms 12888 KB Output is correct
3 Correct 11 ms 13084 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13148 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12944 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 18004 KB Output is correct
2 Correct 111 ms 21304 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 20676 KB Output is correct
2 Correct 167 ms 26708 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 34128 KB Output is correct
2 Correct 286 ms 37204 KB Output is correct
3 Correct 301 ms 41960 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 39900 KB Output is correct
2 Correct 372 ms 40532 KB Output is correct
3 Correct 379 ms 47680 KB Output is correct
4 Correct 382 ms 48076 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 42688 KB Output is correct
2 Correct 385 ms 40928 KB Output is correct
3 Correct 352 ms 41028 KB Output is correct
4 Correct 385 ms 48064 KB Output is correct