Submission #747979

#TimeUsernameProblemLanguageResultExecution timeMemory
747979saayan007City Mapping (NOI18_citymapping)C++17
13 / 100
3 ms4436 KiB
#include "bits/stdc++.h" #include "citymapping.h" using namespace std; using ll = long long; #define fr first #define sc second #define eb emplace_back #define nl endl void find_roads(int N, int Q, int A[], int B[], int W[]) { /* ll dist[N + 1][N + 1]; */ vector<vector<int>> dist(N + 1, vector<int>(N + 1, -1)); for(int i = 1; i <= N; ++i) { dist[i][i] = 0; } auto qry = [&](int x, int y) { if(dist[x][y] != -1) return dist[x][y]; dist[x][y] = abs(get_distance(x, y)); dist[y][x] = dist[x][y]; return dist[x][y]; }; vector<pair<int, ll>> adj[N + 1]; int x = 2; for(int i = 2; i <= N; ++i) { if(qry(1, i) < qry(1, x)) x = i; } /* cout << 1 << ' ' << x << nl; */ adj[1].eb(x, qry(1, x)); adj[x].eb(1, qry(1, x)); vector<pair<ll, int>> right, left; for(int i = 1; i <= N; ++i) { if(i == 1 || i == x) continue; if(qry(1, i) > qry(x, i)) right.eb(qry(x, i), i); else left.eb(qry(1, i), i); } sort(left.begin(), left.end()); sort(right.begin(), right.end()); /* for(auto [t, i] : left) cout << t << "," << i << ' '; cout << nl; */ /* for(auto [t, i] : right) cout << t << ',' << i << ' '; cout << nl; */ int m = left.size(); if(m) { int y = left[0].sc; adj[y].eb(1, qry(1, y)); adj[1].eb(y, qry(1, y)); for(int i = 1; i < m; ++i) { y = left[i].sc; int z = left[i - 1].sc; adj[y].eb(z, qry(1, y) - qry(1, z)); adj[z].eb(y, qry(1, y) - qry(1, z)); } } m = right.size(); if(m) { int y = right[0].sc; adj[y].eb(x, qry(x, y)); adj[x].eb(y, qry(x, y)); for(int i = 1; i < m; ++i) { y = right[i].sc; int z = right[i - 1].sc; adj[y].eb(z, qry(x, y) - qry(x, z)); adj[z].eb(y, qry(x, y) - qry(x, z)); } } int ptr = 0; for(int i = 1; i <= N; ++i) { for(auto [j, w] : adj[i]) { if(i < j) continue; A[ptr] = i; B[ptr] = j; W[ptr] = w; ++ptr; } } 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...