# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
147015 | 2019-08-27T06:09:24 Z | jun6873 | City Mapping (NOI18_citymapping) | C++11 | 8 ms | 1272 KB |
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; // long long get_distance(int X, int Y); using lint = long long; const lint inf = 1e18; int n, t=0, *A, *B, *W; void f(vector<int> v) { int x = v[0], y = v[0], z = v[0]; vector<lint> a, b, c, d; lint mxd; mxd = 0; for (int i : v) { lint d = get_distance(x, i); if (d > mxd) mxd = d, y = i; a.push_back(d); } mxd = 0; for (int i : v) { lint d = get_distance(y, i); if (d > mxd) mxd = d, z = i; b.push_back(d); } for (int i : v) c.push_back(get_distance(z, i)); for (int i=0; i<v.size(); i++) d.push_back(b[i] - c[i]); vector<int> ind; for (int i=0; i<v.size(); i++) ind.push_back(i); sort(ind.begin(), ind.end(), [&](int x, int y) { return (d[x] < d[y]) or (d[x] == d[y] and b[x] < b[y]); }); vector<lint> tb, td; vector<int> tv; for (int i=0; i<b.size(); i++) tb.push_back(b[ind[i]]); b = tb; for (int i=0; i<d.size(); i++) td.push_back(d[ind[i]]); d = td; for (int i=0; i<v.size(); i++) tv.push_back(v[ind[i]]); v = tv; for (int i=0; i<v.size(); ) { vector<int> u; int k = i; while (i+1<v.size() and d[i] == d[i+1]) { u.push_back(i+1); i++; } i++; if (i < v.size()) { A[t] = v[k]; B[t] = v[i]; W[t] = b[i] - b[k]; t++; } if (!u.empty()) { A[t] = v[k]; B[t] = v[u[0]]; W[t] = b[u[0]] - b[k]; t++; } if (u.size() >= 2) { for (int &i : u) i = v[i]; f(u); } } } void find_roads(int N, int Q, int a[], int b[], int w[]) { n = N; A = a; B = b; W = w; vector<int> v; for (int i=1; i<=n; i++) v.push_back(i); f(v); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Correct: 2997 out of 500000 queries used. |
2 | Correct | 3 ms | 504 KB | Correct: 3000 out of 500000 queries used. |
3 | Correct | 4 ms | 504 KB | Correct: 8529 out of 500000 queries used. |
4 | Correct | 4 ms | 504 KB | Correct: 9753 out of 500000 queries used. |
5 | Correct | 5 ms | 940 KB | Correct: 16638 out of 500000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Correct: 2997 out of 500000 queries used. |
2 | Correct | 3 ms | 504 KB | Correct: 3000 out of 500000 queries used. |
3 | Correct | 4 ms | 504 KB | Correct: 8529 out of 500000 queries used. |
4 | Correct | 4 ms | 504 KB | Correct: 9753 out of 500000 queries used. |
5 | Correct | 5 ms | 940 KB | Correct: 16638 out of 500000 queries used. |
6 | Correct | 3 ms | 632 KB | Correct: 2988 out of 500000 queries used. |
7 | Correct | 8 ms | 1272 KB | Correct: 29373 out of 500000 queries used. |
8 | Correct | 4 ms | 504 KB | Correct: 8694 out of 500000 queries used. |
9 | Correct | 4 ms | 504 KB | Correct: 10266 out of 500000 queries used. |
10 | Correct | 4 ms | 632 KB | Correct: 9960 out of 500000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Correct: 2973 out of 12000 queries used. |
2 | Correct | 3 ms | 504 KB | Correct: 2979 out of 12000 queries used. |
3 | Correct | 3 ms | 504 KB | Correct: 3000 out of 12000 queries used. |
4 | Correct | 3 ms | 504 KB | Correct: 2979 out of 12000 queries used. |
5 | Correct | 3 ms | 504 KB | Correct: 2973 out of 12000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Correct: 2973 out of 12000 queries used. |
2 | Correct | 3 ms | 504 KB | Correct: 2979 out of 12000 queries used. |
3 | Correct | 3 ms | 504 KB | Correct: 3000 out of 12000 queries used. |
4 | Correct | 3 ms | 504 KB | Correct: 2979 out of 12000 queries used. |
5 | Correct | 3 ms | 504 KB | Correct: 2973 out of 12000 queries used. |
6 | Correct | 3 ms | 504 KB | Correct: 2994 out of 12000 queries used. |
7 | Correct | 3 ms | 504 KB | Correct: 2988 out of 12000 queries used. |
8 | Correct | 3 ms | 504 KB | Correct: 3000 out of 12000 queries used. |
9 | Correct | 4 ms | 504 KB | Correct: 2991 out of 12000 queries used. |
10 | Correct | 3 ms | 504 KB | Correct: 2982 out of 12000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Correct: 2997 out of 500000 queries used. |
2 | Correct | 3 ms | 504 KB | Correct: 3000 out of 500000 queries used. |
3 | Correct | 4 ms | 504 KB | Correct: 8529 out of 500000 queries used. |
4 | Correct | 4 ms | 504 KB | Correct: 9753 out of 500000 queries used. |
5 | Correct | 5 ms | 940 KB | Correct: 16638 out of 500000 queries used. |
6 | Correct | 3 ms | 632 KB | Correct: 2988 out of 500000 queries used. |
7 | Correct | 8 ms | 1272 KB | Correct: 29373 out of 500000 queries used. |
8 | Correct | 4 ms | 504 KB | Correct: 8694 out of 500000 queries used. |
9 | Correct | 4 ms | 504 KB | Correct: 10266 out of 500000 queries used. |
10 | Correct | 4 ms | 632 KB | Correct: 9960 out of 500000 queries used. |
11 | Correct | 3 ms | 504 KB | Correct: 2973 out of 12000 queries used. |
12 | Correct | 3 ms | 504 KB | Correct: 2979 out of 12000 queries used. |
13 | Correct | 3 ms | 504 KB | Correct: 3000 out of 12000 queries used. |
14 | Correct | 3 ms | 504 KB | Correct: 2979 out of 12000 queries used. |
15 | Correct | 3 ms | 504 KB | Correct: 2973 out of 12000 queries used. |
16 | Correct | 3 ms | 504 KB | Correct: 2994 out of 12000 queries used. |
17 | Correct | 3 ms | 504 KB | Correct: 2988 out of 12000 queries used. |
18 | Correct | 3 ms | 504 KB | Correct: 3000 out of 12000 queries used. |
19 | Correct | 4 ms | 504 KB | Correct: 2991 out of 12000 queries used. |
20 | Correct | 3 ms | 504 KB | Correct: 2982 out of 12000 queries used. |
21 | Correct | 4 ms | 504 KB | Correct: 2988 out of 25000 queries used. |
22 | Correct | 4 ms | 632 KB | Correct: 7893 out of 25000 queries used. |
23 | Correct | 3 ms | 508 KB | Correct: 3099 out of 25000 queries used. |
24 | Correct | 4 ms | 632 KB | Correct: 5172 out of 25000 queries used. |
25 | Correct | 4 ms | 632 KB | Correct: 8739 out of 25000 queries used. |
26 | Correct | 4 ms | 504 KB | Correct: 8379 out of 25000 queries used. |
27 | Correct | 4 ms | 504 KB | Correct: 8517 out of 25000 queries used. |
28 | Correct | 4 ms | 632 KB | Correct: 8907 out of 25000 queries used. |
29 | Correct | 4 ms | 632 KB | Correct: 9282 out of 25000 queries used. |
30 | Correct | 4 ms | 632 KB | Correct: 9765 out of 25000 queries used. |
31 | Correct | 4 ms | 504 KB | Correct: 9801 out of 25000 queries used. |
32 | Correct | 3 ms | 632 KB | Correct: 2985 out of 25000 queries used. |
33 | Correct | 4 ms | 504 KB | Correct: 9750 out of 25000 queries used. |
34 | Correct | 4 ms | 552 KB | Correct: 9741 out of 25000 queries used. |
35 | Correct | 4 ms | 504 KB | Correct: 9792 out of 25000 queries used. |
36 | Correct | 5 ms | 508 KB | Correct: 9843 out of 25000 queries used. |
37 | Correct | 4 ms | 504 KB | Correct: 9696 out of 25000 queries used. |
38 | Correct | 4 ms | 504 KB | Correct: 9900 out of 25000 queries used. |
39 | Correct | 4 ms | 504 KB | Correct: 9741 out of 25000 queries used. |
40 | Correct | 4 ms | 504 KB | Correct: 9822 out of 25000 queries used. |
41 | Correct | 4 ms | 504 KB | Correct: 9765 out of 25000 queries used. |
42 | Correct | 4 ms | 508 KB | Correct: 9801 out of 25000 queries used. |
43 | Correct | 3 ms | 632 KB | Correct: 2994 out of 25000 queries used. |
44 | Correct | 4 ms | 504 KB | Correct: 9684 out of 25000 queries used. |
45 | Correct | 4 ms | 504 KB | Correct: 9672 out of 25000 queries used. |
46 | Correct | 4 ms | 504 KB | Correct: 9684 out of 25000 queries used. |
47 | Correct | 4 ms | 504 KB | Correct: 9786 out of 25000 queries used. |
48 | Correct | 4 ms | 504 KB | Correct: 9870 out of 25000 queries used. |
49 | Correct | 4 ms | 504 KB | Correct: 9810 out of 25000 queries used. |
50 | Correct | 4 ms | 504 KB | Correct: 9777 out of 25000 queries used. |
51 | Correct | 4 ms | 504 KB | Correct: 9798 out of 25000 queries used. |
52 | Correct | 4 ms | 504 KB | Correct: 9747 out of 25000 queries used. |
53 | Correct | 4 ms | 504 KB | Correct: 10245 out of 25000 queries used. |
54 | Incorrect | 7 ms | 1272 KB | Too many calls to get_distance(). |
55 | Halted | 0 ms | 0 KB | - |