제출 #200604

#제출 시각아이디문제언어결과실행 시간메모리
200604wilwxkCity Mapping (NOI18_citymapping)C++14
25 / 100
33 ms8828 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]; 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 = rng()%int(subtree[cur].size()); x = subtree[cur][x]; // printf("solve %d >> %d\n", cur, x); for(auto vertex : subtree[cur]) printf("%d ", vertex); cout << endl; int mni; ll mn = 1e18; for(auto vertex : subtree[cur]) if(vertex != x && query(x, vertex) < mn) mn = query(x, vertex), mni = vertex; ans.push_back({x, mni, query(x, mni)}); vector<int> aux = subtree[cur]; subtree[cur].clear(); for(auto vertex : aux) { if(query(vertex, x) < query(vertex, mni)) subtree[x].push_back(vertex); else subtree[mni].push_back(vertex); } solve(x); solve(mni); } void find_roads(int N, int Q, int A[], int B[], int W[]) { n = N; for(int i = 1; i <= n; i++) subtree[n+1].push_back(i); solve(n+1); for(int i = 0; i < ans.size(); i++) tie(A[i], B[i], W[i]) = ans[i]; }

컴파일 시 표준 에러 (stderr) 메시지

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:49: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...