Saturday, May 25, 2024

# Codeforces Round #409 (rated, Div. 1, based on VK Cup 2017 Round 2), problem: (E) Verifying Kingdom Solution In C/C++

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x–)
#define cross(x,a) for (int x=hd[a];~x;x=nx[x])
#define ll long long
#define inf (1<<29)
#define pii pair<int,int>
#define pdd pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fs first
#define sc second
#define pb push_back
#define VI vector<int>
#define VS vector<string>
using namespace std;
inline ll rd(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!=’-‘)&&(ch!=EOF)) ch=getchar();
if (ch==’-‘){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-‘0’;ch=getchar();}
return x*f;
}
inline void rt(ll x){
if (x<0) putchar(‘-‘),x=-x;
if (x>=10) rt(x/10),putchar(x%10+’0′);
else putchar(x+’0′);
}
const int maxn=2005;
int n,nc;
int hd[maxn],nx[maxn<<1],to[maxn<<1],cnt;
to[cnt]=v;nx[cnt]=hd[u];hd[u]=cnt++;
to[cnt]=u;nx[cnt]=hd[v];hd[v]=cnt++;
}
int pa[maxn],ls[maxn],rs[maxn],ez[maxn];
int cen,ms[maxn],size[maxn];
int del[maxn],allsize,nwk;
void getcenter(int u,int fa){
size[u]=1;ms[u]=0;
cross(i,u){
int v=to[i];
if (v==fa||del[v]) continue;
getcenter(v,u);
size[u]+=size[v];
ms[u]=max(ms[u],size[v]);
}
ms[u]=max(ms[u],allsize-size[u]);
if (u>n&&(!cen||ms[u]<ms[cen])) cen=u;
}
char ans[5];
void divide(int u){
cen=0;getcenter(u,0);u=cen;
del[u]=1;
printf(“%d %d %d\n”,ez[ls[u]],ez[rs[u]],nwk);
fflush(stdout);
scanf(“%s”,ans);
if (ans[0]==’X’){
if ((!~pa[u])||del[pa[u]]){
++nc;
if (~pa[u]){
pa[nc]=pa[u];
if (ls[pa[u]]==u) ls[pa[u]]=nc;else rs[pa[u]]=nc;
}
pa[u]=pa[nwk]=nc;
ls[nc]=u;rs[nc]=ez[nc]=nwk;
}
else allsize=size[pa[u]]<size[u]?size[pa[u]]:allsize-size[u],divide(pa[u]);
}
else if (ans[0]==’Z’){
if (ls[u]<=n||del[ls[u]]){
++nc;pa[nc]=u;
ls[nc]=ls[u],rs[nc]=ez[nc]=nwk,pa[ls[u]]=nc,ls[u]=nc,pa[nwk]=nc;
}
else allsize=size[ls[u]]<size[u]?size[ls[u]]:allsize-size[u],divide(ls[u]);
}
else if (ans[0]==’Y’){
if (rs[u]<=n||del[rs[u]]){
++nc;pa[nc]=u;
rs[nc]=rs[u],ls[nc]=ez[nc]=nwk,pa[rs[u]]=nc,rs[u]=nc,pa[nwk]=nc;
}
else allsize=size[rs[u]]<size[u]?size[rs[u]]:allsize-size[u],divide(rs[u]);
}
}
int main(){
nc=n=rd();
rep(i,1,n) ez[i]=i;
memset(pa,-1,sizeof pa);
pa[1]=pa[2]=++nc,ls[nc]=ez[nc]=1,rs[nc]=2;
rep(v,3,n){
nwk=v,allsize=v*2-3;
memset(hd,-1,sizeof hd);cnt=0;
memset(del,0,sizeof del);
divide(1);
}
puts(“-1”);
rep(i,1,n*2-1) rt(pa[i]),putchar(‘ ‘);putchar(‘\n’);
fflush(stdout);
}

## Celebrating Black History Month:...

As February unfolds, so does the annual celebration of...

## The Path to Self-Mastery:...

Embarking on a journey of self-mastery and breaking free...

## Wizards of Waverly Place...

In a spellbinding announcement, Disney has officially revealed that...

## Jim Irsay’s Reported ‘Suspected...

In a shocking turn of events last month, Jim...

Coachella Valley Music and Arts Festival, one of the...

## 2024 Taiwan Election: Pivotal...

As Taiwan gears up for its 2024 presidential election,...

### Celebrating Black History Month: Past, Future

As February unfolds, so does the annual celebration of Black History Month, a time to reflect on the profound contributions, resilience, and rich cultural...

### The Path to Self-Mastery: Lessons from Book ‘The Mountain Is You’

Embarking on a journey of self-mastery and breaking free from self-sabotage is a transformative process that requires dedication and conscious effort. Brianna Wiest's insightful...

### Wizards of Waverly Place Cast Reunites for Enchanting Revival

In a spellbinding announcement, Disney has officially revealed that the beloved fantasy series "Wizards of Waverly Place" is set for a magical comeback, featuring...

### Jim Irsay’s Reported ‘Suspected Overdose’: A Closer Look

In a shocking turn of events last month, Jim Irsay, the owner of the Indianapolis Colts, was reportedly found unresponsive at his home in...

### Coachella 2024: Iconic headliners, unforgettable musical experience!

Coachella Valley Music and Arts Festival, one of the most iconic and eagerly anticipated music festivals globally, has just dropped its highly anticipated lineup...

### 2024 Taiwan Election: Pivotal Moment in Political Landscape

As Taiwan gears up for its 2024 presidential election, the political landscape is buzzing with anticipation and fervor. With the island nation situated at...

### Michael Strahan’s Daughter’s Medulloblastoma Diagnosis

In a recent and heartbreaking revelation, Michael Strahan, former NFL star and television personality, shared the devastating news of his daughter Isabella's diagnosis with...

### Michigan vs. Washington: The 2024 National Championship Clash

In a highly anticipated matchup, the 2024 National Championship will witness a clash of football titans as the Michigan Wolverines square off against the...

### Jason Kelce: Unmasking the Unconventional NFL Icon

In the world of professional football, where conformity often takes center stage, one player stands out as a beacon of individuality, both on and...