제출 #390815

#제출 시각아이디문제언어결과실행 시간메모리
390815JimmyZJX통행료 (IOI18_highway)C++14
컴파일 에러
0 ms0 KiB
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> #include <climits> #include <cassert> #include <tuple> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> #include <unordered_set> #include <unordered_map> #include <random> #include "highway.h" using namespace std; typedef long long LL; typedef vector<int> Vi; typedef vector<bool> Vb; typedef vector<vector<int>> Vii; #define forR(i, n) for (int i = 0; i < (n); i++) #define MAXMN 130003 vector<vector<pair<int, int>>> nbs(MAXMN); // {nb, edgeNo} vector<int> parent(MAXMN); vector<int> parentEdge(MAXMN); Vi edgeSorted; Vi edgeRank; int maxDist; int parentOf(int n1, int n2) { if (parent[n1] == n2) return n2; return n1; } int childOf(int n1, int n2) { if (parent[n1] == n2) return n1; return n2; } int largestEdgeOfRank(int r) { forR(i, edgeSorted.size()) { if (edgeRank[edgeSorted[i]] > r) return i > 0 ? i - 1 : i; } return edgeSorted.size() - 1; } void build_tree(int root) { Vb vis(MAXMN); Vb edgeVis(MAXMN); edgeSorted.clear(); edgeRank = Vi(MAXMN); maxDist = 0; queue<pair<int, int>> q; q.push({ root, 0 }); // nodeNo, level vis[root] = true; while (!q.empty()) { auto p = q.front(); q.pop(); int x = p.first, level = p.second; maxDist = max(maxDist, level); for (auto nbP : nbs[x]) { int nb = nbP.first, nbEdge = nbP.second; if (!vis[nb]) { vis[nb] = true; q.push({ nb, level + 1 }); parent[nb] = x; parentEdge[nb] = nbEdge; } if (!edgeVis[nbEdge]) { edgeVis[nbEdge] = true; edgeSorted.push_back(nbEdge); edgeRank[nbEdge] = level + 1; } } } } void find_pair(int N, Vi U, Vi V, int A, int B) { int m = U.size(); forR(i, m) { nbs[U[i]].push_back({ V[i], i }); nbs[V[i]].push_back({ U[i], i }); } for (auto& v : nbs) { random_shuffle(v.begin(), v.end(), mt19937()); } build_tree(0); int far_node = childOf(U[edgeSorted.back()], V[edgeSorted.back()]); build_tree(far_node); int far_node2 = childOf(U[edgeSorted.back()], V[edgeSorted.back()]); Vi DiameterEdges; for (int n = far_node2; n != far_node; n = parent[n]) { DiameterEdges.push_back(parentEdge[n]); } int midEdge = DiameterEdges[(DiameterEdges.size() - 1) / 2]; int midNode = childOf(U[midEdge], V[midEdge]); //build_tree(midNode); build_tree((rand() * 2000) % N); //build_tree(far_node2); LL minCost = ask(Vi(m)); LL dist = minCost / A; // search for range of edges int l = 0, r = m - 1; while (l < r) { int mid = (l + r) / 2; Vi ws(m); for (int i = 0; i <= mid; i++) ws[edgeSorted[i]] = 1; if (ask(ws) == minCost) { l = mid + 1; } else { r = mid; } } int leftEdge = edgeSorted[l]; int rootNode = parentOf(U[leftEdge], V[leftEdge]); build_tree(rootNode); l = 0, r = largestEdgeOfRank(dist); while (l < r) { int mid = (l + r) / 2; Vi ws(m); for (int i = mid + 1; i <= m - 1; i++) ws[edgeSorted[i]] = 1; if (ask(ws) == minCost) { r = mid; } else { l = mid + 1; } } int rightRank = l; int rightEdge = edgeSorted[l]; int rightChild = childOf(U[rightEdge], V[rightEdge]); LL distR = 0; Vi REdges; for (int n = rightChild; n != rootNode; n = parent[n]) { REdges.push_back(parentEdge[n]); distR++; } LL distL = dist - distR; if (distL == 0) { answer(rootNode, rightChild); return; } l = largestEdgeOfRank(distL - 1), r = min(rightRank, largestEdgeOfRank(distL)); while (l < r) { int mid = (l + r) / 2; Vi ws(m); for (int i = mid + 1; i <= m - 1; i++) ws[edgeSorted[i]] = 1; for (int e : REdges) ws[e] = 0; if (ask(ws) == minCost) { r = mid; } else { l = mid + 1; } } int edgeLeft = edgeSorted[l]; int leftChild = childOf(U[edgeLeft], V[edgeLeft]); answer(leftChild, rightChild); }

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

highway.cpp: In function 'int largestEdgeOfRank(int)':
highway.cpp:27:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 | #define forR(i, n) for (int i = 0; i < (n); i++)
      |                                      ^
highway.cpp:49:2: note: in expansion of macro 'forR'
   49 |  forR(i, edgeSorted.size()) {
      |  ^~~~
highway.cpp: In function 'void find_pair(int, Vi, Vi, int, int)':
highway.cpp:102:6: warning: unused variable 'midNode' [-Wunused-variable]
  102 |  int midNode = childOf(U[midEdge], V[midEdge]);
      |      ^~~~~~~
In file included from /usr/include/c++/9/algorithm:62,
                 from highway.cpp:3:
/usr/include/c++/9/bits/stl_algo.h: In instantiation of 'void std::random_shuffle(_RAIter, _RAIter, _Generator&&) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Generator = std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>]':
highway.cpp:90:47:   required from here
/usr/include/c++/9/bits/stl_algo.h:4650:48: error: no match for call to '(std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>) (__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type)'
 4650 |    _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/9/random:49,
                 from highway.cpp:16:
/usr/include/c++/9/bits/random.h:561:7: note: candidate: 'std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::operator()() [with _UIntType = long unsigned int; long unsigned int __w = 32; long unsigned int __n = 624; long unsigned int __m = 397; long unsigned int __r = 31; _UIntType __a = 2567483615; long unsigned int __u = 11; _UIntType __d = 4294967295; long unsigned int __s = 7; _UIntType __b = 2636928640; long unsigned int __t = 15; _UIntType __c = 4022730752; long unsigned int __l = 18; _UIntType __f = 1812433253; std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type = long unsigned int]'
  561 |       operator()();
      |       ^~~~~~~~
/usr/include/c++/9/bits/random.h:561:7: note:   candidate expects 0 arguments, 1 provided