//void solve1(){ // sort(rail.begin(),rail.end(),cmp); // int rightest=1; // the rightest position can reach. // isAns[1]=1; // vector<int> ans; // // for(auto r:rail){ // // can go to this rail? // if(r.l <= rightest){ // rightest = max(rightest,r.r); // if(!isAns[r.r]){ // ans.push_back(r.r); // isAns[r.r]=1; // } // } // } // // sort(ans.begin(),ans.end()); // // for(auto a:ans){ // printf("%d ",a); // } // // puts(""); //}
voidsolve2(){ sort(rail.begin(),rail.end(),cmp); int rightest=x; // the rightest position can reach. isAns[x]=1; vector<int> ans;
for(auto r:rail){ // can go to this rail? // x . . . . . . R // l r if(r.l <= rightest && r.r>=x){ rightest = max(rightest,r.r); if(!isAns[r.r]){ ans.push_back(r.r); isAns[r.r]=1; } } } sort(rail.begin(),rail.end(),cmp2); int leftest=x; // the rightest position can reach. for(auto r:rail){ // can go to this rail? if(r.r >= leftest && r.l<=x){ leftest = min(leftest,r.l); if(!isAns[r.l]){ //printf("left %d is ans, because %d>=%d.\n",r.l,r.r,leftest); ans.push_back(r.l); isAns[r.l]=1; } } }
int n,k,m; vector<Employee> emp[N]; // the employee of this Node int emp_pos[N]; // the initial position of employee X vector<int> G[N]; // the tree.
vector<Employee> emp2[N];
voidtry_place(int pos,int fa,vector<Employee>::iterator need_to_place){ int best_pos=-1,best_val=-1; // bfs all children queue<pair<int,int> > q; q.push({pos,fa}); while(q.size()){ auto now = q.front();q.pop();
int maxn = 0; // the maximum ability of Node now. 0 for no employee for(auto people:emp2[now.first]){ maxn = max(maxn,people.abl); } // only can move if the target has lower ability if(maxn<need_to_place->abl){ if(best_pos==-1 || maxn<best_val){ best_pos=now.first; best_val=maxn; } }
voidsolve_chain(){ priority_queue<int,vector<int>,greater<int> > pq; // samll heap // 1 -> 2 -> 3 ... -> n-1 -> n // start from the n-1 pos.
longlong ans = 0; ans += get_max(n); pq.push(ans); // printf("%lld first pushed.\n",ans);
for(int i=n-1;i>=1;i--){ // i can go to i+1 ... n // the top of pq(samllest)
// for every people except the biggest. int mi = get_max(i); ans += mi; pq.push(mi); // printf("%d pushed.\n",mi); bool max_appeared = 0; for(auto p:emp[i]){ if(p.abl!=mi || max_appeared){ if(pq.top()<p.abl){ ans -= pq.top(); ans += p.abl; pq.pop();pq.push(p.abl); } }else{ max_appeared=1; } } }
// 114514 // 1919810 // hai you yi ge xiao shi. xie bu chu lai le ;(
char mp[15][15];
int dx_r[]={1,-1,0,0}; int dy_r[]={0,0,1,-1};
int n,m;
voidsolve_p1(){ // can red move? bool can_red_move = 0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]!='O')continue; for(int k=0;k<4;k++){ int ii=i+dx_r[k],jj=j+dy_r[k]; // because tie or red can't move // so red can never move to a black piece. // only check if empty if(mp[ii][jj]=='.')can_red_move=1; } } } if(!can_red_move){ puts("Black 0"); } else{ puts("Tie"); } }
voidsolve_1b1r(){ // iiyo koiyo // if m==1 -> if(m==1){ // black wins iff there's only . above it. int bx,bo; for(int i=1;i<=n-2;i++){ if(mp[i][1]=='X'){ bx=i; } if(mp[i][1]=='O'){ bo=i; } } }
// else // NOTE THAT red CAN SKIP his round (the piece in line n can move)
// strategy // black : move forward // red : first move horizontally, then move vertically. // wrong puts("Tie"); }
// if black can never move to red, then must tie. // 1) search above. int can_meet = 0; for(int i=bx-1;i>0;i--){ if(mp[i][1]=='#')break; if(mp[i][1]=='O')can_meet++; } // 2) search below. for(int i=bx+1;i<=n;i++){ if(mp[i][1]=='#')break; if(mp[i][1]=='O')can_meet++; } if(!can_meet){ puts("Tie"); return; }
// the last task is divided into the following three subtasks. // a) 2 red 1 black // b) 1 red 1 black (other red can't move) // c) 1 red 1 black (other red can move)
// check if subete ha kotonarimasu. memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++){ if(vis[b[i]]==1){ // printf("same!\n"); return; } vis[b[i]]=1; } // for all possible move, bob will choose the minimal one. int eq = 0; for(int i=0;i<n;i++){ if(a[i]==b[i])eq++; } tans = min(tans,eq); // printf("ok, eq=%d tans=%d\n",eq,tans); return; } for(int i=1;i<=T[dep][0];i++){ b[dep]=T[dep][i]; dfs2(dep+1); } } voiddfs1(int dep){ if(dep==n){ tans = INF; dfs2(0);
// for all possible tans, Alice will choose the greatest. if(tans!=INF)ans=max(ans,tans); return; } for(int i=1;i<=S[dep][0];i++){ a[dep]=S[dep][i]; dfs1(dep+1); } } voidsolve_bf(){ ans = -1; dfs1(0); printf("%d\n",ans); }
int fa[N],sz[N]; int cnt[N]; intfind(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); } voidmerge(int i,int j){ // printf("\tmerge %d(%d/%d), %d(%d/%d)\n",i,find(i),sz[find(i)],j,find(j),sz[find(j)]); i=find(i),j=find(j); if(i==j)return; if(sz[i]>sz[j])swap(i,j); fa[i]=j; sz[j]+=sz[i]; } voidsolveA(){ // puts("great! is A!"); // zhe shi CF yuan ti // dan shi wo wang le ? // ... // suo yi shuo yao bu ti. QAQ // ming nian zai zhan
// (10:25)我觉得如果每个连通块内边数小于等于点数就可以 // 否则就不可以
// (10:44) wonderfully, it works! // but i don't know why it works // it just works perfectly. // watashiha tennsai da!
// now the two are the same. // both add (tsame//2) (the remainder 1 can be omitted -> no affect answer) if(tsame>0){ ans1 += tsame/2; ans2 += tsame/2; } printf("%d\n",min(ans1,ans2)); } intmain(){ freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%d",&kase); while(kase--){ // cntk++; scanf("%d%d",&n,&m); bool isA = 1; bool isB = (n>=3);
for(int i=0;i<n;i++){ scanf("%d",&S[i][0]); for(int j=1;j<=S[i][0];j++){ scanf("%d",&S[i][j]); } } for(int i=0;i<n;i++){ scanf("%d",&T[i][0]); if(T[i][0]==1)isB=0; for(int j=1;j<=T[i][0];j++){ scanf("%d",&T[i][j]); // check if is same. if(!isA)continue; for(int k=1;k<=S[i][0];k++){ if(S[i][k]==T[i][j])isA=0; } } if(!isB)continue; // check is is B // 1) sort them if(T[i][1]>T[i][2])swap(T[i][1],T[i][2]);
