| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171825 |
2019-12-30T12:59:22 Z |
Tuk1352 |
ICC (CEOI16_icc) |
C++11 |
|
214 ms |
632 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
int P[101], S[101];
vector <int> V[101];
int Parent(int a)
{
if (P[a] == a)
{
return a;
}
return P[a] = Parent(P[a]);
}
void Union(int a, int b)
{
int pa, pb;
pa = Parent(a);
pb = Parent(b);
if (pa != pb)
{
if (S[pb] > S[pa])
{
swap(pa, pb);
}
for (int i = 0; i < V[pb].size(); i++)
{
V[pa].push_back(V[pb][i]);
}
S[pa] += S[pb];
P[pb] = pa;
}
}
void run(int N)
{
srand(time(0));
for (int i = 0; i <= N; i++)
{
P[i] = i;
S[i] = 1;
V[i].push_back(i);
}
int q = 0;
for (int i = N; i >= 2; i--)
{
int F[i], k=0;
for (int y = 0; y < N; y++)
{
if (Parent(y) == y)
{
F[k] = y;
k++;
}
}
int A[N], B[N], Pr[k], a, b, sa, sb;
vector <pair<long long,int>> FF;
while (true)
{
FF.clear();
for (int y = 0; y < k; y++)
{
long long ran = rand()*RAND_MAX+rand();
FF.push_back({ran,F[y]});
}
//random_shuffle(F, F+k);
//sort(FF.begin(),FF.end());
random_shuffle(FF.begin(),FF.end());
sa = 0;
sb = 0;
for (int y = 0; y < k/2; y++)
{
//A[y] = F[y]+1;
for (int u = 0; u < V[FF[y].second].size(); u++)
{
A[sa] = V[FF[y].second][u]+1;
sa++;
}
}
for (int y = k/2; y < k; y++)
{
//B[y-i/2] = F[y]+1;
for (int u = 0; u < V[FF[y].second].size(); u++)
{
B[sb] = V[FF[y].second][u]+1;
sb++;
}
}
if (query(sa, sb, A, B) == 1)
{
break;
}
}
int L=0, R=sa, t, s;
while (R-L > 1)
{
t = (L+R) / 2;
s = (R-1)-t+1;
int C[s];
k = 0;
for (int y = t; y < R; y++)
{
C[k] = A[y];
k++;
}
if (query(k, sb, C, B) == 1)
{
L = t;
}
else
{
R = t;
}
}
a = A[L];
L = 0;
R = sb;
while (R-L > 1)
{
t = (L+R) / 2;
s = (R-1)-t+1;
int C[s];
k = 0;
for (int y = t; y < R; y++)
{
C[k] = B[y];
k++;
}
if (query(sa, k, A, C) == 1)
{
L = t;
}
else
{
R = t;
}
}
b = B[L];
setRoad(a, b);
Union(a-1, b-1);
}
}
Compilation message
icc.cpp: In function 'void Union(int, int)':
icc.cpp:29:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < V[pb].size(); i++)
~~^~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:78:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int u = 0; u < V[FF[y].second].size(); u++)
~~^~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:87:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int u = 0; u < V[FF[y].second].size(); u++)
~~^~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:59:25: warning: unused variable 'Pr' [-Wunused-variable]
int A[N], B[N], Pr[k], a, b, sa, sb;
^~
icc.cpp:47:9: warning: unused variable 'q' [-Wunused-variable]
int q = 0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
504 KB |
Ok! 99 queries used. |
| 2 |
Correct |
9 ms |
504 KB |
Ok! 104 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
504 KB |
Ok! 526 queries used. |
| 2 |
Correct |
65 ms |
560 KB |
Ok! 849 queries used. |
| 3 |
Correct |
62 ms |
504 KB |
Ok! 784 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
560 KB |
Ok! 1487 queries used. |
| 2 |
Correct |
214 ms |
632 KB |
Ok! 2119 queries used. |
| 3 |
Correct |
166 ms |
504 KB |
Ok! 1717 queries used. |
| 4 |
Correct |
168 ms |
504 KB |
Ok! 1715 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
504 KB |
Ok! 1574 queries used. |
| 2 |
Correct |
155 ms |
560 KB |
Ok! 1566 queries used. |
| 3 |
Correct |
182 ms |
564 KB |
Ok! 1842 queries used. |
| 4 |
Correct |
159 ms |
632 KB |
Ok! 1609 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
186 ms |
504 KB |
Too many queries! 1865 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
183 ms |
508 KB |
Too many queries! 1853 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
