# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
550005 | 2022-04-17T04:15:45 Z | AKiko | City Mapping (NOI18_citymapping) | C++14 | 116 ms | 8900 KB |
#include "citymapping.h" #include <bits/stdc++.h> #define pii pair<int, int> #define ll long long #define pb push_back #define ss second #define ff first using namespace std; vector<int> p(1e3 + 1); int find(int x) { if(x == p[x]) return x; return p[x] = find(p[x]); } vector<pair<ll, pii> > mst(int N) { vector<pair<ll, pii> > path, res; for(int i = 1; i <= N; i++) { for(int j = i + 1; j <= N; j++) { ll ans = get_distance(i, j); path.pb({ans, {i, j}}); } } sort(path.begin(), path.end()); iota(p.begin(), p.end(), 0); for(auto el : path) { int a = el.ss.ff, b = el.ss.ss; ll c = el.ff; int ap = find(a), bp = find(b); if(ap == bp) continue; p[bp] = ap; res.pb(el); } return res; } void find_roads(int N, int Q, int A[], int B[], int W[]) { vector<pair<ll, pii> > paths = mst(N); for(int i = 0; i < paths.size(); i++) { A[i] = paths[i].ss.ff; B[i] = paths[i].ss.ss; W[i] = paths[i].ff; } return; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 111 ms | 8760 KB | Correct: 498501 out of 500000 queries used. |
2 | Correct | 103 ms | 8812 KB | Correct: 499500 out of 500000 queries used. |
3 | Correct | 100 ms | 8768 KB | Correct: 492528 out of 500000 queries used. |
4 | Correct | 93 ms | 8768 KB | Correct: 494515 out of 500000 queries used. |
5 | Correct | 116 ms | 8732 KB | Correct: 498501 out of 500000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 111 ms | 8760 KB | Correct: 498501 out of 500000 queries used. |
2 | Correct | 103 ms | 8812 KB | Correct: 499500 out of 500000 queries used. |
3 | Correct | 100 ms | 8768 KB | Correct: 492528 out of 500000 queries used. |
4 | Correct | 93 ms | 8768 KB | Correct: 494515 out of 500000 queries used. |
5 | Correct | 116 ms | 8732 KB | Correct: 498501 out of 500000 queries used. |
6 | Correct | 85 ms | 8824 KB | Correct: 495510 out of 500000 queries used. |
7 | Correct | 92 ms | 8900 KB | Correct: 497503 out of 500000 queries used. |
8 | Correct | 86 ms | 8740 KB | Correct: 497503 out of 500000 queries used. |
9 | Correct | 81 ms | 8748 KB | Correct: 495510 out of 500000 queries used. |
10 | Correct | 99 ms | 8676 KB | Correct: 496506 out of 500000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 852 KB | Too many calls to get_distance(). |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 852 KB | Too many calls to get_distance(). |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 111 ms | 8760 KB | Correct: 498501 out of 500000 queries used. |
2 | Correct | 103 ms | 8812 KB | Correct: 499500 out of 500000 queries used. |
3 | Correct | 100 ms | 8768 KB | Correct: 492528 out of 500000 queries used. |
4 | Correct | 93 ms | 8768 KB | Correct: 494515 out of 500000 queries used. |
5 | Correct | 116 ms | 8732 KB | Correct: 498501 out of 500000 queries used. |
6 | Correct | 85 ms | 8824 KB | Correct: 495510 out of 500000 queries used. |
7 | Correct | 92 ms | 8900 KB | Correct: 497503 out of 500000 queries used. |
8 | Correct | 86 ms | 8740 KB | Correct: 497503 out of 500000 queries used. |
9 | Correct | 81 ms | 8748 KB | Correct: 495510 out of 500000 queries used. |
10 | Correct | 99 ms | 8676 KB | Correct: 496506 out of 500000 queries used. |
11 | Incorrect | 3 ms | 852 KB | Too many calls to get_distance(). |
12 | Halted | 0 ms | 0 KB | - |