# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
95497 | 2019-02-01T15:31:48 Z | tincamatei | 도시들 (IOI15_towns) | C++14 | 7 ms | 1144 KB |
#include "towns.h" #include <bits/stdc++.h> using namespace std; set<pair<int, int> > diameter; typedef set<pair<int, int> >::iterator seti; typedef set<pair<int, int> >::reverse_iterator rseti; vector<pair<int, int> > eraseQueue; void lazyErase(pair<int, int> x) { eraseQueue.push_back(x); } void runEraseQueue() { for(int i = 0; i < eraseQueue.size(); ++i) diameter.erase(eraseQueue[i]); eraseQueue.clear(); } int hubDistance(int N, int sub) { int c1, c2, diam; c1 = 0; c2 = 1; diam = getDistance(0, 1); diameter.insert(make_pair(0, 1)); diameter.insert(make_pair(diam, 1)); for(int i = 2; i < N; ++i) { int x, y; int dc1c, dc2c, dic; x = getDistance(c1, i); y = getDistance(c2, i); dic = (x + y - diam) / 2; dc1c = x - dic; dc2c = y - dic; if(dic + dc1c > diam) { rseti a = diameter.rbegin(); int meeting = dc1c; pair<int, int> sub = make_pair(meeting, 0); while(a->first >= meeting) { sub.second += a->second; lazyErase(*a); a++; } runEraseQueue(); diameter.insert(sub); diameter.insert(make_pair(diam, 1)); c2 = i; diam = dic + dc1c; } else if(dic + dc2c > diam) { seti a = diameter.begin(); int meeting = dc1c; pair<int, int> sub = make_pair(dic, 0); set<pair<int, int> > tmp; while(a->first <= meeting) { sub.second += a->second; a++; } while(a != diameter.end()) { tmp.insert(make_pair(a->first + dic - dc1c, a->second)); a++; } diameter = tmp; diameter.insert(sub); diameter.insert(make_pair(0, 1)); c1 = i; diam = dic + dc2c; } else { seti it; it = diameter.lower_bound(make_pair(dc1c, -1)); pair<int, int> x; x = *it; diameter.erase(it); if(x.first == dc1c) x.second++; else diameter.insert(make_pair(dc1c, 1)); diameter.insert(x); } /*for(seti it = diameter.begin(); it != diameter.end(); it++) printf("(%d %d)\n", it->first, it->second); printf("\n");*/ } int rez = 1000000000; for(seti it = diameter.begin(); it != diameter.end(); it++) rez = min(rez, max(it->first, diam - it->first)); return rez; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 7 ms | 1144 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 888 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 6 ms | 888 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 760 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 760 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 760 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |