#include "icc.h"
#define N 105
#define f first
#define s second
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
set<int> grafo[N];
int pai[N], peso[N], ni;
vector<int> el[N];
int Find(int x)
{
if(x == pai[x]) return x;
return pai[x] = Find(pai[x]);
}
void join(int a, int b)
{
a = Find(a), b = Find(b);
if(a == b) return;
if(peso[a] > peso[b])
{
pai[b] = a;
for(auto x: el[b]) el[a].push_back(x);
}
else if(peso[a] <= peso[b])
{
pai[a] = b;
for(auto x: el[a]) el[b].push_back(x);
if(peso[a] == peso[b]) peso[b] ++;
}
}
inline pii Find_Pair(vector<int> esq, vector<int> dir)
{
int ini = 0, fim = dir.size() - 2, mid, best1 = dir.size() - 1, best2 = esq.size() - 1;
int A[N], idl = 0, aux[N], idaux = 0;
for(int i = 0; i < esq.size(); i++) A[idl] = esq[i], idl ++;
for(int i = 0; i < dir.size(); i++) aux[i] = dir[i];
if(!query((int)esq.size(), (int) dir.size(), A, aux)) return {-1, -1};
while(fim >= ini)
{
mid = (ini + fim)/2;
int B[N], idr = 0;
for(int i = 0; i <= mid; i++) B[idr] = dir[i], idr ++;
if(query(idl, idr, A, B))
{
best1 = mid;
fim = mid - 1;
}
else ini = mid + 1;
}
ini = 0, fim = esq.size() - 2, mid;
idl = 0;
for(int i = 0; i < dir.size(); i++) A[idl] = dir[i], idl ++;
while(fim >= ini)
{
mid = (ini + fim)/2;
int B[N], idr = 0;
for(int i = 0; i <= mid; i++) B[idr] = esq[i], idr ++;
if(query(idl, idr, A, B))
{
best2 = mid;
fim = mid - 1;
}
else ini = mid + 1;
}
if(best1 == -1 and best2 == -1) return {-1, -1};
return {dir[best1], esq[best2]};
}
void run(int n)
{
ni = n;
for(int i = 1; i <= n; i++) pai[i] = i, el[i].push_back(i);
for(int i = 1; i < n; i++)
{
set<int> aux; vector<int> val;
for(int i = 1; i <= n; i++) aux.insert(Find(i));
for(auto x: aux) val.push_back(x);
vector<int> bits;
for(int k = 0; k < 7; k++)
{
vector<int> esq, dir;
for(int i = 0; i < val.size(); i++)
{
if(i & (1<<k))
{
int x = val[i];
for(auto v: el[x]) esq.push_back(v);
}
else
{
int x = val[i];
for(auto v: el[x]) dir.push_back(v);
}
}
if(esq.size() == 0 or dir.size() == 0) continue;
pii P = Find_Pair(esq, dir);
if(P.f != -1 and P.s != -1)
{
setRoad(P.f, P.s);
join(P.f, P.s);
break;
}
}
}
}
Compilation message
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
#define s second
^
icc.cpp: In function 'pii Find_Pair(std::vector<int>, std::vector<int>)':
icc.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < esq.size(); i++) A[idl] = esq[i], idl ++;
~~^~~~~~~~~~~~
icc.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < dir.size(); i++) aux[i] = dir[i];
~~^~~~~~~~~~~~
icc.cpp:75:39: warning: right operand of comma operator has no effect [-Wunused-value]
ini = 0, fim = esq.size() - 2, mid;
^
icc.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < dir.size(); i++) A[idl] = dir[i], idl ++;
~~^~~~~~~~~~~~
icc.cpp:49:32: warning: unused variable 'idaux' [-Wunused-variable]
int A[N], idl = 0, aux[N], idaux = 0;
^~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:124:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < val.size(); i++)
~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
504 KB |
Ok! 94 queries used. |
| 2 |
Correct |
9 ms |
652 KB |
Ok! 101 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
48 ms |
692 KB |
Ok! 542 queries used. |
| 2 |
Correct |
71 ms |
692 KB |
Ok! 687 queries used. |
| 3 |
Correct |
58 ms |
784 KB |
Ok! 681 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
172 ms |
820 KB |
Ok! 1471 queries used. |
| 2 |
Correct |
210 ms |
820 KB |
Ok! 1704 queries used. |
| 3 |
Correct |
196 ms |
820 KB |
Ok! 1592 queries used. |
| 4 |
Correct |
190 ms |
820 KB |
Ok! 1544 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
166 ms |
820 KB |
Ok! 1574 queries used. |
| 2 |
Correct |
210 ms |
820 KB |
Ok! 1583 queries used. |
| 3 |
Correct |
189 ms |
820 KB |
Ok! 1614 queries used. |
| 4 |
Correct |
159 ms |
820 KB |
Ok! 1497 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
185 ms |
828 KB |
Ok! 1615 queries used. |
| 2 |
Correct |
173 ms |
880 KB |
Ok! 1614 queries used. |
| 3 |
Correct |
231 ms |
880 KB |
Ok! 1614 queries used. |
| 4 |
Correct |
184 ms |
880 KB |
Ok! 1657 queries used. |
| 5 |
Correct |
159 ms |
880 KB |
Ok! 1486 queries used. |
| 6 |
Correct |
209 ms |
880 KB |
Ok! 1564 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
198 ms |
880 KB |
Ok! 1614 queries used. |
| 2 |
Incorrect |
202 ms |
892 KB |
Too many queries! 1704 out of 1625 |
