首页 > 编程学习 > CodeForces-Gym 101142C CodeCoder vs TopForces(搜索)

CodeForces-Gym 101142C CodeCoder vs TopForces(搜索)

发布时间:2022/12/10 17:13:30

传送门:http://codeforces.com/gym/101142/attachments

Problem C. CodeCoder vs TopForces

Input file: codecoder.in
Output file: codecoder.out
Time limit: 2 seconds
Memory limit: 256 megabytes


Competitive programming is very popular in Byteland. In fact, every Bytelandian citizen is registered
at two programming sites — CodeCoder and TopForces. Each site maintains its own proprietary rating
system. Each citizen has a unique integer rating at each site that approximates their skill. Greater rating
corresponds to better skill.
People of Byteland are naturally optimistic. Citizen A thinks that he has a chance to beat citizen B in
a programming competition if there exists a sequence of Bytelandian citizens A = P0, P1, . . . , Pk = B for
some k ≥ 1 such that for each i (0 ≤ i < k), Pi has higher rating than Pi+1 at one or both sites.
Each Bytelandian citizen wants to know how many other citizens they can possibly beat in a programming
competition.

Input
The first line of the input contains an integer n — the number of citizens (1 ≤ n ≤ 100 000). The
following n lines contain information about ratings. The i-th of them contains two integers CCi and
T Fi — ratings of the i-th citizen at CodeCoder and TopForces (1 ≤ CCi, T Fi ≤ 1e6). All the ratings at

each site are distinct.


Output
For each citizen i output an integer bi — how many other citizens they can possibly beat in a programming
competition. Each bi should be printed in a separate line, in the order the citizens are given in the input.


题意:每个人有2种排名,对于A只要有一种排名高于B,那么A就能赢B,再如果B能赢C,那么A也能赢C,要求输出每个人分别能赢多少个人

题解:先按第一种排名从小到大排序,将第i个人与第i-1个人连一条有向边,表示第i个人能赢第i-1个人;再按第二种排名从小到大排序,将第i个人与第i-1个人连一条有向边;然后按排名从低到高搜索一遍,能搜到的人表示能赢的,由于传递性,vis不用清空


#include<bits/stdc++.h>
using namespace std;
const int MX = 1e6 + 5;
struct node{int x,y,id,cnt;
}p[MX];
struct Edge{int v,nxt;
}edge[MX*2];
int head[MX],tot,cnt,vis[MX];
bool cmp1(node p1,node p2){return p1.x<p2.x;}
bool cmp2(node p1,node p2){return p1.y<p2.y;}
bool cmp3(node p1,node p2){return p1.id<p2.id;}
void add(int u,int v){edge[tot].v=v;edge[tot].nxt=head[u];head[u]=tot++;
}
void dfs(int u){if(vis[u]==0)cnt++;vis[u]=1;for(int i=head[u];~i;i=edge[i].nxt){int v=edge[i].v;if(vis[v]==0) dfs(v);}
}
int main(){int n;freopen("codecoder.in","r",stdin);freopen("codecoder.out","w",stdout);while(~scanf("%d",&n)){memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));tot=0;for(int i=0;i<n;i++) {scanf("%d%d",&p[i].x,&p[i].y);p[i].id=i;}sort(p,p+n,cmp1);for(int i=1;i<n;i++) add(p[i].id,p[i-1].id);sort(p,p+n,cmp2);for(int i=1;i<n;i++) add(p[i].id,p[i-1].id);cnt=0;for(int i=0;i<n;i++){dfs(p[i].id);p[i].cnt=cnt-1;}sort(p,p+n,cmp3);for(int i=0;i<n;i++) printf("%d\n",p[i].cnt);}return 0;
}




本文链接:https://www.ngui.cc/el/2314507.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000