| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 858523 |
2023-10-08T15:30:41 Z |
Tenis0206 |
ICC (CEOI16_icc) |
C++11 |
|
103 ms |
640 KB |
#include <bits/stdc++.h>
#ifndef home
#include "icc.h"
#endif // home
using namespace std;
const int nmax = 100;
#ifdef home
pair<int,int> e[nmax + 5];
void output(string msg)
{
cout<<msg<<'\n';
exit(0);
}
int cnt = 1;
int query(int sza, int szb, int a[], int b[])
{
bool ok = false;
for(int i=0;i<sza;i++)
{
for(int j=0;j<szb;j++)
{
for(int nr=1;nr<=cnt;nr++)
{
if(e[nr].first==a[i] && e[nr].second==b[j])
{
ok = true;
break;
}
if(e[nr].first==b[j] && e[nr].second==a[i])
{
ok = true;
break;
}
}
}
}
return ok;
}
void setRoad(int a, int b)
{
bool ok = false;
if(a==e[cnt].first && b==e[cnt].second)
{
ok = true;
}
if(a==e[cnt].second && b==e[cnt].first)
{
ok = true;
}
if(!ok)
{
output("Bad edge");
}
++cnt;
}
#endif // home
int n;
int a[nmax + 5], b[nmax + 5];
int vst[nmax + 5];
int t[nmax + 5];
vector<int> l[nmax + 5];
mt19937 my_rand(time(NULL));
int my_rand_val(int x)
{
return my_rand() % x;
}
int rep(int x)
{
if(t[x]==x)
{
return x;
}
return rep(t[x]);
}
void uneste(int x, int y)
{
x = rep(x);
y = rep(y);
if(x==y)
{
return;
}
if(l[x].size() > l[y].size())
{
for(auto it : l[y])
{
l[x].push_back(it);
}
l[y].clear();
t[y] = x;
}
else
{
for(auto it : l[x])
{
l[y].push_back(it);
}
l[x].clear();
t[x] = y;
}
}
pair<int,int> find_dif(int nra, int nrb)
{
random_shuffle(a,a+nra,my_rand_val);
random_shuffle(b,b+nrb,my_rand_val);
int val_a = 0, val_b = 0;
int st = 1;
int dr = nra;
while(st<dr)
{
int mij = (st + dr) >> 1;
int nrv = 0;
for(int i=st;i<=mij;i++)
{
vst[nrv++] = a[i - 1];
}
int ok = query(nrv, nrb, vst, b);
if(ok)
{
dr = mij;
}
else
{
st = mij + 1;
}
}
val_a = a[st - 1];
st = 1;
dr = nrb;
while(st<dr)
{
int mij = (st + dr) >> 1;
int nrv = 0;
for(int i=st;i<=mij;i++)
{
vst[nrv++] = b[i - 1];
}
int ok = query(nrv, nra, vst, a);
if(ok)
{
dr = mij;
}
else
{
st = mij + 1;
}
}
val_b = b[st - 1];
return {val_a, val_b};
}
void find_new_edge()
{
vector<int> c;
for(int i=1;i<=n;i++)
{
if(rep(i)==i)
{
c.push_back(i);
}
}
random_shuffle(c.begin(),c.end(),my_rand_val);
pair<int,int> rez = {0,0};
for(int bit=0;(1<<bit)<c.size();bit++)
{
int nra = 0, nrb = 0;
for(int i=0;i<c.size();i++)
{
if((i & (1<<bit)) == 0)
{
for(auto it : l[c[i]])
{
a[nra++] = it;
}
}
else
{
for(auto it : l[c[i]])
{
b[nrb++] = it;
}
}
}
int ok = query(nra, nrb, a, b);
if(ok)
{
rez = find_dif(nra, nrb);
break;
}
}
setRoad(rez.first,rez.second);
uneste(rez.first, rez.second);
}
void run(int N)
{
srand(time(NULL));
n = N;
for(int i=1;i<=n;i++)
{
t[i] = i;
l[i].push_back(i);
}
for(int i=1;i<n;i++)
{
find_new_edge();
}
}
#ifdef home
int main()
{
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
int nn;
cin>>nn;
for(int i=1;i<nn;i++)
{
int x,y;
cin>>x>>y;
e[i] = {x,y};
}
run(nn);
output("OK");
return 0;
}
#endif // home
Compilation message
icc.cpp: In function 'void find_new_edge()':
icc.cpp:183:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
183 | for(int bit=0;(1<<bit)<c.size();bit++)
| ~~~~~~~~^~~~~~~~~
icc.cpp:186:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for(int i=0;i<c.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
604 KB |
Ok! 100 queries used. |
| 2 |
Correct |
4 ms |
604 KB |
Ok! 99 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
604 KB |
Ok! 528 queries used. |
| 2 |
Correct |
34 ms |
632 KB |
Ok! 657 queries used. |
| 3 |
Correct |
30 ms |
604 KB |
Ok! 638 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
624 KB |
Ok! 1386 queries used. |
| 2 |
Correct |
103 ms |
628 KB |
Ok! 1604 queries used. |
| 3 |
Correct |
91 ms |
624 KB |
Ok! 1512 queries used. |
| 4 |
Correct |
90 ms |
624 KB |
Ok! 1495 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
604 KB |
Ok! 1485 queries used. |
| 2 |
Correct |
93 ms |
604 KB |
Ok! 1490 queries used. |
| 3 |
Correct |
97 ms |
640 KB |
Ok! 1594 queries used. |
| 4 |
Correct |
86 ms |
600 KB |
Ok! 1417 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
600 KB |
Ok! 1583 queries used. |
| 2 |
Correct |
97 ms |
600 KB |
Ok! 1591 queries used. |
| 3 |
Correct |
99 ms |
624 KB |
Ok! 1599 queries used. |
| 4 |
Correct |
96 ms |
604 KB |
Ok! 1580 queries used. |
| 5 |
Correct |
88 ms |
604 KB |
Ok! 1474 queries used. |
| 6 |
Correct |
95 ms |
600 KB |
Ok! 1510 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
620 KB |
Ok! 1578 queries used. |
| 2 |
Correct |
102 ms |
600 KB |
Ok! 1602 queries used. |
