#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=90005;
int n,m,par[MAXN];
vector <int> v[MAXN];
vector <pair<int,int> > vv;
map <pair<int,int>, int> r;
long long ANS;
void dfs (int x,int p,int l)
{
vv.push_back({l,x});
par[x]=p;
for (int i=0;i<v[x].size();i++)
{
if (v[x][i]!=p)
{
dfs(v[x][i],x,l+1);
}
}
}
void find_pair (int N, vector<int> U, vector<int> V, int A, int B)
{
n=N;
m=U.size();
vector<int> w;
w.resize(m);
ANS=ask(w);
for (int i=0;i<m;i++)
{
v[U[i]].push_back(V[i]);
v[V[i]].push_back(U[i]);
r[{U[i],V[i]}]=i;
r[{V[i],U[i]}]=i;
}
dfs(0,-1,1);
int low=0,high=vv.size(),mid,ans=-1;
while (low<=high)
{
for (int i=0;i<w.size();i++)
w[i]=0;
mid=(low+high)/2;
for (int i=mid;i<vv.size();i++)
{
int a=vv[i].second;
w[r[{a,par[a]}]]=1;
}
if (ask(w)!=ANS)
{
ans=vv[mid].second;
low=mid+1;
}
else
high=mid-1;
}
answer(0,ans);
}
Compilation message
highway.cpp: In function 'void dfs(int, int, int)':
highway.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<w.size();i++)
~^~~~~~~~~
highway.cpp:43:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=mid;i<vv.size();i++)
~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2424 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
12 ms |
2424 KB |
Output is correct |
4 |
Correct |
4 ms |
2424 KB |
Output is correct |
5 |
Correct |
4 ms |
2344 KB |
Output is correct |
6 |
Correct |
5 ms |
2412 KB |
Output is correct |
7 |
Correct |
4 ms |
2424 KB |
Output is correct |
8 |
Correct |
5 ms |
2424 KB |
Output is correct |
9 |
Correct |
4 ms |
2424 KB |
Output is correct |
10 |
Correct |
4 ms |
2428 KB |
Output is correct |
11 |
Correct |
4 ms |
2424 KB |
Output is correct |
12 |
Correct |
10 ms |
2424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2596 KB |
Output is correct |
2 |
Correct |
62 ms |
4472 KB |
Output is correct |
3 |
Correct |
534 ms |
19908 KB |
Output is correct |
4 |
Correct |
1132 ms |
19904 KB |
Output is correct |
5 |
Execution timed out |
1561 ms |
19908 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
40 ms |
5108 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
2680 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
423 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 |
397 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |