oj.uz

Submission #910598

# Submission time Handle Problem Language Result Execution time Memory
910598 2024-01-18T06:09:57 Z josanneo22 Teleporters (IOI08_teleporters) C++17
85 / 100
 414 ms 65536 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)

constexpr int _N = 2E6 + 5;
struct node{
	bool first;
	int index, pos, left, right;
}a[_N];
inline bool cmp(const node &A, const node &B){ return A.pos < B.pos;}
int nxt[_N], N, M, sz[_N], vis[_N], cnt;
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].first = true;
		a[i].index = i;
		a[i].pos = l;
		
		a[i + N].first = false;
		a[i + N].index = i;
		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].first){
			a[i].left = N + a[i].index;
			a[i].right = a[i].index;
		}
		else{
			a[i].left = a[i].index;
			a[i].right = N + a[i].index;
		}
		//cerr << a[i].left << ' ' << a[i].right << ' ';
	}
	//cerr << '\n';
	a[0].right = 0;
	L(i, 1, 2 * N) nxt[a[i - 1].right] = a[i].left;
	nxt[a[2 * N].right] = 0;
	
	function<void(int)> dfs = [&](int u){
		if(vis[u]) return;
		vis[u] = true;
		sz[cnt]++;
		int v = nxt[u];
		if(!vis[v]) dfs(v);
	};
	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 4 ms 19036 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18908 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19084 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 7 ms 19292 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19304 KB Output is correct
2 Correct 8 ms 19300 KB Output is correct
3 Correct 15 ms 21092 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19804 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19560 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 29760 KB Output is correct
2 Correct 154 ms 42456 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 34776 KB Output is correct
2 Correct 245 ms 57288 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 60932 KB Output is correct
2 Correct 376 ms 65536 KB Output is correct
3 Runtime error 341 ms 65536 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 370 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 414 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -