제출 #1029566

#제출 시각아이디문제언어결과실행 시간메모리
1029566kunzaZa183Teleporters (IOI08_teleporters)C++17
65 / 100
732 ms65536 KiB
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int n, m; cin >> n >> m; map<int, int> mii; vector<int> tp(2e6 + 1); for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; mii[a] = b, mii[b] = a; tp[a] = b, tp[b] = a; } vector<pair<int, int>> vpii; vpii.emplace_back(0, mii.begin()->first); for (auto it = mii.begin(); it != mii.end(); it++) { auto it2 = it; it2++; int a = it->first, b; if (it2 == mii.end()) b = 3e6; else b = it2->first; vpii.emplace_back(a, b); } vector<bool> vb; vb.resize(vpii.size()); vector<int> cyc; int special; for (int i = 0; i < vb.size(); i++) if (!vb[i]) { // cout << "I = " << i << '\n'; int cy = 0; function<void(int)> dfs; dfs = [&](int cur) { // cout << cur << "\n"; if (vb[cur]) { cyc.push_back(cy); return; } vb[cur] = 1; cy++; if (vpii[cur].second == 3e6) { special = cy - 1; return; } dfs(lower_bound(vpii.begin(), vpii.end(), make_pair(tp[vpii[cur].second], -1)) - vpii.begin()); }; dfs(i); } // for (auto a : cyc) cout << a << ' '; // cout << "\n"; sort(cyc.begin(), cyc.end(), greater<int>()); if (m >= cyc.size()) { cout << (n + m) * 2 << "\n"; return 0; cout << special + accumulate(cyc.begin(), cyc.end(), 0) + m * 2 << "\n"; } else cout << special + accumulate(cyc.begin(), cyc.begin() + m, 0) + 2 * m << "\n"; }

컴파일 시 표준 에러 (stderr) 메시지

teleporters.cpp: In function 'int main()':
teleporters.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (int i = 0; i < vb.size(); i++)
      |                   ~~^~~~~~~~~~~
teleporters.cpp:58:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   if (m >= cyc.size()) {
      |       ~~^~~~~~~~~~~~~
#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...