#include "meetings.h"
#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long
using namespace std ;
int qtd ;
vector<int> sub , arr ;
vector<bool> vis , foundPlace ;
vector< vector<int> > adj ;
void dfs1(int x, int parent)
{
sub[x] = 1 ;
for(auto e : adj[x] )
{
if(vis[e] || e == parent ) continue ;
dfs1(e, x ) ;
sub[x] += sub[e] ;
}
}
int dfs2(int x, int parent )
{
for(auto e : adj[x] )
{
if( e == parent || vis[e] ) continue ;
if( sub[e] > qtd/2 ) return dfs2(e, x ) ;
}
return x ;
}
void dfs3(int x, int parent )
{
sub[x] = 1 ;
for(auto e : adj[x] )
{
if( e == parent || vis[e] ) continue ;
dfs3(e,x ) ;
sub[x] += sub[e] ;
}
}
void insertMiddle(int A, int middle, int B )
{
for(int i = 0 ; i < 2 ; i++ )
{
for(int j = 0 ; j < sz(adj[A]) ; j++ )
{
if( adj[A][j] != B ) continue ;
swap(adj[A][ sz( adj[A] )-1 ], adj[A][j] ) ;
adj[A].pop_back() ;
break ;
}
swap(A,B) ;
}
adj[A].push_back(middle) ;
adj[B].push_back(middle) ;
adj[middle].push_back(A) ;
adj[middle].push_back(B) ;
}
void createEdge(int A, int B )
{
adj[A].push_back(B) ;
adj[B].push_back(A) ;
}
void decompose( int toInsert , int x )
{
dfs1( x , -1 ) ;
qtd = sub[x] ;
int cn = dfs2(x,-1) ;
dfs3(cn,-1) ;
vector<int> children ;
for(auto e : adj[cn] )
if( !vis[e] ) children.push_back( e ) ;
sort(all(children), [&](int i, int j ) { return sub[i] < sub[j] ; } ) ;
vis[cn] = true ;
for(int i = 0 ; i < sz(children) ; i += 2 )
{
if(i+1 == sz(children) )
{
int resp = Query(children[i], toInsert, cn ) ;
if( resp == toInsert ) insertMiddle(children[i], toInsert, cn ) ;
else if( resp == cn ) createEdge(cn, toInsert) ;
else if( resp == children[i] ) decompose(toInsert, children[i] ) ;
else
{
insertMiddle(cn, resp, children[i] ) ;
createEdge(resp, toInsert) ;
foundPlace[resp] = true ;
}
return ;
}
int resp = Query(children[i], children[i+1], toInsert) ;
if(resp == cn ) continue ;
else if( resp == children[i] ) return (void)(decompose(toInsert, children[i] ) ) ;
else if( resp == children[i+1] ) return (void)(decompose(toInsert, children[i+1] ) ) ;
else if( resp == toInsert )
{
resp = Query( children[i] , cn , toInsert ) ;
if( resp == toInsert ) insertMiddle( children[i] , toInsert, cn ) ;
else insertMiddle(children[i+1], toInsert, cn ) ;
return ;
}
else
{
int resp2 = Query(children[i], cn, resp ) ;
if(resp2 == resp )
{
insertMiddle(children[i], resp, cn ) ;
createEdge(resp, toInsert) ;
foundPlace[ resp ]= true ;
}
else
{
insertMiddle(children[i+1], resp, cn ) ;
createEdge(resp, toInsert) ;
foundPlace[resp] = true ;
}
return ;
}
}
createEdge(cn, toInsert) ;
}
void Solve(int N)
{
srand( time(0) ) ;
arr.resize(N) ; iota(all(arr) , 0 ) ;
random_shuffle( all(arr) ) ;
sub.resize(N) ;
vis.resize(N) ;
foundPlace.resize(N) ;
adj.resize(N, vector<int>() ) ;
adj[ arr[0] ].push_back( arr[1] ) ;
adj[ arr[1] ].push_back( arr[0] ) ;
foundPlace[ arr[0] ] = foundPlace[ arr[1] ] = true ;
for(int i = 2 ; i < N ; i++ )
{
if(foundPlace[ arr[i] ] ) continue ;
for(int j = 0 ; j < N ; j++ ) vis[j] = false ;
decompose( arr[i] , arr[0] ) ;
foundPlace[ arr[i] ] = true ;
}
for(int i = 0 ; i < N ; i++ )
for(auto e : adj[i] )
if( i < e ) Bridge(i, e) ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
0 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
0 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
0 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
0 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
0 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
10 ms |
364 KB |
Output is correct |
28 |
Correct |
10 ms |
384 KB |
Output is correct |
29 |
Correct |
10 ms |
364 KB |
Output is correct |
30 |
Correct |
9 ms |
364 KB |
Output is correct |
31 |
Correct |
8 ms |
364 KB |
Output is correct |
32 |
Correct |
7 ms |
364 KB |
Output is correct |
33 |
Correct |
11 ms |
364 KB |
Output is correct |
34 |
Correct |
11 ms |
364 KB |
Output is correct |
35 |
Correct |
10 ms |
364 KB |
Output is correct |
36 |
Correct |
9 ms |
364 KB |
Output is correct |
37 |
Correct |
12 ms |
492 KB |
Output is correct |
38 |
Correct |
13 ms |
492 KB |
Output is correct |
39 |
Correct |
11 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
883 ms |
748 KB |
Output is correct |
2 |
Correct |
936 ms |
876 KB |
Output is correct |
3 |
Correct |
889 ms |
912 KB |
Output is correct |
4 |
Correct |
900 ms |
748 KB |
Output is correct |
5 |
Correct |
598 ms |
876 KB |
Output is correct |
6 |
Correct |
470 ms |
748 KB |
Output is correct |
7 |
Correct |
595 ms |
748 KB |
Output is correct |
8 |
Correct |
649 ms |
1004 KB |
Output is correct |
9 |
Correct |
741 ms |
888 KB |
Output is correct |
10 |
Correct |
704 ms |
1004 KB |
Output is correct |
11 |
Correct |
778 ms |
892 KB |
Output is correct |
12 |
Correct |
694 ms |
848 KB |
Output is correct |
13 |
Correct |
833 ms |
964 KB |
Output is correct |
14 |
Correct |
1838 ms |
972 KB |
Output is correct |
15 |
Correct |
1598 ms |
952 KB |
Output is correct |
16 |
Correct |
1671 ms |
876 KB |
Output is correct |
17 |
Correct |
692 ms |
748 KB |
Output is correct |
18 |
Correct |
1582 ms |
1004 KB |
Output is correct |
19 |
Correct |
1517 ms |
1004 KB |
Output is correct |
20 |
Correct |
1769 ms |
960 KB |
Output is correct |
21 |
Correct |
1973 ms |
1004 KB |
Output is correct |
22 |
Correct |
1963 ms |
876 KB |
Output is correct |
23 |
Correct |
1924 ms |
1076 KB |
Output is correct |
24 |
Correct |
1904 ms |
1016 KB |
Output is correct |
25 |
Correct |
1753 ms |
876 KB |
Output is correct |
26 |
Correct |
1715 ms |
748 KB |
Output is correct |
27 |
Correct |
1790 ms |
876 KB |
Output is correct |
28 |
Correct |
821 ms |
876 KB |
Output is correct |
29 |
Correct |
695 ms |
748 KB |
Output is correct |
30 |
Correct |
728 ms |
876 KB |
Output is correct |
31 |
Correct |
768 ms |
1004 KB |
Output is correct |
32 |
Correct |
850 ms |
1144 KB |
Output is correct |
33 |
Correct |
730 ms |
1004 KB |
Output is correct |
34 |
Correct |
10 ms |
364 KB |
Output is correct |
35 |
Correct |
9 ms |
364 KB |
Output is correct |
36 |
Correct |
11 ms |
364 KB |
Output is correct |
37 |
Correct |
9 ms |
364 KB |
Output is correct |
38 |
Correct |
8 ms |
364 KB |
Output is correct |
39 |
Correct |
7 ms |
364 KB |
Output is correct |
40 |
Correct |
11 ms |
364 KB |
Output is correct |
41 |
Correct |
11 ms |
364 KB |
Output is correct |
42 |
Correct |
10 ms |
364 KB |
Output is correct |
43 |
Correct |
8 ms |
364 KB |
Output is correct |
44 |
Correct |
12 ms |
492 KB |
Output is correct |
45 |
Correct |
12 ms |
492 KB |
Output is correct |
46 |
Correct |
11 ms |
492 KB |
Output is correct |
47 |
Correct |
1 ms |
364 KB |
Output is correct |
48 |
Correct |
1 ms |
384 KB |
Output is correct |
49 |
Correct |
1 ms |
364 KB |
Output is correct |
50 |
Correct |
1 ms |
364 KB |
Output is correct |
51 |
Correct |
1 ms |
364 KB |
Output is correct |
52 |
Correct |
1 ms |
364 KB |
Output is correct |
53 |
Correct |
1 ms |
364 KB |
Output is correct |
54 |
Correct |
1 ms |
364 KB |
Output is correct |
55 |
Correct |
1 ms |
364 KB |
Output is correct |
56 |
Correct |
1 ms |
364 KB |
Output is correct |
57 |
Correct |
1 ms |
364 KB |
Output is correct |
58 |
Correct |
1 ms |
364 KB |
Output is correct |
59 |
Correct |
1 ms |
364 KB |
Output is correct |
60 |
Correct |
0 ms |
384 KB |
Output is correct |
61 |
Correct |
0 ms |
364 KB |
Output is correct |
62 |
Correct |
1 ms |
364 KB |
Output is correct |
63 |
Correct |
0 ms |
364 KB |
Output is correct |
64 |
Correct |
0 ms |
364 KB |
Output is correct |
65 |
Correct |
1 ms |
364 KB |
Output is correct |
66 |
Correct |
0 ms |
364 KB |
Output is correct |
67 |
Correct |
1 ms |
364 KB |
Output is correct |
68 |
Correct |
0 ms |
364 KB |
Output is correct |
69 |
Correct |
0 ms |
364 KB |
Output is correct |
70 |
Correct |
0 ms |
364 KB |
Output is correct |
71 |
Correct |
1 ms |
364 KB |
Output is correct |
72 |
Correct |
1 ms |
364 KB |
Output is correct |