Basic Diplomacy solution codeforces
Question:
Aleksey has nn friends. He is also on a vacation right now, so he has mm days to play this new viral cooperative game! But since it’s cooperative, Aleksey will need one teammate in each of these mm days.
On each of these days some friends will be available for playing, and all others will not. On each day Aleksey must choose one of his available friends to offer him playing the game (and they, of course, always agree). However, if any of them happens to be chosen strictly more than ⌈m2⌉⌈m2⌉ times, then all other friends are offended. Of course, Aleksey doesn’t want to offend anyone.
Help him to choose teammates so that nobody is chosen strictly more than ⌈m2⌉⌈m2⌉ times.Input Basic Diplomacy solution codeforces
Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤100001≤t≤10000). Description of the test cases follows.
The first line of each test case contains two integers nn and mm (1≤n,m≤1000001≤n,m≤100000) standing for the number of friends and the number of days to play, respectively.
The ii-th of the following mm lines contains an integer kiki (1≤ki≤n1≤ki≤n), followed by kiki distinct integers fi1fi1, …, fikifiki (1≤fij≤n1≤fij≤n), separated by spaces — indices of available friends on the day ii.
It is guaranteed that the sums of nn and mm over all test cases do not exceed 100000100000. It’s guaranteed that the sum of all kiki over all days of all test cases doesn’t exceed 200000200000.Output Basic Diplomacy solution codeforces
Print an answer for each test case. If there is no way to achieve the goal, print “NO“.
Otherwise, in the first line print “YES“, and in the second line print mm space separated integers c1c1, …, cmcm. Each cici must denote the chosen friend on day ii (and therefore must be one of fijfij).
No value must occur more than ⌈m2⌉⌈m2⌉ times. If there is more than one possible answer, print any of them.Example Basic Diplomacy solution codeforces
input
2 4 6 1 1 2 1 2 3 1 2 3 4 1 2 3 4 2 2 3 1 3 2 2 1 1 1 1
output
YES 1 2 1 1 2 3 NO
Answer:
#include<bits/stdc++.h>
using namespace std;
#define ma 2147483647
#define ll long long
#define ld long double
#define pii pair<int,int>
#define mii map<int,int>
#define umii unordered_map<int,int>
#define um unordered_map
#define vi vector<int>
#define mii map<int,int>
#define si set<int>
#define ft first
#define sc second
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*(b/gcd(a,b))
#define mmst(a,b) memset(a,b,sizeof(a))
#define N 200005
struct st
{
int x;int y;
}k[N];
bool comp(st x,st y)
{
return (x.x<y.x);
}
int l[N],r[N],a[N];
int n,m;
int ad[N],ans[N];
int main()
{
//freopen(“c.in”,”r”,stdin);
int t=0;
scanf(“%d”,&t);
for (int t0=1;t0<=t;t0++)
{
memset(ad,0,sizeof(ad));
scanf(“%d%d”,&n,&m);
for (int i=1;i<=m;i++)
{
scanf(“%d”,&k[i].x);
k[i].y=i;
l[i]=r[i-1]+1;
r[i]=l[i]+k[i].x-1;
for (int j=l[i];j<=r[i];j++)
{
scanf(“%d”,&a[j]);
}
}
sort(k+1,k+m+1,comp);
bool pp=1;
for (int i=1;i<=m;i++)
{
int mi=ma;
int mi_=0;
int l1=l[k[i].y];
int r1=r[k[i].y];
for (int j=l1;j<=r1;j++)
{
if (ad[ a[j] ]<mi)
{
mi=ad[ a[j] ];
mi_=a[j];
}
}
if (mi+1>(m+1)/2)
{
pp=0;
break;
}
ad[mi_]++;
ans[k[i].y]=mi_;
}
if (pp==0)
{
printf(“NO\n”);
}else
{
printf(“YES\n”);
for (int i=1;i<=m;i++) printf(“%d “,ans[i]);
printf(“\n”);
}
}
}
