Submission #442900

#TimeUsernameProblemLanguageResultExecution timeMemory
442900jesus_coconutTeleporters (IOI08_teleporters)C++17
95 / 100
690 ms65540 KiB
#include <bits/stdc++.h> #define all(a) begin(a), end(a) #define S second #define F first using namespace std; int const N = 2000100; void countsort(vector<int> &v) { array<bool, N> tmp{}; for (auto a : v) { assert(a < N); tmp[a] = true; } v.clear(); for (int i = 0; i < N; ++i) { if (tmp[i]) { v.push_back(i); } } } void cs2(vector<int> &v) { array<int, N> tmp{}; for (auto a : v) { assert(a < N); tmp[a]++; } v.clear(); for (int i = N - 1; i > 0; --i) { while (tmp[i] > 0) { v.push_back(i); tmp[i]--; } } } void cc(vector<pair<int, int>> &v) { vector<int> tmp; tmp.reserve(v.size()); for (auto &[a, b] : v) { tmp.push_back(a); tmp.push_back(b); } countsort(tmp); for (auto &[a, b] : v) { a = lower_bound(all(tmp), a) - begin(tmp); b = lower_bound(all(tmp), b) - begin(tmp); } } void countsort(vector<pair<int, int>> &v) { array<int, N> tmp{}; tmp.fill(-1); for (auto &[a, b] : v) { assert(a < N); tmp[a] = b; } v.clear(); for (int i = 0; i < N; ++i) { if (tmp[i] != -1) { v.emplace_back(i, tmp[i]); } } } vector<bool> bio; vector<int> len; vector<int> nxt; void findcyc(int ver, int l, int tar) { bio[ver] = true; if (ver == tar) { len.push_back(l); return; } findcyc(nxt[ver], l + 1, tar); } void solve() { int n, m; cin >> n >> m; bio.resize(2 * n); nxt.resize(2 * n); len.reserve(n); vector<pair<int, int>> v; v.reserve(2 * n); for (int i = 0; i < n; ++i) { int a, b; cin >> a >> b; v.emplace_back(a, b); v.emplace_back(b, a); } countsort(v); cc(v); for (int i = 0; i < 2 * n; ++i) { nxt[i] = (v[i].S + 1) % (2 * n); } for (int i = 0; i < 2 * n; ++i) { if (!bio[nxt[i]]) { findcyc(nxt[i], 1, i); } } int ans = len[0]; len[0] = 0; cs2(len); int i = 0; for (; i < m && i < len.size(); ++i) { if (len[i] > 0) { ans += len[i] + 2; } else break; } int lft = m - i; if (lft % 2 == 1) { lft--; ans++; } ans += 2 * lft; cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }

Compilation message (stderr)

teleporters.cpp: In function 'void solve()':
teleporters.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (; i < m && i < len.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...