| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131187 |
2019-07-16T18:33:43 Z |
zubec |
ICC (CEOI16_icc) |
C++14 |
|
0 ms |
0 KB |
//#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
*/
Compilation message
icc.cpp: In function 'int my_query(std::vector<int>&, std::vector<int>&)':
icc.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec1.size(); i++)
~~^~~~~~~~~~~~~
icc.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec2.size(); i++)
~~^~~~~~~~~~~~~
icc.cpp:41:12: error: 'query' was not declared in this scope
return query(sz1, sz2, A, B);
^~~~~
icc.cpp:41:12: note: suggested alternative: 'my_query'
return query(sz1, sz2, A, B);
^~~~~
my_query
icc.cpp: In function 'void run(int)':
icc.cpp:81:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++){
~~^~~~~~~~~~~~
icc.cpp:83:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:86:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:111:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++){
~~^~~~~~~~~~~~
icc.cpp:113:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:117:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:126:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++){
~~^~~~~~~~~~~~
icc.cpp:128:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:132:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:174:13: error: 'setRoad' was not declared in this scope
setRoad(a, b);
^~~~~~~
