/*
"care a facut teste cu Lattice reduction attack e ciudat"
"linistiti va putin"
- 2023 -
*/
#include<bits/stdc++.h>
#include "icc.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
int root[105];
int sz[105];
int comp[105][105];
bool connected[105][105];
int aquery[105];
int aqsz;
int bquery[105];
int bqsz;
int c[105];
int d[105];
bool seen[105];
void unite(int a, int b)
{
a=root[a];
b=root[b];
if (a==b)
return;
if(sz[a]<sz[b])
{
swap(a,b);
}
int i;
for (i=0; i<sz[b]; i++)
{
comp[a][sz[a]]=comp[b][i];
sz[a]++;
root[comp[b][i]]=a;
}
}
/*
int query(int sza, int szb, int a[], int b[])
{
int i,j;
for (i=0; i<sza; i++)
{
for (j=0; j<szb; j++)
{
if (connected[a[i]][b[j]])
{
return 1;
}
}
}
return 0;
}
*/
void add(int type, int &sza, int b[], int szb)
{
int i;
if (type==1)
{
for (i=0; i<szb; i++)
{
c[sza]=b[i];
sza++;
}
}
else if (type==2)
{
for (i=0; i<szb; i++)
{
aquery[sza]=b[i];
sza++;
}
}
else if (type==3)
{
for (i=0; i<szb; i++)
{
bquery[sza]=b[i];
sza++;
}
}
}
bool compara(int j)
{
int i;
for (i=1; i<=n; i++)
{
seen[i]=0;
}
int x,rando;
for (i=1; i<=n; i++)
{
x=root[i];
if (!seen[x])
{
rando=uniform_int_distribution<int>(0,1)(rng);
if (rando%2==0)
add(2,aqsz,comp[x],sz[x]);
else
add(3,bqsz,comp[x],sz[x]);
seen[x]=1;
}
}
/*
debugs(j);
debugs(aqsz);
debug(bqsz);
for (i=0;i<aqsz;i++)
{
debug(aquery[i]);
}
for (i=0;i<bqsz;i++)
{
debug(bquery[i]);
}
*/
return query(aqsz,bqsz,aquery,bquery);
}
pair<int,int> find_road()
{
int i,j;
for (i=0; i<=6 && (1<<i)<=n; i++)
{
aqsz=0;
bqsz=0;
//debugs(i);
//debug(compara(i));
if (compara(i)==1)
{
break;
}
}
int r,pas,apoz,bpoz,csize;
r=0;
pas=(1<<6);
while (pas)
{
if (r+pas<aqsz)
{
csize=0;
add(1,csize,aquery,r+pas);
if (!query(r+pas,bqsz,c,bquery))
r+=pas;
}
pas=pas/2;
}
apoz=aquery[r];
d[0]=apoz;
r=0;
pas=(1<<6);
while (pas)
{
if (r+pas<bqsz)
{
csize=0;
add(1,csize,bquery,r+pas);
if (!query(r+pas,1,c,d))
r+=pas;
}
pas=pas/2;
}
bpoz=bquery[r];
return {apoz,bpoz};
}
/*
void build_road()
{
int a,b;
cin >> a >> b;
connected[a][b]=1;
connected[b][a]=1;
}
void setroad(int a, int b)
{
cout << "am gasit lol : ";
cout << a << " " << b << "\n";
//unite(a,b);
}
*/
void run(int _n)
{
n=_n;
int pasi,i;
pair<int,int> ans;
for (i=1; i<=n; i++)
{
root[i]=i;
comp[i][0]=i;
sz[i]=1;
}
pasi=0;
while (pasi<n-1)
{
//build_road();///asta trebuie comentat
ans=find_road();
setRoad(ans.first,ans.second);
unite(ans.first,ans.second);
pasi++;
}
}
/*
signed main()
{
//ifstream fin("secvp.in");
//ofstream fout("secvp.out");
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//cout.tie(0);
int en;
cin >> en;
run(en);
}
*/
Compilation message
icc.cpp: In function 'std::pair<int, int> find_road()':
icc.cpp:133:11: warning: unused variable 'j' [-Wunused-variable]
133 | int i,j;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
604 KB |
Ok! 115 queries used. |
| 2 |
Incorrect |
4 ms |
604 KB |
The query sets must be disjoint |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
604 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
