//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;
multiset<int> g[2000];
int cs[2000];
bool blk[2000][2000] , ms[2000];
vector<arr(2)> blks;
//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 Solve(int N){
n = N;
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;
g[x].insert(v) , g[x].insert(u) , g[v].insert(x) , g[u].insert(x);
}else{
ms[x] = 1;
for(int v = 0 ; v < 3 ; v++) g[v].insert(x) , g[x].insert(v);
}
for(int v = 3 ; v < n ; v++){
if(!g[v].empty()) continue;
int r = 0;
sz = n;
while(sz > 1){
dfs1(r , -1);
int c = getCnt(r , -1);
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];
blk[c][ord[i][1]] = 1 , blk[ord[i][1]][c] = 1;
blks.pb({c , ord[i][1]});
break;
}else if(x == c){
sz = 0 , r = c;
}else if(x == v){
sz = 0 , r = -1 , g[c].erase(ord[i][1]) , g[ord[i][1]].erase(c);
g[c].insert(v) , g[v].insert(c) , g[v].insert(ord[i][1]) , g[ord[i][1]].insert(v);
}else{
sz = 0 , r = -1 , g[c].erase(ord[i][1]) , g[ord[i][1]].erase(c);
g[x].insert(v) , g[x].insert(ord[i][1]) , g[x].insert(c);
g[v].insert(x) , g[ord[i][1]].insert(x) , g[c].insert(x);
ms[x] = 1;
}
}else{
auto u = ord[i] , w = ord[i + 1];
int x = Query(v , u[1] , w[1]);
if(x == u[1]){
sz = u[0] , r = u[1];
blk[c][u[1]] = 1 , blk[u[1]][c] = 1;
blks.pb({c , u[1]});
break;
}else if(x == w[1]){
sz = w[0] , r = w[1];
blk[c][w[1]] = 1 , blk[w[1]][c] = 1;
blks.pb({c , w[1]});
break;
}else if(x == c){
if(i < (int)ord.size() - 2) continue;
sz = 0 , r = c;
}else if(x == v){
sz = 0 , r = -1;
int xx = Query(c , v , u[1]);
if(xx == v){
g[c].erase(u[1]) , g[u[1]].erase(c);
g[v].insert(u[1]) , g[v].insert(c) , g[c].insert(v) , g[u[1]].insert(v);
}else{
g[c].erase(w[1]) , g[w[1]].erase(c);
g[v].insert(w[1]) , g[v].insert(c) , g[c].insert(v) , g[w[1]].insert(v);
}
}else{
int xx = Query(c , x , u[1]);
sz = 0 , r = -1;
if(xx == x){
g[c].erase(u[1]) , g[u[1]].erase(c);
g[x].insert(u[1]) , g[x].insert(v) , g[x].insert(c);
g[u[1]].insert(x) , g[v].insert(x) , g[c].insert(x);
}else{
g[c].erase(w[1]) , g[w[1]].erase(c);
g[x].insert(w[1]) , g[x].insert(v) , g[x].insert(c);
g[w[1]].insert(x) , g[v].insert(x) , g[c].insert(x);
}
ms[x] = 1;
}
}
}
}
if(r != -1) g[r].insert(v) , g[v].insert(r);
for(auto b : blks){
blk[b[0]][b[1]] = 0;
blk[b[1]][b[0]] = 0;
}
blks.cl();
}
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 |
1 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 |
344 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 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 |
344 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
600 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
600 KB |
Wrong Answer [1] |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 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 |
344 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
600 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
600 KB |
Wrong Answer [1] |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
217 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
