admin管理员组文章数量:1530035
Omicron变种病毒传染性太强了,城市屡屡破防。封闭在家的我决定为防疫做点事:帮助筛选密切接触、次密切接触人员。
网格员提供了一些小区的风险时段内的接触记录、确诊人员,需要判断人员的风险分类:
- A类:疑似病例、临床诊断病例、确诊病例。(输入数据)
- B类:与A类人员有接触的人员。(需要判断)
- C类:与B类人员有接触的人员。(需要判断)
- D类:其他人员。
输入规格
- 输入的数据有多组,处理至EOF为止。
- 每组数据
- 首行有4项:日期D(字符串)、小区人数N、接触记录数量C、确诊人数P,间隔1个空格。N、C、P都是非负整数。
- 之后是C行接触记录。每条记录由两个人员ID组成,间隔1个空格。没有重复的接触记录。
- 然后是P行确诊人员ID。
- 为保护隐私,发给我的数据中人员ID已经脱敏,都是些序号,范围从1到N。
- 小区最多2000人。本题不考察时空复杂度。
输出规格
- 对每组数据:
- 输出日期,换行。
- 按照序号由小到大逐行输出A、B、C类人员ID和类别(A/B/C字母),间隔1个空格。D类略过。
样例输入
2022-04-01 8 5 2
2 1
8 5
5 2
3 4
4 2
1
8
2022-01-01 5 0 0
样例输出
2022-04-01
1 A
2 B
4 C
5 B
8 A
2022-01-01
样例解释
- 第1组:1、8为A类。2、5与A类人员有接触,属于密接B类。4与B类人员有接触,属于次密接C类。
- 第2组:为空。
提示
- 最多2K人,接触记录排除重复后最多
2K * 2K ~ 4M
条,可以用布尔型的二维数组bool contact[N][N];
记录,当contact[u][v]为true
时表示编号u和v的人员有接触。约需要4M字节,空间可行。- 是否接触其实用1-bit就能表示,1-byte能表示8条接触记录,所以只需
4M / 8 ~ 512KB
- 是否接触其实用1-bit就能表示,1-byte能表示8条接触记录,所以只需
- 人员类别可用数组
char tag[N]
保存,全部初始化为'D'
或NUL
。- 用
'D'
更清晰,可用memset(s, c, n)
设置。 - 用
NUL
更方便,写成char tag[N]{};
即可。 - 这两种方式如果不太理解,建议都试一遍。
- 用
- 样例第一组数据读入后的
contact
数组状态:- 为使区分明显,用
.
代表false
,用T
代表true
。 - 读入全部接触记录后,先根据A类把B类全标记出来,再根据B类从剩余人员中把C类标记出来。
- 为使区分明显,用
-
1 2 3 4 5 6 7 8 ------------------ 1A|. T . . . . . . 2B|T . . T T . . . 3 |. . . T . . . . 4C|. T T . . . . . 5B|. T . . . . . T 6 |. . . . . . . . 7 |. . . . . . . . 8A|. . . . T . . .
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
-
#include<bits/stdc++.h> using namespace std; int main(){ for(int s[100],n,c,p;~scanf("%s %d %d %d",s,&n,&c,&p);){ vector<vector<int>> e(n+10); vector<int> a(n+10,0x3f3f3f3f); while(c--){ int x,y;cin>>x>>y; e[x].push_back(y); e[y].push_back(x); } queue<int> q; while(p--){ int x;cin>>x; q.push(x); a[x]=1; } while(q.size()){ int hd=q.front();q.pop(); for(auto to:e[hd]){ if(a[to]>a[hd]+1){ a[to]=a[hd]+1; q.push(to); } } } printf("%s\n",s); for(int i=1;i<=n;i++){ if(a[i]<=3){ printf("%d %c\n",i,a[i]-1+'A'); } } } }
本文标签:
版权声明:本文标题:7-43 密接判定v1(close_contact1) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1726640782a1079616.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论