oj.uz

Submission #910635

# Submission time Handle Problem Language Result Execution time Memory
910635 2024-01-18T06:34:14 Z josanneo22 Teleporters (IOI08_teleporters) C++17
100 / 100
 403 ms 39636 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)
 
namespace fast {
#pragma GCC optimize(Ofast)
#pragma GCC optimization (unroll-loops)
#pragma GCC target(avx,avx2,fma)
#pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
}
using namespace fast;
 
inline string read_string() {
	char ch = getchar(); string st1 = "";
	while (!((ch >= 'A') && (ch <= 'Z'))) ch = getchar();
	while ((ch >= 'A') && (ch <= 'Z'))  st1 += ch, ch = getchar();
	return st1;
}
char buf[1 << 23], * p1 = buf, * p2 = buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template<typename T> inline void re(T & x) { x = 0; T f = 1; char ch = getchar();  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * (1 << 1) + x * (1 << 3) + (ch - 48); ch = getchar(); } x *= f; }
template<typename x, typename... y>void re(x & a, y&... b) { re(a); re(b...); }
template<typename T> inline void ps(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9)  ps(x / 10); putchar(x % 10 + '0'); }
template<typename x, typename... y>void ps(x & a, y&... b) { ps(a); putchar(' '); ps(b...); }
#define sp putchar(' ')
#define nl putchar('\n')
 
constexpr int _N = 2E6 + 5;
struct node {
	int index, pos;
}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;
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';
}

Compilation message

teleporters.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization (unroll-loops)
      | 
teleporters.cpp:9:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
    9 | #pragma GCC optimize(Ofast)
      |                      ^~~~~
teleporters.cpp:11:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
   11 | #pragma GCC target(avx,avx2,fma)
      |                    ^~~
teleporters.cpp:12:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
   12 | #pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
      |                    ^~~
teleporters.cpp:32:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
teleporters.cpp:39:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   39 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
teleporters.cpp:41:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   41 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
teleporters.cpp:55:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   55 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
teleporters.cpp:61:27: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   61 | inline string read_string() {
      |                           ^
teleporters.cpp:61:27: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teleporters.cpp:61:27: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teleporters.cpp:61:27: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teleporters.cpp:69:42: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   69 | template<typename T> inline void re(T & x) { x = 0; T f = 1; char ch = getchar();  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * (1 << 1) + x * (1 << 3) + (ch - 48); ch = getchar(); } x *= f; }
      |                                          ^
teleporters.cpp:69:42: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teleporters.cpp:69:42: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teleporters.cpp:69:42: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teleporters.cpp:70:58: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   70 | template<typename x, typename... y>void re(x & a, y&... b) { re(a); re(b...); }
      |                                                          ^
teleporters.cpp:70:58: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teleporters.cpp:70:58: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teleporters.cpp:70:58: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teleporters.cpp:71:40: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   71 | template<typename T> inline void ps(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9)  ps(x / 10); putchar(x % 10 + '0'); }
      |                                        ^
teleporters.cpp:71:40: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teleporters.cpp:71:40: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teleporters.cpp:71:40: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teleporters.cpp:72:58: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   72 | template<typename x, typename... y>void ps(x & a, y&... b) { ps(a); putchar(' '); ps(b...); }
      |                                                          ^
teleporters.cpp:72:58: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teleporters.cpp:72:58: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teleporters.cpp:72:58: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teleporters.cpp:80:45: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   80 | inline bool cmp(const node& A, const node& B) { return A.pos < B.pos; }
      |                                             ^
teleporters.cpp:80:45: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teleporters.cpp:80:45: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teleporters.cpp:80:45: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teleporters.cpp:82:15: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   82 | void dfs(int u) {
      |               ^
teleporters.cpp:82:15: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teleporters.cpp:82:15: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teleporters.cpp:82:15: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
teleporters.cpp:88:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   88 | int main() {
      |          ^
teleporters.cpp:88:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
teleporters.cpp:88:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
teleporters.cpp:88:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19092 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 19292 KB Output is correct

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 23120 KB Output is correct
2 Correct 117 ms 25168 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 22976 KB Output is correct
2 Correct 171 ms 29140 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 33364 KB Output is correct
2 Correct 293 ms 37456 KB Output is correct
3 Correct 309 ms 37336 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 39512 KB Output is correct
2 Correct 376 ms 39636 KB Output is correct
3 Correct 392 ms 39508 KB Output is correct
4 Correct 403 ms 39508 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 39368 KB Output is correct
2 Correct 400 ms 39508 KB Output is correct
3 Correct 341 ms 39584 KB Output is correct
4 Correct 385 ms 39600 KB Output is correct