Information Graph

el/2024/5/23 1:33:22

题意

有 n 个雇员在公司 “X” 工作 (为方便考虑,将他们从 1 到 n 编号)。最初,雇员之间没有任何关系。在接下来的每 m 天中,每天发生以下事件中的一件:

要么雇员 y 变成雇员 x 的上司 (那时,雇员 x 尚未拥有一个上司);
要么雇员 x 取得一小包文件并签署它们,然后他将这一小包给了他的上司。他的上司签署了这些文件,并将它们给了更上一层的上司,依此类推 (签署文件的最后一人,将它们发送到归纳箱中);
要么类型为 “判断雇员 x 是否签署了特定的文件” 的一个请求到来。
您的任务是编写一个程序,给定这些事件的情况下,回答所描述类型的查询。在那时,数据保证:在整个工作时间,公司中没有循环依赖。

分析

这道题我们可以采用离线处理

首先我我们先去建图,在建图的过程中如果遇到了文件传输的话,我们记录每一个文件的起点和终点,起点比较好确定,就是我输入的数值,那么怎么去确认终点呢?我们可以去维护一个并查集

然后我们去处理每一个询问,其实就是去判断询问的点是不是在对应的那条路径上面,我们已经有了起点,终点,待判断的点,可以用最近公公祖先去处理这个问题,待判断的点和起点的LCA为他本身,待判断的点和终点的LCA为终点,同时记得判断一下三点个是否在同一个联通快内部即可

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int h[N],ne[N],e[N],idx;
int f[N][21];
int res;
int line1[N],line2[N];
int q[N];
int d[N];
int ppp[N];
int qid[N];
int n,m,num;void add(int a,int b){ne[idx] = h[a],e[idx] = b,h[a] = idx++;
}int find(int x){if(x != q[x]) q[x] = find(q[x]);return q[x]; 
}void bfs(int root){d[0] = 0,d[root] = 1;queue<int> Q;Q.push(root);while(Q.size()){int t = Q.front();Q.pop();for(int i = h[t];~i;i = ne[i]){int j = e[i];if(d[j] > d[t] + 1){d[j] = d[t] + 1;Q.push(j);f[j][0] = t;for(int k = 1;k <= 20;k++)f[j][k] = f[f[j][k - 1]][k - 1];}}}
}int LCA(int a,int b){if(d[a] < d[b]) swap(a,b);for(int i = 20;i >= 0;i--)if(d[f[a][i]] >= d[b])a = f[a][i];if(a == b) return a;for(int i = 20;i >= 0;i--)if(f[a][i] != f[b][i])a = f[a][i],b = f[b][i];return f[a][0];
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof h);for(int i = 1;i <= n;i++) q[i] = i;while(m--){int op,x,y;scanf("%d",&op);if(op == 1){scanf("%d%d",&x,&y);add(y,x);q[x] = find(y);}else if(op == 2){scanf("%d",&x);line1[++res] = x;line2[res] = find(x);}else{scanf("%d%d",&x,&y);ppp[++num] = x;qid[num] = y;}}memset(d,0x3f,sizeof d);for(int i = 1;i <= n;i++)if(q[i] == i)bfs(i);for(int i = 1;i <= num;i++){int id = qid[i],x = ppp[i];int st = line1[id],ed = line2[id];int a = find(st),b = find(ed),c = find(x);if(a != b || b != c || a != c){puts("NO");continue;}if(LCA(st,x) == x && LCA(x,ed) == ed) puts("YES");elseputs("NO");}
}/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/

http://www.ngui.cc/el/5239358.html

相关文章

让我们异或吧 DFS + 位运算技巧

题意 中文题意就不需要分析了吧 分析 我在洛谷上面搜的是LCA的标签&#xff0c;但是这道题跟LCA好像关系不太大&#xff1f; 首先因为有n - 1条边&#xff0c;首先我们可以确定这是一条树&#xff0c;然后我们去求异或值的时候&#xff0c;可以先求出点到跟节点的异或值&…

松鼠的新家 LCA + 树上差分

题意 中文题意就不需要分析了吧 分析 首先两点之间&#xff0c;我们应该去走最短路径最能得到最优解&#xff0c;所以很容易想到求LCA&#xff0c;假设两点分别为x&#xff0c;y&#xff0c;LCA(x,y) u&#xff0c;所以只需要把路径 x -> u -> y上的所有点加上一个糖…

Alyona and a tree 树上差分 +倍增

传送门 题目描述 给定一颗树&#xff0c;每个结点有对应点权&#xff0c;每条边也有对应边权。如果dis<v, u> < val[u]&#xff0c;则说明结点u被结点v所管辖。对于每个结点&#xff0c;输出它管辖的结点数目。 分析 这道题如果我们遍历每一个点并且往上爬&#x…

Snacks dfs 序 + 线段树

传送门 题目描述 百度科技园内有n个零食机&#xff0c;零食机之间通过n−1条路相互连通。每个零食机都有一个值v&#xff0c;表示为小度熊提供零食的价值。 由于零食被频繁的消耗和补充&#xff0c;零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发&#xff0…

Count on a tree 主席树 + LCA

传送门 题目描述 给定一个包含 N 个结点的树. 树节点从 1 到 N编号.。每个节点有一个整数权值&#xff0c;查询从节点 u 到节点 v的路径上权值第k小的节点的权值。 分析 树上主席树的入门题了 我们可以用类似于树上差分的思想来处理这个问题&#xff0c;每一个节点其实就是…

Super Mario 主席树 +二分

传送门 题目描述 马里奥是一个举世闻名的管道工&#xff0c;他的跳跃能力让我们钦佩。在一条长度为n的道路上&#xff0c;在每个整数点i的位置都有一个高度为hi的障碍物。现在的问题是&#xff1a;假设马里奥可以跳跃的最高高度为H&#xff0c;在道路的[L,R] 区间内他可以跳跃…

The Door Problem 并查集

传送门 题目描述 ​有n个门和m个开关&#xff0c;每个开关可以控制任意多的门&#xff0c;每个门严格的只有两个开关控制&#xff0c;问能否通过操作某些开关使得所有门都打开。&#xff08;给出门的初始状态&#xff09;。 分析 一开始看的时候觉得是个2—sat问题&#xf…

Generate a String 线性DP + 单调队列优化

传送门 题目描述 给定正整数 n, x, y&#xff0c;你要生成一个长度为 n 的字符串&#xff0c;有两种操作&#xff1a; 添一字符或删去一个原有字符&#xff0c;代价为 x&#xff1b; 将已有字串复制粘贴一次&#xff08;翻倍&#xff09;&#xff0c;代价为 y。 求最小代价。…

Three Paths on a Tree 树的直径

传送门 题目描述 在一棵树内找三个点x,y,z&#xff0c;要求三个点之间的距离最大&#xff0c; 分析 首先我们可以找到这棵树内的直径&#xff0c;然后去去找另一点到这棵树上的直径最短 我一开始的思路是三次bfs&#xff0c;求出直径的端点&#xff0c;并且处理出每一个点…

Number of Components 思维

传送门 题目描述 分析 在一条链中&#xff0c;可以观察出结论&#xff1a;联通块数 点数 - 边数 所以我们需要求出每个点的贡献以及每一条边的贡献 首先&#xff0c;每一个点只有在 a[i] > l && a[i] < r 的时候才会被选择&#xff0c;所以每一个点的贡献应该…