Submission #747933

#TimeUsernameProblemLanguageResultExecution timeMemory
747933saayan007City Mapping (NOI18_citymapping)C++17
25 / 100
56 ms8400 KiB
#include "bits/stdc++.h" #include "citymapping.h" using namespace std; using ll = long long; #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]; for(int i = 1; i <= N; ++i) { dist[i][i] = 0; for(int j = i + 1; j <= N; ++j) { dist[i][j] = dist[j][i] = abs(get_distance(i, j)); } } /* for(int i = 1; i <= N; ++i) { */ /* for(int j = 1; j <= N; ++j) { */ /* cout << 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(dist[i][j] < dist[i][x]) x = j; } adj[i].eb(x, dist[i][x]); int y = 0; for(int j = 1; j <= N; ++j) { if(j == i || j == x) continue; if(dist[i][j] == dist[i][x] + dist[x][j]) continue; if(y == 0 || dist[i][j] < dist[i][y]) y = j; } if(y == 0) continue; adj[i].eb(y, dist[i][y]); /* continue; */ int z = 0; for(int j = 1; j <= N; ++j) { if(j == i || j == x || j == y) continue; if(dist[i][j] == dist[i][x] + dist[x][j]) continue; if(dist[i][j] == dist[i][y] + dist[y][j]) continue; if(z == 0 || dist[i][j] < dist[i][z]) z = j; } if(z == 0) continue; adj[i].eb(z, 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...