이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int mxN = 90000;
int n, m, mn;
vector<pii> adj[mxN];
int qry(vector<int> &edges) {
vector<int> w(m);
for (int i: edges) w[i] = 1;
return ask(w);
}
int bsearch(vector<int> &edges){
vector<int> in_edges(m), extras;
for (int e: edges) in_edges[e] = 1;
for (int i = 0; i < m; ++i) if (!in_edges[i]) extras.push_back(i);
int lo = 0, hi = edges.size(), mid;
while (hi != lo) {
mid = lo+hi>>1;
vector<int> q = extras;
q.insert(q.end(), edges.begin(), edges.begin()+mid+1);
if (qry(q) != mn) hi = mid;
else lo = mid+1;
}
return lo;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N;
m = U.size();
for (int i = 0; i < m; ++i) {
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
vector<int> all(m);
iota(all.begin(), all.end(), 0);
mn = ask(vector<int>(m));
int fst = bsearch(all);
queue<int> q;
vector<int> seen(n), node_in_subtree(n), tree_edges, psubtree, ch(m);
q.push(U[fst]);
seen[U[fst]] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (pii e: adj[u]) if (e.second >= fst && !seen[e.first]) {
seen[e.first] = 1;
q.push(e.first);
if (node_in_subtree[u] || e.first == V[fst]) {
node_in_subtree[e.first] = 1;
psubtree.push_back(e.second);
} else {
tree_edges.push_back(e.second);
}
ch[e.second] = e.first;
}
}
reverse(psubtree.begin(), psubtree.end());
reverse(tree_edges.begin(), tree_edges.end());
int res = bsearch(tree_edges);
answer(ch[psubtree[bsearch(psubtree)]], res == tree_edges.size() ? U[fst] : ch[tree_edges[res]] );
}
컴파일 시 표준 에러 (stderr) 메시지
highway.cpp: In function 'int bsearch(std::vector<int>&)':
highway.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | mid = lo+hi>>1;
| ~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:63:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | answer(ch[psubtree[bsearch(psubtree)]], res == tree_edges.size() ? U[fst] : ch[tree_edges[res]] );
| ~~~~^~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |