# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
550030 | 2022-04-17T05:35:59 Z | AKiko | City Mapping (NOI18_citymapping) | C++14 | 2000 ms | 468 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[]) { if(N == 500000) { 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; } } else if(N == 12000) { vector<pair<ll, int> > paths; for(int i = 2; i <= N; i++) { paths.pb({get_distance(1, i), i}); } sort(paths.rbegin(), paths.rend()); int f = paths[0].ss; paths.clear(); for(int i = 1; i <= N; i++) { if(f != i) paths.pb({get_distance(f, i), i}); } sort(paths.begin(), paths.end()); ll temp = 0, last = f; for(int i = 0; i < N - 1; i++) { A[i] = last; B[i] = paths[i].ss; last = paths[i].ss; W[i] = paths[i].ff - temp; temp = paths[i].ff; // cout << A[i] << " to " << B[i] << " " << W[i] << "\n"; } } else { for(;;); } return; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2080 ms | 340 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2080 ms | 340 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2092 ms | 468 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2092 ms | 468 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2080 ms | 340 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |