打卡信奥刷题（3345）用C++实现信奥题 P9464 [EGOI 2023] Padel Prize Pursuit / 追梦笼式网球

P9464 [EGOI 2023] Padel Prize Pursuit / 追梦笼式网球题目背景Day 1 Problem B.题面译自 EGOI2023 ppp。题目描述有N NN个编号为0 00到N − 1 N-1N−1的选手参加一场M MM天的笼式网球锦标赛。每天恰好进行一次比赛。在锦标赛中共颁发M MM块奖牌每场比赛颁发一块新奖牌。在第i ii天的比赛中0 ≤ i ≤ M − 1 0\le i\le M-10≤i≤M−1两名编号分别为x i x_ixi​和y i y_iyi​的选手参加。比赛中发生如下事件选手x i x_ixi​打败选手y i y_iyi​。一个新的奖牌授予给获胜者x i x_ixi​。失败者所有现有的奖牌都授予给获胜者。在第M MM天最后一场比赛结束后一天举行颁奖典礼。在颁奖典礼上所有奖牌被收集起来并授予给持有该奖牌时间最长的选手。具体地在第M MM天奖牌i ii授予给持有奖牌i ii最多个晚上的选手不必须连续持有。如果两个或更多选手持有一个奖牌同样多晚上奖牌授予给其中编号最小的选手。你的任务是求出颁奖典礼中每位选手被授予多少奖牌。输入格式第一行两个整数N , M N,MN,M表示选手数和比赛数。接下来M MM行每行两个整数x i , y i x_i,y_ixi​,yi​表示第i ii天的比赛中选手x i x_ixi​打败选手y i y_iyi​。输出格式一行N NN个整数第k kk个整数表示颁奖典礼中第k kk位选手被授予的奖牌数。输入输出样例 #1输入 #13 4 0 1 2 1 1 0 2 1输出 #11 1 2输入输出样例 #2输入 #23 7 0 1 0 2 2 0 0 1 1 0 2 0 0 2输出 #22 2 3输入输出样例 #3输入 #36 10 2 5 3 0 4 2 0 1 4 3 2 4 0 3 0 2 5 2 5 0输出 #35 0 1 1 1 2说明/提示样例1 11解释下图展示了样例1 11中锦标赛期间奖牌的归属。当选手1 11在第三天被打败时她的所有奖牌都被授予给选手2 22。样例2 22解释如下图。在颁奖典礼中选手0 00被授予奖牌5 55和6 66选手1 11被授予奖牌3 33和4 44选手2 22被授予奖牌0 , 1 , 2 0,1,20,1,2。数据范围对于全部数据2 ≤ N ≤ 2 × 10 5 2\le N\le 2\times 10^52≤N≤2×1051 ≤ M ≤ 2 × 10 5 1\le M\le 2\times 10^51≤M≤2×1050 ≤ x i , y i ≤ N − 1 0\le x_i,y_i\le N-10≤xi​,yi​≤N−1且x i ≠ y i x_i\ne y_ixi​yi​。子任务一12 1212分N 2 N2N2。子任务二16 1616分N , M ≤ 2 × 10 3 N,M\le 2\times 10^3N,M≤2×103。子任务三15 1515分第i ii场比赛的获胜者参加了第i 1 i1i1场比赛依赖子任务一。子任务四20 2020分在第i ii场比赛时x i x_ixi​有至少和y i y_iyi​一样多的奖牌。子任务五22 2222分一旦一名选手被打败她永远不会再次参赛。子任务六15 1515分无特殊限制依赖子任务二、三、四、五。C实现#includebits/stdc.husingnamespacestd;constintN4e5100;intn,m;intans[N],cnt[N],dt[N];boolvis[N];structnode{intu,st,ed;};node a[N];vectorintV[N];voidadd(intx,ints,intMx){cnt[x]s;if(cnt[x]cnt[Mx])Mxx;elseif(cnt[x]cnt[Mx]xMx)Mxx;}voiddfs(intu,intMx){if(!u)return;vis[u]true;intsa[u].ed-a[u].st1,rMxMx;add(a[u].u,s,Mx);ans[Mx];for(intv:V[u])dfs(v,Mx);cnt[a[u].u]-s;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(inti1;im;i){intx,y;cinxy;x,y;a[i].ux,a[i].sti,a[i].edm;if(dt[x])a[dt[x]].edi-1,V[i].push_back(dt[x]);if(dt[y])a[dt[y]].edi-1,V[i].push_back(dt[y]);dt[x]i,dt[y]0;}for(inti1;in;i){if(dt[i])dfs(dt[i],0);}for(inti1;in;i)coutans[i] ;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容