Submission #1226497

#TimeUsernameProblemLanguageResultExecution timeMemory
1226497chaeryeongCity Mapping (NOI18_citymapping)C++20
32 / 100
33 ms584 KiB
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; void find_roads(int n, int q, int A[], int B[], int W[]) { if (q == 500000) { int cnt = 0; vector <ll> c(n + 1, 0); for (int i = 1; i <= n; i++) { c[i] = get_distance(1, i); } int par[n + 1] = {}; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { ll x = get_distance(i, j); if (c[i] + x == c[j] || c[j] + x == c[i]) { if (c[i] < c[j]) { if (par[j] == 0 || c[i] > c[par[j]]) { par[j] = i; } } else { if (par[i] == 0 || c[j] > c[par[i]]) { par[i] = j; } } } } } for (int i = 2; i <= n; i++) { assert(par[i] != 0); int idx = cnt++; A[idx] = par[i]; B[idx] = i; W[idx] = c[i] - c[par[i]]; } return; } vector <int> ii(n, 0); vector <ll> c(n + 1, 0); for (int i = 1; i <= n; i++) { c[i] = get_distance(1, i); } iota(ii.begin(), ii.end(), 1); stable_sort(ii.begin(), ii.end(), [&] (auto x, auto y) { return c[x] < c[y]; }); if (q == 12000) { vector <int> a[2] = {{1, ii[1]}, {1}}; int cur = 0; for (int i = 2; i < n; i++) { if (c[ii[i - 1]] + get_distance(ii[i - 1], ii[i]) != c[ii[i]]) { cur ^= 1; } a[cur].push_back(ii[i]); } int cnt = 0; for (int j = 0; j + 1 < (int)a[0].size(); j++) { int idx = cnt; cnt++; A[idx] = a[0][j]; B[idx] = a[0][j + 1]; W[idx] = c[a[0][j + 1]] - c[a[0][j]]; } for (int j = 0; j + 1 < (int)a[1].size(); j++) { int idx = cnt; cnt++; A[idx] = a[1][j]; B[idx] = a[1][j + 1]; W[idx] = c[a[1][j + 1]] - c[a[1][j]]; } return; } }
#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...