# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
483119 | 2021-10-27T18:03:58 Z | blue | Teleporters (IOI08_teleporters) | C++17 | 0 ms | 0 KB |
#include <iostream> #include <vector> using namespace std; const int mx = 2'000'000; int* nxt; int main() { int N, M; cin >> N >> M; vector<int> ep(1+mx+1, 0); for(int i = 1; i <= N; i++) { int W, E; cin >> W >> E; ep[W] = +i; ep[E] = -i; } nxt = new int[mx + 100'000]; nxt = nxt + mx/2 + 50'000; int lst = 0; for(int p = mx; p >= 0; p--) { if(ep[p] == 0) continue; // cerr << "x = " << p << ' ' << ep[p] << '\n'; nxt[ep[p]] = lst; lst = ep[p]; } nxt[0] = 0; // for(int i = 1; i <= N; i++) cerr << nxt[+i] << ' ' << nxt[-i] << '\n'; vector<int> nw; bool* visit = new bool[mx + 100'000] + (mx/2 + 50'000); for(int i = 1; i <= N; i++) visit[i] = visit[-i] = 0; for(int p = 1; p <= mx; p++) { if(ep[p] == 0) continue; if(visit[-ep[p]]) continue; nw.push_back(0); for(int u = -ep[p]; u != 0 && !visit[u]; u = -nxt[u]) { visit[u] = 1; nw[int(nw.size()-1)]++; } } reverse(nw.begin(), nw.end()); int mn = nw.back(); nw.pop_back(); // cerr << "mn = " << mn << '\n'; // // for(int f: nw) cerr << f << ' '; // cerr << '\n'; int ans = mn; sort(nw.begin(), nw.end()); while(1) { if(M <= 0) break; if(!nw.empty()) { ans += nw.back(); nw.pop_back(); } ans += 2; M--; } cout << ans << '\n'; // for(int q: nw) cerr << q << ' '; // cerr << '\n'; }