| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 725087 |
2023-04-16T20:34:21 Z |
FatihSolak |
ICC (CEOI16_icc) |
C++17 |
|
116 ms |
644 KB |
#include <bits/stdc++.h>
#include "icc.h"
#define N 105
using namespace std;
vector<int> adj[N];
vector<int> group[N];
bool ban[N][N];
bool vis[N];
int cnt = 0;
void run(int n){
function<void(int)> dfs = [&](int v)->void{
vis[v] = 1;
group[cnt].push_back(v);
for(auto u:adj[v]){
if(!vis[u])
dfs(u);
}
};
for(int it = 1;it<n;it++){
vector<vector<int>> l,r;
vector<int> tmpl,tmpr;
for(int i = 1;i<=n;i++){
if(!vis[i]){
cnt++;
dfs(i);
if(tmpl.size() < tmpr.size())
tmpl.push_back(cnt);
else tmpr.push_back(cnt);
}
}
l.push_back(tmpl);
r.push_back(tmpr);
while(1){
int maxi = 0;
for(auto &u:l)
maxi = max(maxi,(int)u.size());
for(auto &u:r)
maxi = max(maxi,(int)u.size());
if(maxi == 1)break;
tmpl.clear();
tmpr.clear();
for(auto &u:l){
for(auto c:u){
for(auto x:group[c]){
tmpl.push_back(x);
}
}
}
for(auto &u:r){
for(auto c:u){
for(auto x:group[c]){
tmpr.push_back(x);
}
}
}
if(query(tmpl.size(),tmpr.size(),tmpl.data(),tmpr.data()))
break;
for(auto &u:l){
for(auto c:u){
for(auto &x:r){
for(auto y:x){
ban[c][y] = 1;
ban[y][c] = 1;
}
}
}
}
vector<vector<int>> nwl,nwr;
int lsize = 0;
int rsize = 0;
for(auto &u:l){
if(u.size() == 1)
continue;
tmpl.clear();
tmpr.clear();
for(auto c:u){
if(tmpl.size() < tmpr.size())
tmpl.push_back(c);
else tmpr.push_back(c);
}
if(lsize < rsize){
nwl.push_back(tmpr);
nwr.push_back(tmpl);
lsize += tmpr.size();
rsize += tmpl.size();
}
else{
nwl.push_back(tmpl);
nwr.push_back(tmpr);
lsize += tmpl.size();
rsize += tmpr.size();
}
}
for(auto &u:r){
if(u.size() == 1)
continue;
tmpl.clear();
tmpr.clear();
for(auto c:u){
if(tmpl.size() < tmpr.size())
tmpl.push_back(c);
else tmpr.push_back(c);
}
if(lsize < rsize){
nwl.push_back(tmpr);
nwr.push_back(tmpl);
lsize += tmpr.size();
rsize += tmpl.size();
}
else{
nwl.push_back(tmpl);
nwr.push_back(tmpr);
lsize += tmpl.size();
rsize += tmpr.size();
}
}
l = nwl;
r = nwr;
}
vector<int> ll,rr;
for(auto &u:l){
for(auto c:u){
ll.push_back(c);
}
}
while(ll.size() > 1){
vector<int> a,b;
for(auto c:ll){
if(a.size() < b.size())
a.push_back(c);
else b.push_back(c);
}
tmpl.clear();
tmpr.clear();
for(auto u:a){
for(auto x:group[u]){
tmpl.push_back(x);
}
}
for(auto &u:r){
for(auto c:u){
for(auto x:group[c]){
tmpr.push_back(x);
}
}
}
if(query(tmpl.size(),tmpr.size(),tmpl.data(),tmpr.data())){
ll = a;
}
else ll = b;
}
for(auto &u:r){
for(auto c:u){
if(ban[ll[0]][c])continue;
rr.push_back(c);
}
}
while(rr.size() > 1){
vector<int> a,b;
for(auto c:rr){
if(a.size() < b.size())
a.push_back(c);
else b.push_back(c);
}
tmpl.clear();
tmpr.clear();
for(auto u:ll){
for(auto x:group[u]){
tmpl.push_back(x);
}
}
for(auto c:a){
for(auto x:group[c]){
tmpr.push_back(x);
}
}
if(query(tmpl.size(),tmpr.size(),tmpl.data(),tmpr.data())){
rr = a;
}
else rr = b;
}
ll = group[ll[0]];
rr = group[rr[0]];
while(ll.size() > 1){
vector<int> a,b;
for(auto c:ll){
if(a.size() < b.size())
a.push_back(c);
else b.push_back(c);
}
if(query(a.size(),rr.size(),a.data(),rr.data())){
ll = a;
}
else ll = b;
}
while(rr.size() > 1){
vector<int> a,b;
for(auto c:rr){
if(a.size() < b.size())
a.push_back(c);
else b.push_back(c);
}
if(query(ll.size(),a.size(),ll.data(),a.data())){
rr = a;
}
else rr = b;
}
setRoad(ll[0],rr[0]);
adj[ll[0]].push_back(rr[0]);
adj[rr[0]].push_back(ll[0]);
for(int i = 1;i<=n;i++){
vis[i] = 0;
}
for(int i = 1;i<=cnt;i++){
for(int j = 1;j<=cnt;j++){
ban[i][j] = 0;
}
group[i].clear();
}
cnt = 0;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
468 KB |
Ok! 113 queries used. |
| 2 |
Correct |
6 ms |
504 KB |
Ok! 110 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
512 KB |
Ok! 624 queries used. |
| 2 |
Correct |
24 ms |
436 KB |
Ok! 455 queries used. |
| 3 |
Correct |
33 ms |
508 KB |
Ok! 477 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
516 KB |
Ok! 1533 queries used. |
| 2 |
Correct |
92 ms |
544 KB |
Ok! 1116 queries used. |
| 3 |
Correct |
96 ms |
524 KB |
Ok! 1467 queries used. |
| 4 |
Correct |
99 ms |
468 KB |
Ok! 1491 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
468 KB |
Ok! 1433 queries used. |
| 2 |
Correct |
96 ms |
468 KB |
Ok! 1433 queries used. |
| 3 |
Correct |
97 ms |
536 KB |
Ok! 1325 queries used. |
| 4 |
Correct |
104 ms |
644 KB |
Ok! 1493 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
608 KB |
Ok! 1245 queries used. |
| 2 |
Correct |
93 ms |
520 KB |
Ok! 1337 queries used. |
| 3 |
Correct |
94 ms |
516 KB |
Ok! 1200 queries used. |
| 4 |
Correct |
100 ms |
540 KB |
Ok! 1375 queries used. |
| 5 |
Correct |
116 ms |
636 KB |
Ok! 1524 queries used. |
| 6 |
Correct |
99 ms |
512 KB |
Ok! 1549 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
468 KB |
Ok! 1412 queries used. |
| 2 |
Correct |
90 ms |
528 KB |
Ok! 1206 queries used. |
