#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
const int MAXN=200010;
int marc[MAXN],dist[MAXN];
vector<int> grafo[MAXN],grafo2[MAXN];
pair<int,int> edge[MAXN];
/*
long long int ask(vector<int> aux)
{
printf("ASK : ");
for(int i=0;i<aux.size();i++) printf("%d",aux[i]);
printf("\n");
long long int val;
scanf("%lld",&val);
return val;
}
*/
void dfs(int v,int ind)
{
marc[v]=ind;
for(int i=0;i<grafo2[v].size();i++)
{
int viz=grafo2[v][i];
if(marc[viz]==ind) continue;
dist[viz]=dist[v]+1;
dfs(viz,ind);
}
}
void find_pair(int n,vector<int> u,vector<int> v,int a,int b)
{
vector<int> w;
for(int i=0;i<u.size();i++) w.push_back(0);
long long int aux=ask(w);
for(int i=0;i<u.size();i++)
{
grafo[u[i]].push_back(v[i]);
grafo[v[i]].push_back(u[i]);
edge[i]=make_pair(u[i],v[i]);
}
for(int i=0;i<u.size();i++)
{
w[i]=1;
if(ask(w)>aux)
{
int a=edge[i].first;
int b=edge[i].second;
grafo2[a].push_back(b);
grafo2[b].push_back(a);
}
w[i]=0;
}
long long int resp=0, s,t;
for(int i=0;i<n;i++)
{
dfs(i,i+1);
for(int j=0;j<n;j++)
{
if(resp<dist[j])
resp=dist[j], s=i, t=j;
}
memset(dist,0,sizeof(dist));
}
// printf("%lld %lld\n",s,t);
answer(s,t);
}
/*
int main ()
{
int m,n,a,b;
vector<int> u,v;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d %d",&a,&b), u.push_back(a), v.push_back(b);
scanf("%d %d",&a,&b);
find_pair(n,u,v,a,b);
}
*/
/*
7 6
0 1
1 2
2 3
3 4
4 5
5 6
1 10
*/
Compilation message
highway.cpp: In function 'void dfs(int, int)':
highway.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<grafo2[v].size();i++)
~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<u.size();i++) w.push_back(0);
~^~~~~~~~~
highway.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<u.size();i++)
~^~~~~~~~~
highway.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<u.size();i++)
~^~~~~~~~~
highway.cpp:75:8: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
answer(s,t);
~~~~~~^~~~~
highway.cpp:75:8: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
10496 KB |
Output is correct |
| 2 |
Correct |
17 ms |
10432 KB |
Output is correct |
| 3 |
Correct |
16 ms |
10500 KB |
Output is correct |
| 4 |
Correct |
16 ms |
10468 KB |
Output is correct |
| 5 |
Correct |
15 ms |
10488 KB |
Output is correct |
| 6 |
Correct |
16 ms |
10492 KB |
Output is correct |
| 7 |
Correct |
15 ms |
10496 KB |
Output is correct |
| 8 |
Correct |
16 ms |
10408 KB |
Output is correct |
| 9 |
Correct |
16 ms |
10492 KB |
Output is correct |
| 10 |
Correct |
15 ms |
10488 KB |
Output is correct |
| 11 |
Correct |
16 ms |
10496 KB |
Output is correct |
| 12 |
Correct |
16 ms |
10540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9720 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 |
10260 KB |
Output is incorrect: more than 100 calls to ask. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9720 KB |
Output is incorrect: more than 100 calls to ask. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
10280 KB |
Output is incorrect: more than 100 calls to ask. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
10264 KB |
Output is incorrect: more than 100 calls to ask. |
| 2 |
Halted |
0 ms |
0 KB |
- |
