Submission #1239371

#TimeUsernameProblemLanguageResultExecution timeMemory
1239371lanaskaricaTeleporters (IOI08_teleporters)C++20
25 / 100
460 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair <int, int> #define fi first #define se second const int MAXN = 2e6 + 5; int bio[MAXN]; vector <pii> vtr; vector <int> v[MAXN], c; int dfs(int a) { int zb = 1; for (auto e : v[a]) { if (bio[e] != 0) continue; bio[e] = 1; zb += dfs(e); } return zb; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, a, b; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a >> b; vtr.push_back({a, b}); vtr.push_back({b, a}); } sort(vtr.begin(), vtr.end()); int p = 0; for (int i = 0; i < 2 * n; i++) { v[p].push_back(vtr[i].se); //cout << p << " " << vtr[i].se << endl; p = vtr[i].fi; } bio[0] = 1; int rj = dfs(0); //cout << rj << endl; for (int i = 0; i < 2 * n; i++) { if (bio[vtr[i].fi] != 0) continue; bio[vtr[i].fi] = 1; int br = dfs(vtr[i].fi); c.push_back(br); //cout << vtr[i].fi << " " << br << endl; } sort(c.rbegin(), c.rend()); for (int i = 0; i < min(m, (int)c.size()); i++) {rj += c[i] + 2; m--;} if (m == 0) {cout << rj - 1 << "\n"; return 0;} for (int i = 0; i < m; i++) { if (i % 2 == 0) rj++; else rj += 3; } cout << rj - 1 << "\n"; return 0; }
#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...