//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
int n , sz;
set<int> g[2000];
int cs[2000];
bool blk[2000][2000] , ms[2000];
vector<arr(2)> blks;
int cnt = 0;
//int Query(int v , int u , int w){
// cout << "Q : {" << v << " , " << u << " , " << w << "}\n";
// int res;
// cin >> res;
// return res;
//}
//void Bridge(int v , int u){
// cout << "There is an edge between " << v << " and " << u << ".\n";
// string res;
// cin >> res;
// if(res == "no") exit(0);
//}
void dfs1(int v , int p){
cs[v] = 1;
for(int u : g[v]){
if(blk[v][u] or u == p) continue;
dfs1(u , v) , cs[v] += cs[u];
}
}
int getCnt(int v , int p){
for(int u : g[v]){
if(blk[v][u] or u == p) continue;
if(cs[u] > sz / 2) return getCnt(u , v);
}
return v;
}
void connect(int v , int u){
g[v].insert(u) , g[u].insert(v);
}
void addIn(int v , int w , int u){
g[v].erase(w) , g[w].erase(v);
connect(v , u) , connect(w , u);
}
void setBlk(int v , int u , bool vl){
blk[v][u] = vl , blk[u][v] = vl;
if(vl) blks.pb({v , u});
}
void Solve(int N){
n = N , cnt = 3;
int x = Query(0 , 1 , 2);
if(x >= 0 and x <= 2){
int v = 0 , u = 1;
if(3 - x == 2) u = 2;
if(3 - x == 3) v = 2;
connect(x , v) , connect(x , u);
}else{
ms[x] = 1 , cnt++;
for(int v = 0 ; v < 3 ; v++) connect(x , v);
}
for(int v = 3 ; v < n ; v++){
if(!g[v].empty()) continue;
int r = 0;
sz = cnt;
while(sz > 1){
// cout << sz << "#\n" << flush;
// if(sz == 8){
// for(int i = 0 ; i < n ; i++){
// if(g[i].empty()) continue;
// cout << i << " : ";
// for(int u : g[i]) cout << u << " , ";
// cout << "||\n" << flush;
// }
// }
dfs1(r , -1);
int c = getCnt(r , -1);
// cout << "Centroid is " << c << ".\n";
vector<arr(2)> ord;
for(int u : g[c]){
if(blk[c][u]) continue;
if(cs[u] > cs[c]) ord.pb({cs[u] - cs[c] , u});
else ord.pb({cs[u] , u});
}
sort(ord.bg() , ord.end() , [](arr(2) a , arr(2) b){
return (a[0] > b[0]);
});
for(int i = 0 ; i < (int)ord.size() ; i += 2){
if(i == (int)ord.size() - 1){
int x = Query(ord[i][1] , c , v);
if(x == ord[i][1]){
sz = ord[i][0] , r = ord[i][1] , setBlk(c , ord[i][1] , 1);
break;
}else{
sz = 0 , r = -1;
if(x == c) r = c;
else if(x == v) addIn(c , ord[i][1] , v);
else{
ms[x] = 1 , cnt++ , addIn(c , ord[i][1] , x) , connect(x , v);
}
}
}else{
auto u = ord[i] , w = ord[i + 1];
int x = Query(v , u[1] , w[1]);
sz = 0 , r = -1;
if(x == u[1] or x == w[1]){
sz = u[0] , r = x , setBlk(c , x , 1);
if(x == w[1]) sz = w[0];
break;
}else if(x == c){
if(i < (int)ord.size() - 2) continue;
r = c;
}else if(x == v){
if(Query(c , v , u[1]) == v) addIn(c , u[1] , v);
else addIn(c , w[1] , v);
break;
}else{
ms[x] = 1 , cnt++;
if(Query(c , x , u[1]) == x){
addIn(c , u[1] , x) , connect(x , v);
}else{
addIn(c , w[1] , x) , connect(x , v);
}
break;
}
}
}
// cout << "L\n" << flush;
}
if(r != -1) connect(r , v);
for(auto b : blks) setBlk(b[0] , b[1] , 0);
blks.cl() , cnt++;
// cout << "_____\n" << flush;
}
for(int v = 0 ; v < n ; v++){
for(int u : g[v]){
if(u > v) continue;
Bridge(u , v);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
600 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
600 KB |
Wrong Answer [4] |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
600 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
600 KB |
Wrong Answer [4] |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
600 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
600 KB |
Wrong Answer [4] |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
253 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
