이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
#include "highway.h"
#define f first
#define s second
#define DIM 130005
using namespace std;
static int t[2][DIM], niv[2][DIM], viz[2][DIM], m, p[2][DIM], nr[2], n, cd[DIM];
static pair<int, int> w[DIM];
static vector<int> r, v[DIM];
void bfs(int i, int srs){
int st, dr, j, nod, vecin;
viz[i][srs] = 1;
cd[1] = srs;
st = dr = 1;
while(st <= dr){
nod = cd[st];
st++;
p[i][nod] = ++nr[i];
for(j = 0; j < v[nod].size(); j++){
vecin = v[nod][j];
if(viz[i][vecin] == 0){
cd[++dr] = vecin;
niv[i][vecin] = 1 + niv[i][nod];
t[i][vecin] = nod;
viz[i][vecin] = 1;
}
}
}
}
int solve(int ind, long long sum){
int i, st, dr, mid, ok;
for(i = 0; i < m; i++){
if(t[ind][ w[i].s ] == w[i].f){
swap(w[i].f, w[i].s);
}
}
st = 1;
dr = n;
while(st < dr){
mid = (st + dr) / 2;
ok = 0;
for(i = 1; i <= n; i++){
if(niv[ind][i] < niv[1 - ind][i] && p[ind][i] > mid && p[ind][i] <= dr){
ok = 1;
}
}
if(ok == 0){
dr = mid;
continue;
}
for(i = 0; i < m; i++){
if(t[ind][ w[i].f ] == w[i].s && niv[ind][ w[i].f ] < niv[1 - ind][ w[i].f ]){
if(p[ind][ w[i].f ] > mid && p[ind][ w[i].s ] <= dr){
r[i] = 1;
}
else{
r[i] = 0;
}
}
else{
if(niv[ind][ w[i].f ] > niv[1 - ind][ w[i].f ] && niv[ind][ w[i].s ] > niv[1 - ind][ w[i].s ]){
r[i] = 0;
}
else{
r[i] = 1;
}
}
}
if(ask(r) > sum){
st = mid + 1;
}
else{
dr = mid;
}
}
for(int i = 1; i <= n; i++){
if(p[ind][i] == st){
return i;
}
}
}
void find_pair(int N, vector<int> U, vector<int> V, int a, int b){
n = N;
int i, st, dr, mid, x, y;
long long sum, cost;
m = U.size();
r.resize(m);
for(i = 0; i < m; i++){
w[i] = make_pair(U[i] + 1, V[i] + 1);
v[ w[i].f ].push_back(w[i].s);
v[ w[i].s ].push_back(w[i].f);
r[i] = 0;
}
sum = ask(r);
st = 0;
dr = m - 1;
while(st < dr){
mid = (st + dr) / 2;
for(i = 0; i < m; i++){
if(i >= st && i <= mid){
r[i] = 1;
}
else{
r[i] = 0;
}
}
if(ask(r) > sum){
dr = mid;
}
else{
st = mid + 1;
}
}
bfs(0, w[st].f);
bfs(1, w[st].s);
x = solve(0, sum + b - a);
y = solve(1, sum + b - a);
answer(x - 1, y - 1);
}
컴파일 시 표준 에러 (stderr) 메시지
highway.cpp: In function 'void bfs(int, int)':
highway.cpp:20:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j = 0; j < v[nod].size(); j++){
~~^~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:86:20: warning: unused variable 'cost' [-Wunused-variable]
long long sum, cost;
^~~~
highway.cpp: In function 'int solve(int, long long int)':
highway.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# | 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... |