제출 #836620

#제출 시각아이디문제언어결과실행 시간메모리
836620LiudasCity Mapping (NOI18_citymapping)C++17
57 / 100
26 ms724 KiB
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; struct node{ vector<long long> childs; vector<long long> dists; }; void dfs(int head, int par, long long dist, vector<node> &tree, vector<int> &good, long long d){ if((tree[head].childs.size() <= 2) && d < dist){ good.push_back(head); } for(int i = 0; i < tree[head].childs.size(); i ++){ if(tree[head].childs[i] == par)continue; dfs(tree[head].childs[i], head, dist, tree, good, d + tree[head].dists[i]); } } void find_roads(int N, int Q, int A[], int B[], int W[]) { vector<pair<long long, long long>> tree; vector<long long> init(N+5); int p = 0; for(int i = 1; i < N; i ++){ tree.push_back({get_distance(1, i+1), i+1}); init[i+1] = tree.back().first; } sort(tree.begin(), tree.end()); vector<int> picks(N+20); picks[0] = -1e9; vector <long long> ends; ends.push_back(1); vector<node> arr(N + 20); for(auto [j, i] : tree){ sort(ends.begin(), ends.end(), [&](long long a, long long b){return init[a] < init[b];}); long long t = get_distance(ends.back(), i); vector<int> good; dfs(ends.back(), -1, t, arr, good, 0); sort(good.begin(), good.end(), [&](long long a, long long b){return init[a] > init[b];}); for(auto r : good){ long long t = get_distance(r, i); if(init[i] == init[r] + t){ A[p] = i; B[p] = r; W[p++] = t; picks[r]++; ends.push_back(i); arr[r].childs.push_back(i); arr[r].dists.push_back(t); arr[i].childs.push_back(r); arr[i].dists.push_back(t); break; } } } return; }

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

citymapping.cpp: In function 'void dfs(int, int, long long int, std::vector<node>&, std::vector<int>&, long long int)':
citymapping.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i = 0; i < tree[head].childs.size(); 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...