| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58419 |
2018-07-17T19:28:24 Z |
MatheusLealV |
ICC (CEOI16_icc) |
C++17 |
|
225 ms |
920 KB |
#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] ++;
}
}
pii Find_Pair(vector<int> esq, vector<int> dir)
{
//cout<<ni<<" "<<esq.size()<<" "<<dir.size()<<"\n";
int ini = 0, fim = dir.size() - 1, mid, best1 = -1, best2 = -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() - 1, 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;
}
//cout<<"ACHEI "<<best1<<" "<<best2<<"\n";
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);
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);
}
}
pii P = Find_Pair(esq, dir);
if(P.f != -1 and P.s != -1)
{
// cout<<"ROAD "<<P.f<<" "<<P.s<<"\n";
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:54: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:56: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:78:39: warning: right operand of comma operator has no effect [-Wunused-value]
ini = 0, fim = esq.size() - 1, mid;
^
icc.cpp:82: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:52: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:127:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < val.size(); i++)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
504 KB |
Ok! 104 queries used. |
| 2 |
Correct |
13 ms |
612 KB |
Ok! 107 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
612 KB |
Ok! 548 queries used. |
| 2 |
Correct |
65 ms |
744 KB |
Ok! 691 queries used. |
| 3 |
Correct |
58 ms |
744 KB |
Ok! 664 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
197 ms |
744 KB |
Ok! 1519 queries used. |
| 2 |
Correct |
191 ms |
744 KB |
Ok! 1710 queries used. |
| 3 |
Correct |
221 ms |
756 KB |
Ok! 1633 queries used. |
| 4 |
Correct |
176 ms |
756 KB |
Ok! 1548 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
201 ms |
784 KB |
Ok! 1540 queries used. |
| 2 |
Correct |
160 ms |
784 KB |
Ok! 1519 queries used. |
| 3 |
Correct |
197 ms |
848 KB |
Ok! 1683 queries used. |
| 4 |
Correct |
177 ms |
848 KB |
Ok! 1530 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
848 KB |
Ok! 1680 queries used. |
| 2 |
Correct |
199 ms |
848 KB |
Ok! 1683 queries used. |
| 3 |
Correct |
178 ms |
852 KB |
Ok! 1683 queries used. |
| 4 |
Correct |
225 ms |
852 KB |
Ok! 1703 queries used. |
| 5 |
Correct |
163 ms |
852 KB |
Ok! 1511 queries used. |
| 6 |
Correct |
190 ms |
852 KB |
Ok! 1569 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
198 ms |
920 KB |
Too many queries! 1683 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
