Submission #1381124
Source Code Expand
#include <bits/stdc++.h> using namespace std; struct Edge { int from, to; Edge(int f, int t) : from(f), to(t) {} }; using Edges = vector<Edge>; using Graph = vector<Edges>; vector<int> tarjan(const Graph& g) { int n = g.size(), idx = 0, k = 0, s = 0; vector<int>ord(n, -1), low(n), onS(n), cmp(n), stk(n); function<void(int)> dfs = [&](int v) { ord[v] = low[v] = idx++; stk[s++] = v; onS[v] = true; for (auto &e : g[v]) { int w = e.to; if (ord[w] == -1) { dfs(w); low[v] = min(low[v], low[w]); } else if (onS[w]) { low[v] = min(low[v], ord[w]); } } if (low[v] == ord[v]) { while (1) { int w = stk[--s]; onS[w] = false; cmp[w] = k; if (w == v)break; } ++k; } }; for (int v = 0; v<n; ++v) if (ord[v] == -1)dfs(v); return cmp; } int main() { int N; cin >> N; vector<int> x(N), y(N); for (int i = 0; i < N; i++) { cin >> x[i] >> y[i]; } int l = 0, r = 1e9 + 1; while (l + 1 < r) { int c = l + (r - l) / 2; Graph g(N * 2); for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if (abs(x[i] - x[j]) < c) { g[i].emplace_back(i, N + j); g[j].emplace_back(j, N + i); } if (abs(x[i] - y[j]) < c) { g[i].emplace_back(i, j); g[N + j].emplace_back(N + j, N + i); } if (abs(y[i] - x[j]) < c) { g[N + i].emplace_back(N + i, N + j); g[j].emplace_back(j, i); } if (abs(y[i] - y[j]) < c) { g[N + i].emplace_back(N + i, j); g[N + j].emplace_back(N + j, i); } } } auto v = tarjan(g); bool can = true; for (int i = 0; i < N; i++) { if (v[i] == v[i + N]) { can = false; } } if (can) { l = c; } else { r = c; } } cout << l << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Flags |
User | kazuma |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1833 Byte |
Status | TLE |
Exec Time | 5495 ms |
Memory | 7168 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1200 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 1 ms | 256 KB |
00_example_02.txt | AC | 1 ms | 256 KB |
00_example_03.txt | AC | 2 ms | 256 KB |
01.txt | AC | 71 ms | 6912 KB |
02.txt | AC | 15 ms | 1664 KB |
03.txt | AC | 3 ms | 384 KB |
04.txt | AC | 4 ms | 384 KB |
05.txt | AC | 4 ms | 580 KB |
06.txt | TLE | 5480 ms | -1567396 KB |
07.txt | TLE | 5475 ms | -1579628 KB |
08.txt | TLE | 5482 ms | -1568924 KB |
09.txt | AC | 40 ms | 7168 KB |
10.txt | AC | 9 ms | 1536 KB |
11.txt | AC | 2 ms | 384 KB |
12.txt | AC | 3 ms | 384 KB |
13.txt | AC | 3 ms | 512 KB |
14.txt | TLE | 5461 ms | -1717324 KB |
15.txt | TLE | 5465 ms | -1737708 KB |
16.txt | TLE | 5474 ms | -1724788 KB |
17.txt | AC | 73 ms | 6912 KB |
18.txt | AC | 16 ms | 1280 KB |
19.txt | TLE | 5475 ms | -1829932 KB |
20.txt | TLE | 5463 ms | -1832952 KB |
21.txt | TLE | 5495 ms | -1316140 KB |
22.txt | TLE | 5492 ms | -1310892 KB |
23.txt | TLE | 5491 ms | -1321260 KB |
24.txt | TLE | 5486 ms | -1324716 KB |
25.txt | TLE | 5489 ms | -1311788 KB |
26.txt | TLE | 5461 ms | -1763816 KB |
27.txt | AC | 1 ms | 256 KB |