#include "highway.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll m,i,x[202020],y[202020],jarak,p[202020],te,o[202020];
vector<ll> v[202020],w[202020];
vector<int> z,q1,q2;
void dfs(ll aa,ll bb,ll cc)
{
p[aa]=bb;
//dep[aa]=cc;
ll ii;
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=bb)
{
x[++te]=w[aa][ii];
y[te]=v[aa][ii];
o[w[aa][ii]]=v[aa][ii];
dfs(v[aa][ii],aa,cc+1);
}
}
void dfs1(ll aa)
{
ll ii;
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=p[aa])
{
// cout<<w[aa][ii]<<"_\n";
z[w[aa][ii]]=0;
dfs1(v[aa][ii]);
}
}
void dfs2(ll aa,ll bb)
{
ll ii;
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=p[aa])
{
if(bb==1)
{
q1.pb(w[aa][ii]);
}
dfs2(v[aa][ii],bb-1);
}
}
void dfs3(ll aa,ll bb,ll cc)
{
ll ii;
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=p[aa]&&v[aa][ii]!=cc)
{
if(bb==1)
q2.pb(w[aa][ii]);
dfs3(v[aa][ii],bb-1,cc);
}
}
void ubah(ll aa,ll bb,ll cc)
{
ll ii;
for(ii=aa;ii<=bb;ii++)
z[x[ii]]=cc;
}
void ubah1(ll aa,ll bb,ll cc)
{
ll ii;
for(ii=aa;ii<=bb;ii++)
z[q1[ii]]=cc;
}
void ubah2(ll aa,ll bb,ll cc)
{
ll ii;
for(ii=aa;ii<=bb;ii++)
z[q2[ii]]=cc;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
m = U.size();
for(i=0;i<m;i++)
{
v[U[i]].pb(V[i]);
w[U[i]].pb(i);
v[V[i]].pb(U[i]);
w[V[i]].pb(i);
}
dfs(0,0,0);
ll L=0,R=m-1,C,H;
for(i=0;i<m;i++)
z.pb(0);
ll tem=ask(z);
jarak=tem/A;
ask(z);
while(L<=R)
{
C=(L+R)/2;
ubah(1,C,1);
ubah(C+1,m,0);
if(ask(z)==tem)
{
H=C+1;
L=C+1;
}
else
R=C-1;
}
ubah(1,m,1);
z[x[H]]=0;
dfs1(y[H]);
ll tom=ask(z);
//for(i=0;i<m;i++)
// cout<<i<<" "<<z[i]<<"\n";
//cout<<y [H]<<" "<<H<<" "<<tom<<" "<<tem<<"\n";
if(tom==tem)
{
if(jarak==1)
{
answer(y[H],p[y[H]]);
}
else
{
dfs2(y[H],jarak-1);
L=0;
R=q1.size()-1;
ll H1;
while(L<=R)
{
C=(L+R)/2;
ubah1(0,C,0);
ubah1(C+1,q1.size()-1,1);
if(ask(z)==tem)
{
H1=C;
R=C-1;
}
else
L=C+1;
}
answer(o[q1[H1]],p[y[H]]);
}
//cout<<"A";
}
else
{
ll jer=jarak-((tom-tem)/(B-A)),H1,H2;
if(jer==1)
H1=y[H];
else
{
dfs2(y[H],jer-1);
//cout<<jer<<"\n";
L=0;
R=q1.size()-1;
ubah(1,m,0);
//for(i=0;i<q1.size();i++)
// cout<<q1[i]<<"*\n";
while(L<=R)
{
C=(L+R)/2;
ubah1(0,C,0);
ubah1(C+1,q1.size()-1,1);
if(ask(z)==tem)
{
// cout<<C<<"_()\n";
H1=o[q1[C]];
R=C-1;
}
else
L=C+1;
}
// cout<<H1<<"\n";
}
ubah(1,m,0);
dfs3(p[y[H]],jarak-jer,y[H]);
L=0;
R=q2.size()-1;
//for(i=0;i<q2.size();i++)
// cout<<q2[i]<<"_\n";
while(L<=R)
{
C=(L+R)/2;
ubah2(0,C,0);
ubah2(C+1,q2.size()-1,1);
if(ask(z)==tem)
{
H2=o[q2[C]];
R=C-1;
}
else
L=C+1;
}
//cout<<H1<<" "<<H2<<"\n";
answer(H1, H2);
}
}
Compilation message
highway.cpp: In function 'void dfs(ll, ll, ll)':
highway.cpp:17:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs1(ll)':
highway.cpp:29:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs2(ll, ll)':
highway.cpp:40:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs3(ll, ll, ll)':
highway.cpp:53:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:195:9: warning: 'H2' may be used uninitialized in this function [-Wmaybe-uninitialized]
answer(H1, H2);
~~~~~~^~~~~~~~
highway.cpp:195:9: warning: 'H1' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:141:18: warning: 'H1' may be used uninitialized in this function [-Wmaybe-uninitialized]
answer(o[q1[H1]],p[y[H]]);
^
highway.cpp:111:6: warning: 'H' may be used uninitialized in this function [-Wmaybe-uninitialized]
dfs1(y[H]);
~~~~^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9848 KB |
Output is correct |
2 |
Correct |
11 ms |
9848 KB |
Output is correct |
3 |
Correct |
11 ms |
9720 KB |
Output is correct |
4 |
Correct |
11 ms |
9848 KB |
Output is correct |
5 |
Correct |
11 ms |
9808 KB |
Output is correct |
6 |
Correct |
11 ms |
9848 KB |
Output is correct |
7 |
Correct |
10 ms |
9720 KB |
Output is correct |
8 |
Correct |
11 ms |
9896 KB |
Output is correct |
9 |
Correct |
11 ms |
9848 KB |
Output is correct |
10 |
Correct |
11 ms |
9848 KB |
Output is correct |
11 |
Correct |
11 ms |
9724 KB |
Output is correct |
12 |
Correct |
12 ms |
9720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
9848 KB |
Output is correct |
2 |
Correct |
31 ms |
11044 KB |
Output is correct |
3 |
Correct |
260 ms |
21396 KB |
Output is correct |
4 |
Correct |
282 ms |
21484 KB |
Output is correct |
5 |
Correct |
263 ms |
21452 KB |
Output is correct |
6 |
Correct |
277 ms |
21396 KB |
Output is correct |
7 |
Correct |
282 ms |
21396 KB |
Output is correct |
8 |
Correct |
276 ms |
21396 KB |
Output is correct |
9 |
Correct |
272 ms |
21440 KB |
Output is correct |
10 |
Correct |
318 ms |
21392 KB |
Output is correct |
11 |
Correct |
273 ms |
22188 KB |
Output is correct |
12 |
Correct |
270 ms |
23044 KB |
Output is correct |
13 |
Correct |
268 ms |
22424 KB |
Output is correct |
14 |
Correct |
291 ms |
21612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
11768 KB |
Output is correct |
2 |
Correct |
40 ms |
13672 KB |
Output is correct |
3 |
Correct |
53 ms |
15240 KB |
Output is correct |
4 |
Correct |
185 ms |
25884 KB |
Output is correct |
5 |
Correct |
178 ms |
25900 KB |
Output is correct |
6 |
Correct |
190 ms |
26840 KB |
Output is correct |
7 |
Correct |
167 ms |
25880 KB |
Output is correct |
8 |
Correct |
150 ms |
26148 KB |
Output is correct |
9 |
Correct |
177 ms |
25880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9848 KB |
Output is correct |
2 |
Correct |
33 ms |
11120 KB |
Output is correct |
3 |
Correct |
157 ms |
18952 KB |
Output is correct |
4 |
Correct |
267 ms |
21404 KB |
Output is correct |
5 |
Correct |
246 ms |
21400 KB |
Output is correct |
6 |
Correct |
274 ms |
21400 KB |
Output is correct |
7 |
Correct |
238 ms |
21444 KB |
Output is correct |
8 |
Correct |
269 ms |
21508 KB |
Output is correct |
9 |
Correct |
256 ms |
21372 KB |
Output is correct |
10 |
Correct |
255 ms |
21416 KB |
Output is correct |
11 |
Correct |
281 ms |
21084 KB |
Output is correct |
12 |
Correct |
284 ms |
23004 KB |
Output is correct |
13 |
Correct |
270 ms |
22032 KB |
Output is correct |
14 |
Correct |
301 ms |
22296 KB |
Output is correct |
15 |
Correct |
253 ms |
21312 KB |
Output is correct |
16 |
Correct |
248 ms |
21400 KB |
Output is correct |
17 |
Correct |
286 ms |
22000 KB |
Output is correct |
18 |
Correct |
264 ms |
21668 KB |
Output is correct |
19 |
Correct |
247 ms |
21332 KB |
Output is correct |
20 |
Correct |
265 ms |
22816 KB |
Output is correct |
21 |
Correct |
231 ms |
22616 KB |
Output is correct |
22 |
Correct |
223 ms |
22604 KB |
Output is correct |
23 |
Correct |
228 ms |
22156 KB |
Output is correct |
24 |
Correct |
255 ms |
22864 KB |
Output is correct |
25 |
Correct |
262 ms |
27424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
75 ms |
43532 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
73 ms |
44708 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |