Submission #747976

#TimeUsernameProblemLanguageResultExecution timeMemory
747976saayan007City Mapping (NOI18_citymapping)C++17
25 / 100
58 ms8300 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 ll dist[1001][1001]; ll 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]; } void find_roads(int N, int Q, int A[], int B[], int W[]) { if(Q == 1200) { for(int i = 1; i <= N; ++i) { for(int j = 1; j <= N; ++j) { dist[i][j] = (i == j ? 0 : -1); } } 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; } ll other_dist[N + 1][N + 1]; for(int i = 1; i <= N; ++i) { other_dist[i][i] = 0; for(int j = i + 1; j <= N; ++j) { other_dist[i][j] = other_dist[j][i] = abs(get_distance(i, j)); } } /* for(int i = 1; i <= N; ++i) { */ /* for(int j = 1; j <= N; ++j) { */ /* cout << other_dist[i][j] << ' '; */ /* } */ /* cout << nl; */ /* } */ /* cout << nl; */ vector<pair<int, ll>> adj[N + 1]; for(int i = 1; i <= N; ++i) { int x = (i == 1 ? 2 : 1); for(int j = 1; j <= N; ++j) { if(j == i) continue; if(other_dist[i][j] < other_dist[i][x]) x = j; } adj[i].eb(x, other_dist[i][x]); int y = 0; for(int j = 1; j <= N; ++j) { if(j == i || j == x) continue; if(other_dist[i][j] == other_dist[i][x] + other_dist[x][j]) continue; if(y == 0 || other_dist[i][j] < other_dist[i][y]) y = j; } if(y == 0) continue; adj[i].eb(y, other_dist[i][y]); /* continue; */ int z = 0; for(int j = 1; j <= N; ++j) { if(j == i || j == x || j == y) continue; if(other_dist[i][j] == other_dist[i][x] + other_dist[x][j]) continue; if(other_dist[i][j] == other_dist[i][y] + other_dist[y][j]) continue; if(z == 0 || other_dist[i][j] < other_dist[i][z]) z = j; } if(z == 0) continue; adj[i].eb(z, other_dist[i][z]); } int ptr = 0; for(int i = 1; i <= N; ++i) { for(auto [j, w] : adj[i]) { if(j <= i) continue; A[ptr] = i; B[ptr] = j; W[ptr] = w; ++ptr; /* cout << i << ' ' << j << ' ' << w << nl; */ } } 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...