#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int> > > adj2(100000);
pair<int, int> parents[100000];
bool visited[100000];
void dfs(int s, int parent, int ind){
if(!visited[s]){
parents[s] = {parent, ind};
visited[s] = 1;
for(int i = 0; i < adj2[s].size(); i++){
dfs(adj2[s][i].first, s, adj2[s][i].second);
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
vector<int> w(M);
for(int i = 0; i < M; i++){
w[i] = 0;
}
vector<vector<pair<int, int> > > adj(N);
for(int i = 0; i < M; i++){
adj2[U[i]].push_back({V[i], i});
adj2[V[i]].push_back({U[i], i});
}
dfs(0, 0, 0);
for(int i = 1; i < N; i++){
adj[parents[i].first].push_back({i, parents[i].second});
}
long long curr = ask(w);
int where = 0;
bool ok = 1;
while(ok){
ok = 0;
int lo = 0; int hi = adj[where].size() - 1;
int best = -1;
while(lo <= hi){
int mid = (lo + hi)/2;
for(int j = lo; j <= mid; j++){
w[adj[where][j].second] = !w[adj[where][j].second];
}
long long last = ask(w);
if(last != curr){
hi = mid - 1;
ok = 1;
best = adj[where][mid].first;
curr = last;
}
else{
lo = mid + 1;
}
}
if(ok)where = best;
}
answer(0, where);
}
Compilation message
highway.cpp: In function 'void dfs(int, int, int)':
highway.cpp:14:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i = 0; i < adj2[s].size(); i++){
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2688 KB |
Output is correct |
3 |
Correct |
2 ms |
2688 KB |
Output is correct |
4 |
Correct |
2 ms |
2688 KB |
Output is correct |
5 |
Correct |
3 ms |
2688 KB |
Output is correct |
6 |
Correct |
2 ms |
2688 KB |
Output is correct |
7 |
Correct |
2 ms |
2688 KB |
Output is correct |
8 |
Correct |
2 ms |
2688 KB |
Output is correct |
9 |
Correct |
2 ms |
2688 KB |
Output is correct |
10 |
Correct |
2 ms |
2688 KB |
Output is correct |
11 |
Correct |
2 ms |
2688 KB |
Output is correct |
12 |
Correct |
2 ms |
2688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2816 KB |
Output is correct |
2 |
Correct |
15 ms |
3756 KB |
Output is correct |
3 |
Incorrect |
159 ms |
12448 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
4088 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
2816 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
3840 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
3840 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |