题目链接:Codeforces 466E Information Graph
题目大意:一开始有n个员工,他们互相独立。现在有三种操作。
- 1 u v,v称为u的上级
- 2 u,从u发起一份文件,逐层递交给上级
- 3 u v,询问u是否查阅过v号文件。
解题思路:将每个文件移动的范围处理出来,然后对于每次询问,将询问拆成两个标记,假设查询x是否浏览过第k号文件,第k号文件的范围为u-v,那么在最后dfs时,遍历到x,判断是否经过u;遍历到v时,判断是否经过x。如果两个都满足,则是YES。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
int N, M, K = 0, f[maxn], c[maxn], vis[maxn];
vector<int> G[maxn];
vector<pii> P, Q[maxn];
inline int getfar(int x) {
return x == f[x] ? x : f[x] = getfar(f[x]);
}
void init () {
scanf("%d%d", &N, &M);
for (int i = 0; i <= N; i++)
f[i] = i;
int op, x, y;
while (M--) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d", &x, &y);
f[x] = y;
G[y].push_back(x);
} else if (op == 2) {
scanf("%d", &x);
P.push_back(make_pair(getfar(x), x));
} else {
scanf("%d%d", &x, &y);
pii u = P[y-1];
Q[x].push_back(make_pair(u.first, K));
Q[u.second].push_back(make_pair(x, K));
K++;
}
}
}
void dfs (int u) {
vis[u] = 1;
for (int i = 0; i < G[u].size(); i++)
dfs(G[u][i]);
for (int i = 0; i < Q[u].size(); i++) {
int v = Q[u][i].first, id = Q[u][i].second;
if (vis[v])
c[id]++;
}
vis[u] = 0;
}
int main () {
init();
for (int i = 1; i <= N; i++) {
if (f[i] == i)
dfs(i);
}
for (int i = 0; i < K; i++)
printf("%s\n", c[i] == 2 ? "YES" : "NO");
return 0;
}
分享到:
相关推荐
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
【并查集】Codeforces 566D Restructuring Company题面在这里对于本题,只需要再维护一个并查集表示i所在联通块的最右位置因为相邻
解决问题(문제해결) ACM-ICPC凭证,BOJ,CodeForces,Codewars,SCPC,摇动,TopCoder凭证
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
# sublime-plugin-for-codeforces 自定义构建,用于从 codeforces 获取测试用例并检查程序是否正确。 平台:GNU/Linux 语言:Python2.7.9 描述:这个程序从 codeforces 中获取测试用例,并告诉你程序的输出是否与...
268C Beautiful Sets of Points 传送门 题意:在n*m的格点图里尽量多的选点,使点之间两两距离不为整数,同时不能选(0,0). 构造水题了,很明显每行/列最多放一个,那么最多应该放min(n,m)+1个,由于0,0不能选,直接...
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<=st[y]<=ed[y]<=ed[x]. 即...
codeForces C ++中的Code Force解决方案
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
波兰球和游戏: ://codeforces.com/problemset/problem/755/B 问题779 B.怪异的舍入: : 问题845 A.国际象棋锦标赛: : 问题884 B.日语填字游戏反击: : 问题985 A.国际象棋的放置: : 问题1042 A.长凳: : 问题1105...
并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,只需要找度为222的点即可 如果一条边两个顶点的度都为222,我们可以用并查集判断两点是否在一个子图里 用并查集判断两...
Codeforces 185A - Plant 全测试点49个
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
Codeforces Round #620 (Div. 2) [codeforces 1304A] Two Rabbits 整除+模 总目录详见https://blog.csdn.net/mrcrack/article/details/103564004 在线测评地址https://codeforces.ml/contest/1304/problem/A ...
Codeforces扩展包 是否曾经想让Codeforce拥有方便的快捷键,自动更新排行榜,可以按需隐藏/显示的问题标签,更好的站点导航,深色主题或以上所有功能? 这些和更多功能可以在Codeforces ++中获得! 该扩展是开源的,...
Codeforces global round 10 codes
Codeforces round 678 division 2 codes