| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605858 |
2022-07-26T03:46:33 Z |
Je_O |
ICC (CEOI16_icc) |
C++17 |
|
145 ms |
628 KB |
#include "icc.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 105;
int par[N];
vector<int> cc[N];
int find(int x){
if(par[x] == x)return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x); y = find(y);
if(x == y)return;
if(cc[x].size() > cc[y].size())swap(x, y);
par[x] = y;
for(int i = 0; i < cc[x].size(); ++i){
cc[y].pb(cc[x][i]);
}
return;
}
vector<int> lst[N][2];
void build(int idx, int l, int r, int p){
if(l == r){
lst[idx][p].pb(l);
return;
}
if(idx > 1)for(int i = l; i <= r; ++i)lst[idx][p].pb(i);
int m = (l + r)/2;
build(idx + 1, l, m, 0);
build(idx + 1, m + 1, r, 1);
return;
}
vector<int> va, vb;
void add(int idx, int p){
if(p == 0){
for(int i = 0; i < cc[idx].size(); ++i){
va.pb(cc[idx][i]);
}
}else{
for(int i = 0; i < cc[idx].size(); ++i){
vb.pb(cc[idx][i]);
}
}
return;
}
int ask(int sz_a, int sz_b, vector<int> v_a, vector<int> v_b){
int ar_a[sz_a];
int ar_b[sz_b];
for(int i = 0; i < sz_a; ++i)ar_a[i] = v_a[i];
for(int i = 0; i < sz_b; ++i)ar_b[i] = v_b[i];
return query(sz_a, sz_b, ar_a, ar_b);
}
// bool path[N][N];
// int curid = 0;
// int uu[N], vv[N];
// int query(int sz_a, int sz_b, vector<int> v_a, vector<int> v_b){
// cout << v_a[0] << ' ' << v_b[0] << endl;
// for(int i = 0; i < sz_a; ++i){
// for(int j = 0; j < sz_b; ++j){
// if(path[v_a[i]][v_b[j]])return 1;
// }
// }
// return 0;
// }
// void setRoad(int a, int b){
// if((uu[curid] == a && vv[curid] == b) || (uu[curid] == b && vv[curid] == a)){
// cout << curid << ' ' << "true" << endl;
// }else{
// cout << a << ' ' << b << '\n';
// }
// return;
// }
void run(int n){
for(int i = 1; i <= n; ++i)par[i] = i;
for(int i = 1; i <= n; ++i)cc[i].pb(i);
for(int q = 1; q < n; ++q){
// path[uu[q]][vv[q]] = true;
// path[vv[q]][uu[q]] = true;
// ++curid;
vector<int> v;
for(int i = 1; i <= n; ++i){
if(find(i) == i)v.pb(i);
}
for(int i = 1; i <= n; ++i){
lst[i][0].clear(); lst[i][1].clear();
}
va.clear(); vb.clear();
build(1, 0, v.size() - 1, 0);
for(int i = 1; i <= n; ++i){
va.clear(); vb.clear();
for(int j = 0; j < lst[i][0].size(); ++j){
add(v[lst[i][0][j]], 0);
}
for(int j = 0; j < lst[i][1].size(); ++j){
add(v[lst[i][1][j]], 1);
}
int get = 0;
if(va.size() > 0 && vb.size() > 0)get = ask(va.size(), vb.size(), va, vb);
if(get == 1)break;
}
// cout << q << " -> ";
// for(int i = 0; i < va.size(); ++i)cout << va[i] << ' ';
// cout << endl;
// for(int i = 0; i < vb.size(); ++i)cout << vb[i] << ' ';
// cout << endl;
int l = 0, r = va.size() - 1;
while(l < r){
int m = (l + r)/2;
vector<int> cur_va;
for(int i = 0; i <= m; ++i){
cur_va.pb(va[i]);
}
int get = 0;
if(cur_va.size() > 0 && vb.size() > 0)get = ask(cur_va.size(), vb.size(), cur_va, vb);
if(get == 1){
r = m;
}else{
l = m + 1;
}
}
int ans_1 = va[l];
l = 0; r = vb.size() - 1;
while(l < r){
int m = (l + r)/2;
vector<int> cur_vb;
for(int i = 0; i <= m; ++i){
cur_vb.pb(vb[i]);
}
int get = 0;
if(va.size() > 0 && cur_vb.size() > 0)get = ask(va.size(), cur_vb.size(), va, cur_vb);
if(get == 1){
r = m;
}else{
l = m + 1;
}
}
int ans_2 = vb[l];
setRoad(ans_1, ans_2);
merge(ans_1, ans_2);
}
return;
}
// int main(){
// ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int n; cin >> n;
// for(int i = 1; i < n; ++i){
// cin >> uu[i] >> vv[i];
// }
// run(n);
// return 0;
// }
Compilation message
icc.cpp: In function 'void merge(int, int)':
icc.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i = 0; i < cc[x].size(); ++i){
| ~~^~~~~~~~~~~~~~
icc.cpp: In function 'void add(int, int)':
icc.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0; i < cc[idx].size(); ++i){
| ~~^~~~~~~~~~~~~~~~
icc.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0; i < cc[idx].size(); ++i){
| ~~^~~~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:110:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int j = 0; j < lst[i][0].size(); ++j){
| ~~^~~~~~~~~~~~~~~~~~
icc.cpp:113:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int j = 0; j < lst[i][1].size(); ++j){
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
468 KB |
Ok! 103 queries used. |
| 2 |
Correct |
8 ms |
468 KB |
Ok! 100 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
504 KB |
Ok! 528 queries used. |
| 2 |
Correct |
35 ms |
468 KB |
Ok! 562 queries used. |
| 3 |
Correct |
35 ms |
468 KB |
Ok! 588 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
496 KB |
Ok! 1441 queries used. |
| 2 |
Correct |
108 ms |
500 KB |
Ok! 1340 queries used. |
| 3 |
Correct |
145 ms |
500 KB |
Ok! 1545 queries used. |
| 4 |
Correct |
117 ms |
468 KB |
Ok! 1482 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
496 KB |
Ok! 1500 queries used. |
| 2 |
Correct |
110 ms |
468 KB |
Ok! 1506 queries used. |
| 3 |
Correct |
111 ms |
512 KB |
Ok! 1519 queries used. |
| 4 |
Correct |
108 ms |
468 KB |
Ok! 1489 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
512 KB |
Ok! 1502 queries used. |
| 2 |
Correct |
109 ms |
500 KB |
Ok! 1483 queries used. |
| 3 |
Correct |
109 ms |
500 KB |
Ok! 1514 queries used. |
| 4 |
Correct |
120 ms |
624 KB |
Ok! 1519 queries used. |
| 5 |
Correct |
109 ms |
512 KB |
Ok! 1492 queries used. |
| 6 |
Correct |
107 ms |
468 KB |
Ok! 1507 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
628 KB |
Ok! 1519 queries used. |
| 2 |
Correct |
108 ms |
504 KB |
Ok! 1483 queries used. |
