# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
239216 | 2020-06-14T20:13:29 Z | osaaateiasavtnl | Teleporters (IOI08_teleporters) | C++14 | 1000 ms | 65540 KB |
#include<bits/stdc++.h> using namespace std; #define int long long #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcountll #define ll long long #define mp make_pair #define f first #define s second #define Time (double)clock()/CLOCKS_PER_SEC const int INF = 1e9+7; int get(vector <ii> a) { /* cout << "get : " << endl; for (auto e : a) cout << e.f << ' ' << e.s << endl; cout << endl; */ int n = a.size(); map <int, int> who; vector <int> c = {0, INF}; for (int i = 0; i < n; ++i) { c.app(a[i].f); c.app(a[i].s); who[a[i].f] = i; who[a[i].s] = i; } sort(all(c)); int sz = c.size() - 1; vector <int> to(sz, -1); for (int i = 0; i + 2 < c.size(); ++i) { int u = who[c[i+1]]; int x = a[u].f^a[u].s^c[i+1]; to[i] = lower_bound(all(c), x) - c.begin(); } int ans = 0; vector <int> len; vector <bool> used(sz); for (int i = 0; i < sz; ++i) { if (!used[i]) { int u = i; int l = 0; while (u != -1 && !used[u]) { used[u] = 1; ++l; u = to[u]; } if (u == -1) { return l - 1; } } } return -1; } int n, m; int solve(vector <ii> a, int h) { /* cout << "solve : " << endl; for (auto e : a) cout << e.f << ' ' << e.s << endl; cout << endl; */ if (h == m) return get(a); vector <int> c; for (auto e : a) { c.app(e.f); c.app(e.s); } int ans = 0; c.app(0); c.app(c.back()+1); sort(all(c)); for (int l = 0; l + 1 < c.size(); ++l) { for (int r = l; r + 1 < c.size(); ++r) { int lx = c[l] + 1; int rx = c[r] + 2; vector <ii> b; for (auto e : a) { if (e.f >= c[l + 1]) e.f += 2; if (e.f >= c[r + 1]) e.f += 2; if (e.s >= c[l + 1]) e.s += 2; if (e.s >= c[r + 1]) e.s += 2; b.app(e); } /* cout << "add " << lx << ' ' << rx << endl; cout << c[r] << endl; */ b.app(mp(lx, rx)); ans = max(ans, solve(b, h + 1)); } } return ans; } signed main() { #ifdef HOME freopen("input.txt", "r", stdin); #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> n >> m; vector <ii> a(n); for (int i = 0; i < n; ++i) { int l, r; cin >> l >> r; a[i] = mp(l, r); } cout << solve(a, 0) << endl; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 384 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 533 ms | 416 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1090 ms | 384 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1093 ms | 384 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1095 ms | 2048 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1090 ms | 1408 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1088 ms | 512 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1086 ms | 1024 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1091 ms | 3840 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1063 ms | 7168 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 203 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 215 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 256 ms | 65536 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 276 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 307 ms | 65536 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 341 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 320 ms | 65536 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 421 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 465 ms | 65540 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |