Submission #200625

#TimeUsernameProblemLanguageResultExecution timeMemory
200625wilwxkCity Mapping (NOI18_citymapping)C++14
57 / 100
14 ms7160 KiB
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e3+5; ll dist[MAXN][MAXN]; vector<tuple<int, int, int> > ans; vector<int> subtree[MAXN]; ll further[MAXN][2]; mt19937 rng(time(0)); int n; ll query(int a, int b) { if(a == b) return 0; if(a > b) swap(a, b); if(dist[a][b]) return dist[a][b]; // printf("query %d %d\n", a, b); return dist[a][b] = get_distance(a, b); } void solve(int cur) { if(subtree[cur].size() == 1) return; int x = further[cur][0]; int y = x; for(auto vertex : subtree[cur]) if(query(x, vertex) > query(x, y)) y = vertex; // printf("solve %d >> %d %d\n", cur, x, y); for(auto vertex : subtree[cur]) printf("%d ", vertex); cout << endl; vector<pair<ll, int> > line; vector<pair<ll, int> > aux; for(int vertex : subtree[cur]) { ll val = query(x, vertex) + query(y, vertex) - query(x, y); val /= 2; if(val == 0) line.push_back({query(x, vertex), vertex}); val = query(x, y) - query(vertex, y) + val; aux.push_back({val, vertex}); } sort(line.begin(), line.end()); sort(aux.begin(), aux.end()); subtree[cur].clear(); further[cur][0] = 0; further[cur][1] = -1; int p = 0; for(int i = 0; i < line.size(); i++) { int vertex = line[i].second; ll dx = line[i].first; while(p < aux.size() && aux[p].first == dx) { ll val = query(x, aux[p].second) - dx; if(val > further[vertex][1]) further[vertex][0] = aux[p].second, further[vertex][1] = val; subtree[vertex].push_back(aux[p++].second); } if(i != 0) ans.push_back({vertex, line[i-1].second, line[i].first-line[i-1].first}); } for(auto item : line) solve(item.second); } void find_roads(int N, int Q, int A[], int B[], int W[]) { n = N; int ori = rng()%n +1; for(int i = 1; i <= n; i++) subtree[ori].push_back(i); for(int i = 1; i <= n; i++) if(query(ori, i) > further[ori][1]) further[ori][0] = i, further[ori][1] = query(ori, i); solve(ori); for(int i = 0; i < ans.size(); i++) tie(A[i], B[i], W[i]) = ans[i]; }

Compilation message (stderr)

citymapping.cpp: In function 'void solve(int)':
citymapping.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < line.size(); i++) {
                 ~~^~~~~~~~~~~~~
citymapping.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p < aux.size() && aux[p].first == dx) {
         ~~^~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); i++) tie(A[i], B[i], W[i]) = ans[i];
                 ~~^~~~~~~~~~~~
#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...