Submission #58255

#TimeUsernameProblemLanguageResultExecution timeMemory
58255memikakizakiTeleporters (IOI08_teleporters)C++14
65 / 100
1063 ms66560 KiB
#include <bits/stdc++.h> #define long long long using namespace std; const int N = 1e6+1, INF = 1e9; int n, m, lf[N], rg[N], nxt[N]; vector<int> vals, cycles; bool mark[N]; long ans; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 0; i < n; i++) { cin >> lf[i] >> rg[i]; vals.push_back(lf[i]); vals.push_back(rg[i]); } vals.push_back(INF); sort(vals.begin(), vals.end()); for(int i = 0; i < n; i++) { lf[i] = lower_bound(vals.begin(), vals.end(), lf[i]) - vals.begin(); rg[i] = lower_bound(vals.begin(), vals.end(), rg[i]) - vals.begin(); nxt[lf[i]] = rg[i]+1; nxt[rg[i]] = lf[i]+1; } nxt[vals.size()-1] = INF; for(int i = 0; i < vals.size(); i++) if(!mark[i]) { int curr = i, sz = 0; bool cycle = false; while(curr != INF) { if(mark[curr]) { cycle = true; break; } ++sz; mark[curr] = true; curr = nxt[curr]; } if(cycle) cycles.push_back(sz); else ans = sz-1; } sort(cycles.begin(), cycles.end(), greater<int>()); for(int i = 0; i < min((int) cycles.size(), m); i++) ans += cycles[i] + 2; if(m > cycles.size()) { m -= cycles.size(); ans += (m - (m & 1)) << 1 + (m & 1); } cout << ans; }

Compilation message (stderr)

teleporters.cpp: In function 'int main()':
teleporters.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vals.size(); i++) if(!mark[i]) {
                 ~~^~~~~~~~~~~~~
teleporters.cpp:45:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(m > cycles.size()) {
     ~~^~~~~~~~~~~~~~~
teleporters.cpp:47:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   ans += (m - (m & 1)) << 1 + (m & 1);
                           ~~^~~~~~~~~
#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...