제출 #200640

#제출 시각아이디문제언어결과실행 시간메모리
200640wilwxkCity Mapping (NOI18_citymapping)C++14
0 / 100
14 ms4216 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<pair<int, int> > g[MAXN]; int sz[MAXN]; ll depth[MAXN]; 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]; return dist[a][b] = get_distance(a, b); } bool cmp(pair<int, ll> a, pair<int, ll> b) { return sz[a.first] > sz[b.first]; } void predfs(int cur) { sz[cur] = 1; for(auto edge : g[cur]) { int viz, w; tie(viz, w) = edge; depth[viz] = depth[cur]+w; predfs(viz); sz[cur] += sz[viz]; } sort(g[cur].begin(), g[cur].end(), cmp); } ll dfs(int cur, int x) { // printf("%d %d\n", cur, x); if(g[cur].empty()) { ll val = query(1, x)+query(x, cur)-query(1, cur); val /= 2; val = query(1, x)-val; if(val == depth[cur]) { g[cur].push_back({x, query(cur, x)}); ans.push_back({cur, x, query(cur, x)}); // printf("added %d %d %lld\n", cur, x, query(cur, x)); return -1; } return val; } bool explore = 0; for(auto edge : g[cur]) { int viz, w; tie(viz, w) = edge; ll val = dfs(viz, x); if(val < depth[cur]) return val; } } void process(int cur) { predfs(1); dfs(1, cur); } void find_roads(int N, int Q, int A[], int B[], int W[]) { n = N; vector<pair<ll, int> > aux; for(int i = 1; i <= n; i++) aux.push_back({query(1, i), i}); sort(aux.begin(), aux.end()); for(auto item : aux) if(item.second != 1) process(item.second); for(int i = 0; i < ans.size(); i++) tie(A[i], B[i], W[i]) = ans[i]; }

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

citymapping.cpp: In function 'll dfs(int, int)':
citymapping.cpp:51:7: warning: unused variable 'explore' [-Wunused-variable]
  bool explore = 0;
       ^~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:73: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];
                 ~~^~~~~~~~~~~~
citymapping.cpp: In function 'll dfs(int, int)':
citymapping.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#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...