| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 731572 | abcvuitunggio | ICC (CEOI16_icc) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "icc.h"
#include <bits/stdc++.h>
#define NAM
using namespace std;
#ifdef NAM
int g[101][101],n,u[101],v[101],id=1,cnt;
int query(int sa, int sb, int a[], int b[]){
cnt++;
for (int i=0;i<sa;i++)
for (int j=0;j<sb;j++){
if (a[i]<1||a[i]>n||b[j]<1||b[j]>n){
cout << "Cities in query out of range.";
exit(1);
}
if (g[a[i]][b[j]])
return 1;
}
return 0;
}
void setRoad(int a, int b){
if (a<1||a>n||b<1||b>n){
cout << "Road cannot exist.";
exit(2);
}
if (!g[a][b]){
cout << "Road " << a << ' ' << b << " doesn't exist.";
exit(3);
}
id++;
g[u[id]][v[id]]=g[v[id]][u[id]]=1;
}
#endif // NAM
int p[101];
vector <int> ve[101],root;
int f(int i){
return (p[i]==i?i:p[i]=f(p[i]));
}
void unite(int i, int j){
i=f(i);
j=f(j);
if (i>j)
swap(i,j);
p[j]=i;
for (int k:ve[j])
ve[i].push_back(k);
ve[j].clear();
}
int ask(int x, int y, int a[], int b[]){
int A[x],B[y];
for (int i=0;i<x;i++)
A[i]=a[i];
for (int j=0;j<y;j++)
B[j]=b[j];
return query(x,y,A,B);
}
int n;
void findroad(){
root.clear();
for (int i=1;i<=n;i++)
if (f(i)==i)
root.push_back(i);
for (int i=0;(1<<i)<root.size();i++){
int sa=0,sb=0;
for (int j=0;j<root.size();j++)
if ((j>>i)&1)
sb+=ve[root[j]].size();
else
sa+=ve[root[j]].size();
int a[sa],b[sb],x=0,y=0;
for (int j=0;j<root.size();j++){
if ((j>>i)&1)
for (int u:ve[root[j]]){
b[y]=u;
y++;
}
else
for (int u:ve[root[j]]){
a[x]=u;
x++;
}
}
if (query(sa,sb,a,b)){
int l=1,r=sa,kq=-1,kq2=-1;
while (l<=r){
int mid=(l+r)>>1;
if (ask(mid,sb,a,b)){
kq=mid;
r=mid-1;
}
else
l=mid+1;
}
l=1,r=sb;
while (l<=r){
int mid=(l+r)>>1;
if (ask(sa,mid,a,b)){
kq2=mid;
r=mid-1;
}
else
l=mid+1;
}
setRoad(a[kq-1],b[kq2-1]);
unite(a[kq-1],b[kq2-1]);
break;
}
}
}
void Run(int N){
n=N;
for (int i=1;i<=n;i++){
p[i]=i;
ve[i].push_back(i);
}
for (int i=1;i<n;i++)
findroad();
}
int main(){
cin >> n;
for (int i=1;i<n;i++)
cin >> u[i] >> v[i];
g[u[1]][v[1]]=g[v[1]][u[1]]=1;
Run(n);
#ifdef NAM
cout << "You successfully found all the roads. Congratulations!\n";
cout << "You've asked " << cnt << " queries.";
#endif // NAM
}