| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 131187 | zubec | ICC (CEOI16_icc) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef __WIN32
int gg[110][110], ptr;
pair < int, int > edg[110];
void setRoad(int a, int b){
++ptr;
cout << a << ' ' << b << endl;
int x = edg[ptr].first, y = edg[ptr].second;
gg[x][y] = gg[y][x] = 1;
}
int query(int a, int b, int *A, int *B){
for (int i = 0; i < a; ++i){
for (int j = 0; j < b; ++j){
if (gg[A[i]][B[j]])return 1;
}
}
return 0;
}
#endif // __WIN32
int n;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int sz1, sz2, A[110], B[110];
int my_query(vector<int> &vec1, vector <int> &vec2){
sz1 = sz2 = 0;
for (int i = 0; i < vec1.size(); i++)
A[sz1++] = vec1[i];
for (int i = 0; i < vec2.size(); i++)
B[sz2++] = vec2[i];
return query(sz1, sz2, A, B);
}
int dsu[110];
int dsu_get(int v){
if (v == dsu[v])
return v;
return dsu[v] = dsu_get(dsu[v]);
}
void dsu_unite(int a, int b){
a = dsu_get(a);
b = dsu_get(b);
dsu[b] = a;
}
vector <int> g[110];
void run(int N){
n = N;
for (int i = 1; i <= n; i++){
dsu[i] = i;
}
for (int tt = 1; tt < n; tt++){
vector <int> vec;
for (int i = 1; i <= n; i++)
g[i].clear();
for (int i = 1; i <= n; i++){
vec.push_back(dsu_get(i));
g[dsu_get(i)].push_back(i);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
while(1){
int mask = 0;
int lst = 0;
int sz = 0;
for (int bt = 0; ; bt++){
vector <int> vec1, vec2;
for (int j = 0; j < vec.size(); j++){
if (vec[j] & (1<<bt)){
for (int l = 0; l < g[vec[j]].size(); l++)
vec1.push_back(g[vec[j]][l]);
} else {
for (int l = 0; l < g[vec[j]].size(); l++)
vec2.push_back(g[vec[j]][l]);
}
}
if (vec1.empty() || vec2.empty())
break;
sz = bt;
/*cout << "kek " << bt << endl;
for (int j = 0; j < vec1.size(); j++)
cout << vec1[j] << ' ';
cout << endl;
for (int j = 0; j < vec2.size(); j++)
cout << vec2[j] << ' ';
cout << endl;*/
if (my_query(vec1, vec2)){
mask |= (1<<bt);
lst = bt;
}
}
int mask1 = 0, mask2 = (1<<lst);
for (int bt = sz; bt >= 0; bt--){
if (bt == lst)
continue;
if (mask & (1<<bt)){
vector <int> vec1, vec2;
for (int j = 0; j < vec.size(); j++){
if ((vec[j] & (1<<bt)) && (vec[j] & (1<<lst))){
for (int l = 0; l < g[vec[j]].size(); l++)
vec1.push_back(g[vec[j]][l]);
} else
if (!(vec[j] & (1<<bt)) && !(vec[j] & (1<<lst))){
for (int l = 0; l < g[vec[j]].size(); l++)
vec2.push_back(g[vec[j]][l]);
}
}
if (vec1.empty() || vec2.empty() || !my_query(vec1, vec2))
mask1 |= (1<<bt); else
mask2 |= (1<<bt);
} else {
vector <int> vec1, vec2;
for (int j = 0; j < vec.size(); j++){
if (!(vec[j] & (1<<bt)) && (vec[j] & (1<<lst))){
for (int l = 0; l < g[vec[j]].size(); l++)
vec1.push_back(g[vec[j]][l]);
} else
if (!(vec[j] & (1<<bt)) && !(vec[j] & (1<<lst))){
for (int l = 0; l < g[vec[j]].size(); l++)
vec2.push_back(g[vec[j]][l]);
}
}
if (vec1.empty() || vec2.empty() || !my_query(vec1, vec2)){
mask1 |= (1<<bt);
mask2 |= (1<<bt);
}
}
}
vector <int> vec1 = g[mask1], vec2 = g[mask2];
/*cout << mask1 << ' ' << mask2 << ' ' << mask << endl;
cout << "kek " << vec1.size() << ' ' << vec2.size() << endl;
for (int j = 0; j < vec1.size(); j++)
cout << vec1[j] << ' ';
cout << endl;
for (int j = 0; j < vec2.size(); j++)
cout << vec2[j] << ' ';
cout << endl;*/
int l = 0, r = vec1.size()-1;
while(l < r){
int mid = (l+r)>>1;
vector <int> cur;
for (int j = l; j <= mid; j++)
cur.push_back(vec1[j]);
if (my_query(cur, vec2))
r = mid; else
l = mid+1;
}
int a = vec1[l];
l = 0, r = vec2.size();
while(l < r){
int mid = (l+r)>>1;
vector <int> cur;
for (int j = l; j <= mid; j++)
cur.push_back(vec2[j]);
if (my_query(vec1, cur))
r = mid; else
l = mid+1;
}
int b = vec2[l];
setRoad(a, b);
dsu_unite(a, b);
break;
}
}
}
#ifdef __WIN32
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++){
cin >> edg[i].first >> edg[i].second;
}
gg[edg[1].first][edg[1].second] = gg[edg[1].second][edg[1].first] = 1;
ptr = 1;
run(n);
}
#endif // __WIN32
/**
4
2 4
1 3
1 4
*/