| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1117175 |
2024-11-22T21:29:06 Z |
mmk |
ICC (CEOI16_icc) |
C++14 |
|
338 ms |
1276 KB |
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
const int MAXN = 110;
int pai[MAXN], marc[MAXN], sz[MAXN];
map<pair<int,int>,bool> aresta;
// int query(int sza, int szb, int a[], int b[]);
// int setRoad(int a, int b);
// srand(time(0));
int q(vector<int> a, vector<int> b)
{
if(a.size() == 0 || b.size() == 0) return false;
int sza = a.size(), szb = b.size();
for(int v : a)
{
for(int viz : b)
if(aresta[{v,viz}]) return 1;
}
int novoA[sza], novoB[szb];
for(int i = 0; i < sza; i++)
novoA[i] = a[i];
for(int i = 0; i < szb; i++)
novoB[i] = b[i];
return query(sza, szb, novoA, novoB);
}
int find(int v)
{
if(pai[v] == v) return v;
return pai[v] = find(pai[v]);
}
void un(int a, int b)
{
a = find(a);
b = find(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a,b);
pai[b] = a;
sz[a] += sz[b];
}
vector<int> botaGrupo(int v, int N)
{
vector<int> grupo;
for(int i = 1; i <= N; i++)
{
if(find(i) == find(v))
grupo.push_back(i);
}
return grupo;
}
pair<vector<int>,vector<int>> split(vector<int> v, int N)
{
int sz = v.size();
int qtdA = 0, qtdB = 0;
for(int i = 1; i <= N; i++)
marc[i] = 0;
vector<int> a,b;
for(int i = 0; i < sz; i++)
{
if(marc[v[i]]) continue;
int grupo = rand()%2;
vector<int> adiciona = botaGrupo(v[i],N);
if(qtdA >= sz/2)
{
for(int cur : adiciona)
{
marc[cur] = 1;
b.push_back(cur);
}
qtdB++;
}
else if(qtdB >= sz/2)
{
for(int cur : adiciona)
{
marc[cur] = 1;
a.push_back(cur);
}
qtdA++;
}
else
{
for(int cur : adiciona)
{
marc[cur] = 1;
if(grupo == 0) a.push_back(cur);
else b.push_back(cur);
}
if(grupo == 0) qtdA++;
else qtdB++;
}
}
return make_pair(a,b);
}
pair<vector<int>,vector<int>> split2(vector<int> v, int N)
{
int sz = v.size();
int qtdA = 0, qtdB = 0;
vector<int> a,b;
for(int i = 0; i < sz; i++)
{
int grupo = rand()%2;
int cur = v[i];
if(qtdA >= sz/2)
{
b.push_back(cur);
qtdB++;
}
else if(qtdB >= sz/2)
{
a.push_back(cur);
qtdB++;
}
else
{
if(grupo == 0) a.push_back(cur);
else b.push_back(cur);
if(grupo == 0) qtdA++;
else qtdB++;
}
}
return make_pair(a,b);
}
pair<vector<int>,vector<int>> achaAresta(int N)
{
vector<int> todos;
for(int i = 1; i <= N; i++)
todos.push_back(i);
pair<vector<int>,vector<int>> temp = split(todos,N);
vector<int> a,b;
a = temp.first, b = temp.second;
// cerr << "grupo1: ";
// for(int cur : a) cerr << cur << " ";
// cerr << "\n";
// cerr << "grupo2: ";
// for(int cur : b) cerr << cur << " ";
// cerr << "\n";
vector<int> aux;
if(q(a,b)) return {a,b};
else return {aux,aux};
}
vector<int> achaGrupoPonta(vector<int> a, vector<int> b, int N)
{
vector<int> nulo;
if(a.size() == 0 || b.size() == 0)
return nulo;
int grupoA = find(a[0]);
bool mesmo = true;
for(int cur : a)
{
if(find(cur) != grupoA)
mesmo = false;
}
if(mesmo)
return a;
vector<int> half1, half2;
pair<vector<int>,vector<int>> temp = split(a,N);
half1 = temp.first, half2 = temp.second;
if(q(half1,b))
return achaGrupoPonta(half1,b,N);
else
return achaGrupoPonta(half2,b,N);
}
int achaPonta(vector<int> a, vector<int> b, int N)
{
if(a.size() == 0)
return -1;
if(a.size() == 1)
return a[0];
vector<int> half1,half2;
pair<vector<int>,vector<int>> temp = split2(a,N);
half1 = temp.first, half2 = temp.second;
if(q(half1,b)) return achaPonta(half1,b,N);
return achaPonta(half2,b,N);
}
void run(int N)
{
int cnt = N - 1;
for(int i = 1; i <= N; i++)
{
pai[i] = i;
sz[i] = 1;
}
while(cnt--)
{
bool achou = false;
pair<vector<int>,vector<int>> aux;
while(!achou)
{
// cerr << "bonga\n";
aux = achaAresta(N);
if(aux.first.size() == 0 && aux.second.size() == 0)
continue;
else
achou = true;
}
// vector<int> grupoA = achaGrupoPonta(aux.first,aux.second,N);
// vector<int> grupoB = achaGrupoPonta(aux.second,aux.first,N);
int pontaA = achaPonta(aux.first,aux.second,N);
int pontaB = achaPonta(aux.second,aux.first,N);
setRoad(pontaA,pontaB);
un(pontaA,pontaB);
aresta[{pontaA,pontaB}] = 1;
aresta[{pontaB,pontaA}] = 1;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
592 KB |
Ok! 109 queries used. |
| 2 |
Correct |
7 ms |
592 KB |
Ok! 99 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
592 KB |
Ok! 548 queries used. |
| 2 |
Correct |
57 ms |
592 KB |
Ok! 864 queries used. |
| 3 |
Correct |
54 ms |
804 KB |
Ok! 858 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
1260 KB |
Ok! 1499 queries used. |
| 2 |
Correct |
338 ms |
1252 KB |
Ok! 2175 queries used. |
| 3 |
Correct |
177 ms |
1264 KB |
Ok! 1625 queries used. |
| 4 |
Correct |
198 ms |
1104 KB |
Ok! 1708 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
1260 KB |
Ok! 1614 queries used. |
| 2 |
Correct |
204 ms |
1264 KB |
Ok! 1657 queries used. |
| 3 |
Correct |
280 ms |
1276 KB |
Ok! 1899 queries used. |
| 4 |
Correct |
179 ms |
1272 KB |
Ok! 1591 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
253 ms |
1104 KB |
Too many queries! 1911 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
310 ms |
1104 KB |
Too many queries! 1991 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
