Submission #963864

#TimeUsernameProblemLanguageResultExecution timeMemory
963864guechotjrhhCity Mapping (NOI18_citymapping)C++14
25 / 100
4 ms856 KiB
#include "citymapping.h" #include<vector> #include<algorithm> #include<random> using namespace std; #define ll long long #define pi pair<ll,ll> #define x first #define y second random_device rd; mt19937 g(rd()); int* a, * b, * w; int t = 0; void rec(vector<int>& v) { int n = v.size(); if (n == 1) return; shuffle(v.begin(), v.end(), g); int u1 = v[0], u2 = v[1]; vector<ll> d1(n, 0), d2(n, 0); vector<int> v1, v2; int t1 = 1, t2 = 0; for (int i = 0; i < n; i++) { if (v[i] != u1) d1[i] = get_distance(v[i], u1); if (v[i] != u2) d2[i] = get_distance(v[i], u2); if (d1[i] < d2[i]) { v1.push_back(v[i]); if (d2[i] < d2[t2]) t2 = i; } else { v2.push_back(v[i]); if (d1[i] < d1[t1]) t1 = i; } } a[t] = v[t1]; b[t] = v[t2]; w[t] = d1[t1] - d1[t2]; t++; rec(v1); rec(v2); } void find_roads(int N, int Q, int A[], int B[], int W[]) { a = A; b = B; w = W; /*ll u = 0, mi = 1; for (int i = 2; i <= N; i++) { ll x = get_distance(1, i); if (x > u) { u = x; mi = i; } } vector<pi> vec; for (int i = 1; i <= N; i++) { if (i != mi) vec.push_back({ get_distance(mi,i),i }); } sort(vec.begin(), vec.end()); A[0] = mi; B[0] = vec[0].y; W[0] = vec[0].x; for (int i = 1; i < N-1; i++) { A[i] = vec[i].y; B[i] = vec[i - 1].y; W[i] = vec[i].x - vec[i - 1].x; }*/ vector<int> v(N); for (int i = 1; i <= N; i++) v[i - 1] = i; rec(v); return; } /* 5 500000 1 1 4 8 4 2 1 4 3 7 3 5 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...