#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
vector<int> cam;
int A,B;
vector<int> grafo[90004];
vector<int> ek,vk,teste;
map< pair<int,int> ,int > edge;
void dfs(int v,int p,int dist,int k){
for(int i=0;i<grafo[v].size();i++){
int viz=grafo[v][i];
if(viz!=p){
if(dist==k-1){
ek.push_back(edge[make_pair(v,viz)]);
vk.push_back(viz);
}
else{
dfs(viz,v,dist+1,k);
}
}
}
}
void paint(int ini,int fim){
for(int i=0;i<teste.size();i++){
teste[i]=0;
}
for(int i=ini;i<=fim;i++){
teste[ek[i]]=1;
}
}
/*void answer(int s,int t){
cout<<s<<" "<<t<<endl;
}
long long int ask(vector<int> a){
long long int resp=0;
for(int i=0;i<cam.size();i++){
if(a[cam[i]]==0) resp+=A;
else resp+=B;
}
return resp;
}*/
void find_pair(int n,vector<int> u,vector<int> v,int a,int b){
for(int i=0;i<u.size();i++){
edge[make_pair(u[i],v[i])]=i;
edge[make_pair(v[i],u[i])]=i;
grafo[u[i]].push_back(v[i]);
grafo[v[i]].push_back(u[i]);
teste.push_back(0);
}
long long int t1=ask(teste);
int k=t1/a;
dfs(0,-1,0,k);
/*for(int i=0;i<ek.size();i++){
cout<<ek[i]<<" "<<vk[i]<<endl;
}*/
int ini=0,fim=ek.size()-1;
while(ini!=fim){
int meio=(fim+ini)/2;
paint(ini,meio);
long long int t=ask(teste);
if(t==t1){
ini=meio+1;
}
else{
fim=meio;
}
}
answer(0,vk[ini]);
}
/*int main(){
int n,m;
cin>>n>>m;
vector<int> u,v;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
u.push_back(a);
v.push_back(b);
}
int c;
cin>>c;
for(int i=0;i<c;i++){
int a;
cin>>a;
cam.push_back(a);
}
cin>>A>>B;
find_pair(n,u,v,A,B);
}*/
Compilation message
highway.cpp: In function 'void dfs(int, int, int, int)':
highway.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<grafo[v].size();i++){
~^~~~~~~~~~~~~~~~
highway.cpp: In function 'void paint(int, int)':
highway.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<teste.size();i++){
~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<u.size();i++){
~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2424 KB |
Output is correct |
2 |
Correct |
4 ms |
2440 KB |
Output is correct |
3 |
Correct |
4 ms |
2368 KB |
Output is correct |
4 |
Correct |
5 ms |
2424 KB |
Output is correct |
5 |
Correct |
4 ms |
2344 KB |
Output is correct |
6 |
Correct |
4 ms |
2424 KB |
Output is correct |
7 |
Correct |
5 ms |
2424 KB |
Output is correct |
8 |
Correct |
4 ms |
2424 KB |
Output is correct |
9 |
Correct |
4 ms |
2444 KB |
Output is correct |
10 |
Correct |
5 ms |
2424 KB |
Output is correct |
11 |
Correct |
4 ms |
2424 KB |
Output is correct |
12 |
Correct |
4 ms |
2424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
2604 KB |
Output is correct |
2 |
Correct |
45 ms |
4204 KB |
Output is correct |
3 |
Correct |
430 ms |
18568 KB |
Output is correct |
4 |
Correct |
360 ms |
18588 KB |
Output is correct |
5 |
Correct |
354 ms |
18580 KB |
Output is correct |
6 |
Correct |
388 ms |
18448 KB |
Output is correct |
7 |
Correct |
352 ms |
18484 KB |
Output is correct |
8 |
Correct |
411 ms |
18588 KB |
Output is correct |
9 |
Correct |
315 ms |
18492 KB |
Output is correct |
10 |
Correct |
400 ms |
18528 KB |
Output is correct |
11 |
Correct |
322 ms |
18892 KB |
Output is correct |
12 |
Correct |
350 ms |
19392 KB |
Output is correct |
13 |
Correct |
316 ms |
19204 KB |
Output is correct |
14 |
Correct |
384 ms |
19584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
35 ms |
4164 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
2552 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
58 ms |
5228 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
30 ms |
4408 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |