首页 > 其他分享 >LY1374 [ 20231008 NOIP 模拟赛 T2 ] 机房惨案

LY1374 [ 20231008 NOIP 模拟赛 T2 ] 机房惨案

时间:2023-10-08 16:22:06浏览次数:38  
标签:fir cnt NOIP fa 20231008 top T2 int nex

题意

给定一棵树,每次操作将一个点染成黑色。

求询问的点到所有黑点的路径编号最小值。

** 数据保证第一次为染色操作 **

Sol

注意到保证第一次为染色。

考虑钦定根节点为染色的点。

那么对于所有染色操作,暴力记录染色的点到根节点的路径上所有点的贡献。

每个点只会贡献一次,这部分是 \(O(n)\)。

考虑询问的点到根节点的贡献。预处理即可 \(O (n + q)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <bitset>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
string read_() {
	string ans;
	char c = getchar();
	while (c != 'J' && c != 'Q')
		c = getchar();
	while (c == 'J' || c == 'Q') {
		ans += c;
		c = getchar();
	}
	return ans;

}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 1e6 + 5, M = 2e6 + 5;

namespace G {

array <int, N> fir;
array <int, M> nex, to;
int cnt;
void add(int x, int y) {
	cnt++;
	nex[cnt] = fir[x];
	to[cnt] = y;
	fir[x] = cnt;
}

}

/*
namespace Hpt {

using G::fir, G::nex, G::to;
array <int, N> fa, siz, son, dep;
void dfs1(int x) {
	siz[x] = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (to[i] == fa[x]) continue;
		fa[to[i]] = x;
		dep[to[i]] = dep[x] + 1;
		dfs1(to[i]);
		if (siz[to[i]] > siz[son[x]]) son[x] = to[i];
	}
}

array <int, N> dfn, idx, top;
int cnt;
void dfs2(int x, int Mgn) {
	cnt++;
	dfn[x] = cnt;
	idx[cnt] = x;
	top[x] = Mgn;
	if (son[x]) dfs2(son[x], Mgn);
	for (int i = fir[x]; i; i = nex[i]) {
		if (to[i] == son[x] || to[i] == fa[x]) continue;
		dfs2(to[i], to[i]);
	}
}

int lca(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		x = fa[top[x]];
	}
	if (dfn[x] > dfn[y]) swap(x, y);
	return x;
}

}
*/
using G::fir, G::nex, G::to;
bitset <N> vis;
array <int, N> fa, dis;
int dfs(int x, int rt) {
	int ans = 0x7f7f7f7f;
	while (x != rt && !vis[x]) {
		ans = min(x, ans);
		vis[x] = 1;
		x = fa[x];
	}
	return ans;
}
void _dfs(int x) {
	dis[x] = min(dis[x], x);
	for (int i = fir[x]; i; i = nex[i]) {
		if (to[i] == fa[x]) continue;
		dis[to[i]] = min(dis[to[i]], dis[x]);
		fa[to[i]] = x;
		_dfs(to[i]);
	}
}
int main() {
	freopen("network.in", "r", stdin);
	freopen("network.out", "w", stdout);
	int n = read(), q = read() - 1;
	for (int i = 2; i <= n; i++) {
		int x = read(), y = read();
		G::add(x, y), G::add(y, x);
	}
	dis.fill(0x7f7f7f7f);
	int lcaST = 0x7f7f7f7f;
	int rt = read();
	_dfs(rt);
	/* Hpt::dfs1(rt), Hpt::dfs2(rt, 0); */
	while (q--) {
		string opt = read_();
		if (opt[0] == 'J') {
			int x = read();
			lcaST = min(lcaST, dfs(x, rt));
		}
		else {
			int x = read();
			write(min(lcaST, dis[x])), puts("");
		}
	}
	return 0;
}

标签:fir,cnt,NOIP,fa,20231008,top,T2,int,nex
From: https://www.cnblogs.com/cxqghzj/p/17749499.html

相关文章

  • Sovit2D在线组态设计 构建LNG加气站Web Scada控制系统
    前言天然气是最清洁的化石能源,天然气使用安全、应用广泛,在炊事、供热、发电、交通等领域扮演重要角色。LNG(液化天然气)作为一种市场化的全球能源,能够很好的解决天然气的可及性问题。建设背景在LNG行业迅速发展的同时,加气站的监管难度加大,加之许多地方管理工作相对薄弱滞后、控......
  • Langchain-Chatchat项目:2.1-通过GPT2模型来检索NebulaGraph
      在官方例子中给出了通过chain=NebulaGraphQAChain.from_llm(ChatOpenAI(temperature=0),graph=graph,verbose=True)来检索NebulaGraph图数据库。本文介绍了通过GPT2替换ChatOpenAI的思路和实现,暂时不考虑效果。之所以没用ChatGLM2是因为加载模型太慢,调试不方便,不过将GPT2......
  • P1003 [NOIP2011 提高组] 铺地毯
    第一思路:开一个N*N的数组,每次都扫一遍地毯范围并标记编号然后你会发现:喜提MLE为什么呢?我们来看看数据范围0≤n≤1e4n的范围是1e4,数组总大小为1e16,大约需要4000TB的内存空间服务器也不带这么玩的正解:将地毯信息用结构体存储structnode{ intx1,y1,x2,y2;//x1......
  • 2023NOIP A层联测5
    A.T1(cook)复合题,考场上只做出来了分块的部分,没有想到那个组合数求和可以用莫队分块部分具体不说了,对散块部分加权时,可以采用归并优化时间复杂度(因为我北卡长哩,卡到了晚饭之后,卡了一下午,好欸!)现在考虑问题\(\sum_{i=0}^{k}\dbinom{x}{i}\)令$(S(n,m)=\sum_{i=0}^{m}C......
  • 洛谷 P1969 [NOIP2013 提高组] 积木大赛 - 小思维
    洛谷P1969[NOIP2013提高组]积木大赛[NOIP2013提高组]积木大赛题目描述春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为\(n\)的大厦,大厦可以看成由\(n\)块宽度为\(1\)的积木组成,第\(i\)块积木的最终高度需要是\(h_i\)。在搭建开始之前......
  • 2023NOIP A层联测6
    A.万花筒考虑发现每次相当于把x和x+d连边,不难发现最后一定是一些环证明可以看白简B.冒泡排序趟数期望写一下我曾经比较疑惑的点为什么inv和p一定一一对应,因为我们发现只要给出我们一个inv我们就可以倒推出唯一确定的p,所以它们是一一对应的关系这道......
  • P3953 [NOIP2017 提高组] 逛公园
    Description策策同学特别喜欢逛公园。公园可以看成一张\(N\)个点\(M\)条边构成的有向图,且没有自环和重边。其中\(1\)号点是公园的入口,\(N\)号点是公园的出口,每条边有一个非负权值,代表策策经过这条边所要花的时间。策策每天都会去逛公园,他总是从\(1\)号点进去,从\(N\)......
  • 【GJOI 2023.10.6 T2】 亿只只因的回家路
    亿只只因的回家路题意:给出一个\(n\)点\(m\)边的无向图,每条边有长度\(v_i\),有\(k\)只小鸡,第\(i\)只小鸡在\(id_i\)号节点,鸡妈妈在\(1\)号点,现鸡妈妈要接所有的小鸡,小鸡与鸡妈妈的速度为\(1\),问最短多久鸡妈妈才能接到所有的小鸡,\(n\le10^5,k\le2\times10^......
  • LY1371 [ 20231007 NOIP 模拟赛 T0 ] 十一之争
    题意给定一个长度为\(n\)的数字串\(s\)和只包含yo的字符串\(t\),yoimiya会和oimiya玩\(n\)轮游戏,初始有一个数字串\(x\)为\(0\),每次:如果\(t_i\)是y则是yoimiya操作,如果是o则是oimiya操作。每次操作:将\(s_i\)或者\(0\)加入\(x\)的末尾。如果最......
  • Ynoi2012 NOIP2016 人生巅峰
    Day\(\text{XXX}\)。注意到修改是易于复合的立方操作,而且值域非常小,所以可以直接\(O(v\logm)\)预处理出对每个\(i\in[0,v)\)操作了\(2^{j}\lem\)次的结果,维护出每一位被修改了多少次,查询某一位的值直接倍增\(O(\logm)\)即可。然后这个限制很弱,因为如果区间内有重复......