#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef long long ll;
vector<pi> AdjList[100005];
vector<int> Ax;
vector<pi> EdgeList;
ll bigA, bigB, bigN, bigM, dist, dsu, dtv, S, T;
void res_Ax(){
for (int i = 0; i < bigM; ++i) Ax[i] = 0;
}
int find_spath_edge(vector<int> ved0, vector<int> ved1){
vector<int> v0, v1;
if (ved0.size() == 1 && ved1.size() == 0){
return ved0[0];
}
else if (ved0.size() == 0 && ved1.size() == 1){
return ved1[0];
}
res_Ax();
for (int i = 0; i < ved1.size(); ++i){
Ax[ved1[i]] = 1;
}
ll nd = ask(Ax);
if (nd > dist){
for (int i = 0; i < ved1.size(); ++i){
if (i%2==0) v0.push_back(ved1[i]);
else v1.push_back(ved1[i]);
}
}
else{
for (int i = 0; i < ved0.size(); ++i){
if (i%2==0) v0.push_back(ved0[i]);
else v1.push_back(ved0[i]);
}
}
return find_spath_edge(v0,v1);
}
vector<int> tree_u_edges, tree_v_edges;
void dfs(int p, int x, int c){
for (auto it : AdjList[x]){
if (it.second == p) continue;
if (c == 0) tree_u_edges.push_back(it.first);
else tree_v_edges.push_back(it.first);
dfs(x,it.second,c);
}
}
vector<pi> pot_edges;
void dfs2(int p, int x, int d){
if (d == 0) return;
for (auto it : AdjList[x]){
if (it.second == p) continue;
if (d == 1){
pot_edges.push_back(pi(it.first,it.second));
}
else{
dfs(x,it.second,d-1);
}
}
}
int solve(vector<int> tree_ed, int source, int parent, int distance){
pot_edges.clear();
dfs2(parent,source,distance);
vector<int> v0, v1;
for (int i = 0; i < pot_edges.size(); ++i){
if (i%2==0) v0.push_back(pot_edges[i].first);
else v1.push_back(pot_edges[i].first);
}
int e = find_spath_edge(v0,v1);
for (int i = 0; i < pot_edges.size(); ++i){
if (pot_edges[i].first == e) return pot_edges[i].second;
}
assert(0);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
bigM = U.size(); bigN = N; bigA = A; bigB = B;
Ax.resize(bigM,0);
dist = ask(Ax);
for (int i = 0; i < bigM; ++i){
AdjList[U[i]].push_back(pi(i,V[i]));
AdjList[V[i]].push_back(pi(i,U[i]));
EdgeList.push_back(pi(U[i],V[i]));
}
vector<int> v0, v1;
for (int i = 0; i < bigM; ++i){
if (i%2==0){
v0.push_back(i);
}
else v1.push_back(i);
}
res_Ax();
int x = find_spath_edge(v0,v1);
int u = EdgeList[x].first, v = EdgeList[x].second;
dfs(v,u,0); dfs(u,v,1);
res_Ax();
for (int i = 0; i < tree_u_edges.size(); ++i){
Ax[tree_u_edges[i]] = 1;
}
dsu = (ask(Ax)-dist)/(B-A);
dtv = dist/A - dsu - 1;
assert(dsu >= 0 && dtv >= 0);
if (dsu > 0) S = solve(tree_u_edges,u,v,dsu);
else S = u;
if (dtv > 0 ) T = solve(tree_v_edges,v,u,dtv);
else T = v;
assert(0);
answer(S,T);
}
Compilation message
highway.cpp: In function 'int find_spath_edge(std::vector<int>, std::vector<int>)':
highway.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ved1.size(); ++i){
~~^~~~~~~~~~~~~
highway.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ved1.size(); ++i){
~~^~~~~~~~~~~~~
highway.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ved0.size(); ++i){
~~^~~~~~~~~~~~~
highway.cpp: In function 'int solve(std::vector<int>, int, int, int)':
highway.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < pot_edges.size(); ++i){
~~^~~~~~~~~~~~~~~~~~
highway.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < pot_edges.size(); ++i){
~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tree_u_edges.size(); ++i){
~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2664 KB |
Output is incorrect: more than 100 calls to ask. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2680 KB |
Output is incorrect: more than 100 calls to ask. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
3892 KB |
Output is incorrect: more than 100 calls to ask. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2768 KB |
Output is incorrect: more than 100 calls to ask. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
372 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
317 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
