제출 #415716

#제출 시각아이디문제언어결과실행 시간메모리
415716_fractal통행료 (IOI18_highway)C++14
7 / 100
330 ms12432 KiB
#include "highway.h" #include <iostream> #include <algorithm> #include <queue> using namespace std; vector<vector<pair<int, int>>> g; vector<int> lmao; long long cur; int M; int calc(int v, vector<pair<int, int>> t, int mid) { int tl = 1, tr = t.size() - 1, ans = v; vector<int> get(M, 0); while (tl <= tr) { int tm = tl + tr >> 1; for (auto &i : get) i = 0; for (int i = 1; i < t.size(); ++i) get[lmao[t[i].second]] = 1; for (int i = 1; i <= tm; ++i) { get[lmao[t[i].second]] = 0; } get[mid] = 0; if (ask(get) == cur) { ans = t[tm].second; tr = tm - 1; } else { tl = tm + 1; } } return ans; } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { M = U.size(); vector<int> activ; vector<int> get(M, 0); vector<int> was(N, 0); g = vector<vector<pair<int, int>>> (N, vector<pair<int, int>>(0)); cur = ask(get); lmao = vector<int>(N, 0); for (int i = 0; i < M; ++i) { g[V[i]].push_back({U[i], i}); g[U[i]].push_back({V[i], i}); } int tl = 0, tr = M, ans = -1; while (tl <= tr) { int tm = tl + tr >> 1; for (int i = 0; i < M; ++i) get[i] = (i <= tm ? 0 : 1); if (ask(get) == cur) { ans = tm; tr = tm - 1; } else { tl = tm + 1; } } queue<int> q; vector<int> d(N, -1), col(N, 0); vector<pair<int, int>> is[2]; q.push(U[ans]), q.push(V[ans]); d[U[ans]] = d[V[ans]] = 0; col[U[ans]] = 0; col[V[ans]] = 1; while (q.size()) { int v = q.front(); q.pop(); is[col[v]].push_back({d[v], v}); for (auto it : g[v]) { int to = it.first, c = it.second; if (d[to] == -1) { d[to] = d[v] + 1; col[to] = col[v]; lmao[to] = c; q.push(to); } } } sort(is[0].begin(), is[0].end()); sort(is[1].begin(), is[1].end()); int a = calc(U[ans], is[0], ans); int b = calc(V[ans], is[1], ans); answer(a, b); return; }

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

highway.cpp: In function 'int calc(int, std::vector<std::pair<int, int> >, int)':
highway.cpp:16:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
highway.cpp:18:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for (int i = 1; i < t.size(); ++i)
      |                   ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...