[ACNOI2022]《普林斯普的荣光》

news/2024/4/14 11:26:35

题目

题目背景
多年以后,我在搬砖的工地上,远远望见了一个身影:仍然是如同漆黑的杆子一般,手丝毫不摆动,而脚一步一印往前挪动,像吸盘,像祂正试图学会在地上平移,用自己的脚。

我几乎要失声叫出祂的名字;这个名字我花了十年去恐惧,花了十年去遗忘,但我看到祂的一瞬间,所有努力都是徒劳,所有意义都被抹杀。

任何事物都逃不过祂的眼睛。当我从惊慌中挣脱出来,抬头便遇上祂的审视。祂胸前的金牌扰乱着我的神志。我只能勉强从牙缝中挤出来几个字:

普……普林斯普!”

祂的嘴唇没有动,我的脑海中却响起一句话。这真的是我刚刚所顿悟的么?

校长笑话,烟雾弹也;水群摆烂,麻痹对手尔。”

回忆如波涛翻滚。仿佛有无数个祂同时在我耳边低语:

你看,你又被骗了吧。”

题目描述
给出一个无向连通图 G = ( V , E ) G=(V,E) G=(V,E),定义新图 G ′ = ( V , E ′ ) G'=(V,E') G=(V,E) 满足 E ′ = { ⟨ a , b , c a ⟩ ∣ dis ( a , b ) ⩽ d a } E'=\{\langle a,b,c_a\rangle\mid\text{dis}(a,b)\leqslant d_a\} E={a,b,cadis(a,b)da},其中 ⟨ a , b , c ⟩ \langle a,b,c\rangle a,b,c 表示边权为 c c c a → b a\to b ab 有向边,而 dis ( a , b ) \text{dis}(a,b) dis(a,b) G G G a , b a,b a,b 最短路的边数。

求新图 G ′ G' G 1 1 1 号点到每个点的最短路。

数据范围与约定
n ⩽ 2 × 1 0 5 ∧ d i ∈ [ 1 , n ] ∧ c i ∈ [ 1 , 1 0 9 ] ∧ ∣ E ∣ ⩽ ∣ V ∣ + 50 n\leqslant 2\times 10^5\land d_i\in[1,n]\land c_i\in[1,10^9]\land |E|\leqslant |V|+50 n2×105di[1,n]ci[1,109]EV+50 。时限 4 s \rm 4s 4s

思路

注意到 ∣ E ∣ ⩽ ∣ V ∣ + 50 |E|\leqslant|V|+50 EV+50,考虑建一棵生成树,然后讨论非树边的影响。必要条件是搞懂树边的影响。即,先考虑原图是一棵树的情况。

树上路径问题?类似此题,可以直接点分治优化建图。不需要边分治,因为 dis ( y , z ) ⩽ d x − dis ( x , z ) \text{dis}(y,z)\leqslant d_x-\text{dis}(x,z) dis(y,z)dxdis(x,z) x → y x\to y xy 有边的充分条件,即 dis ( x , y ) \text{dis}(x,y) dis(x,y) 可以实际上不经过 z z z,不需要边分治来保障 “必须经过” 的要求。

当然,现在想想,优化建图跑最短路,不如 O U Y E \sf OUYE OUYE 所说 数据结构优化转移。建出显式图,只会增加不必要的时空复杂度。非最短路问题,倒是有可能让代码实现更简单(比如 2-sat \text{2-sat} 2-sat 问题)。

非树边呢?相当于转移过程中,需要走过某条非树边。点分治的本质是,考虑 dis \text{dis} dis 必须经过某个点;将每条非树边的任一端点设为 “特殊点”,对经过特殊点的 dis \text{dis} dis 进行转移即可。

显式建图,似乎有 O ( n log ⁡ n + n k ) \mathcal O(n\log n+nk) O(nlogn+nk) 条边,其中 k = ∣ E ∣ − ∣ V ∣ + 1 k=|E|-|V|+1 k=EV+1 。跑 d i j k s t r a \tt dijkstra dijkstra 岂不是 O [ n log ⁡ n log ⁡ ( n log ⁡ n ) ] \mathcal O[n\log n\log(n\log n)] O[nlognlog(nlogn)] 了吗?可以类比此题,将 ( v i + c i ) (v_i+c_i) (vi+ci) 放入 h e a p \tt heap heap 中;显式建图,则其等价于将边权为 0 0 0 的连通块进行 b f s \rm bfs bfs 更新。这样可以保证每个点直接得到答案,复杂度 O ( n log ⁡ n + n k ) \mathcal O(n\log n+nk) O(nlogn+nk)

代码

#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // (the STRONG LONG for loneliness)
#include <cctype> // DDG yydDOG & ZXY yydBUS !!!
#include <queue>
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){int a = 0, c = getchar(), f = 1;for(; !isdigit(c); c=getchar())if(c == '-') f = -f;for(; isdigit(c); c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}const int MAXN = 200005, MAXM = 200055;
# define _go(i,x) for(int i=head[x]; ~i; i=e[i].nxt)
struct Edge{ int to, nxt; };
Edge e[MAXN<<1]; int head[MAXN], cntEdge;
void addEdge(int a, int b){e[cntEdge].to = b, e[cntEdge].nxt = head[a];head[a] = cntEdge ++;
}
const int LOGN = 18;
int siz[MAXN], dep[LOGN][MAXN], fa[MAXN][LOGN];
bool vis[MAXN]; int whole, core;
void findRoot(int x, int pre){siz[x] = 1; int mx = 0;_go(i,x) if((i^1) != pre && !vis[e[i].to]){findRoot(e[i].to,i), siz[x] += siz[e[i].to];mx = std::max(mx,siz[e[i].to]);}if((mx<<1) <= whole && whole <= (siz[x]<<1)) core = x;
}
int *group[MAXN];
int* collect(const int &level, int x, int pre, int* ptr){fa[x][level] = core, *(ptr ++) = x;_go(i,x) if((i^1) != pre && !vis[e[i].to]){dep[level][e[i].to] = dep[level][x]+1;ptr = collect(level,e[i].to,i,ptr);}return ptr;
}
void solve(int x, int level){static int buc[MAXN], tmp[MAXN]; ///< bucket sortfindRoot(x,-1), memset(buc,0,whole<<2);dep[level][core] = 0, collect(level,core,-1,tmp);rep0(i,0,whole) ++ buc[dep[level][tmp[i]]];rep0(i,1,whole) buc[i] += buc[i-1];group[core] = new int[whole+1];*group[core] = core, group[core][whole] = -1;for(int *i=tmp+1; i!=tmp+whole; ++i){int &rnk = buc[dep[level][*i]-1];group[core][rnk ++] = *i;}vis[core] = true;const int _core = core;_go(i,core) if(!vis[e[i].to]){if(siz[e[i].to] > siz[_core])whole = siz[x]-siz[_core];else whole = siz[e[i].to];solve(e[i].to,level+1);}
}void bfs(int *que, int *dis, int x, const int &n){memset(dis+1,-1,n<<2), dis[x] = 0;int *bac = que; *bac = x;for(; que!=bac+1; ++que) // keep releasing_go(i,x=*que) if(!(~dis[e[i].to])){dis[e[i].to] = dis[x]+1;++ bac, *bac = e[i].to;}
}namespace UFS{int fa[MAXN];int find(int a);bool merge(int a, int b);
}
bool bad[MAXN]; int tot;
const int MAXK = 102;
int dis[MAXK][MAXN], que[MAXK][MAXN];
int *que_ptr[MAXK];typedef std::pair<llong,int> PII;
llong ans[MAXN]; extern bool vis[MAXN];
std::priority_queue<PII> pq;
int radius[MAXN], cost[MAXN];
int main(){int n = readint(), m = readint();rep(i,1,n) UFS::fa[i] = i;memset(head+1,-1,n<<2);std::queue< std::pair<int,int> > bad_edge;for(int i=1,a,b; i<=m; ++i){a = readint(), b = readint();if(UFS::merge(a,b))addEdge(a,b), addEdge(b,a);else{bad[a] = bad[b] = true;bad_edge.push(std::make_pair(a,b));}}whole = n, solve(1,0); memset(vis+1,false,n);for(; !bad_edge.empty(); bad_edge.pop()){const std::pair<int,int> &p = bad_edge.front();addEdge(p.first,p.second), addEdge(p.second,p.first);}rep(i,1,n) if(bad[i]) bfs(que[tot],dis[tot],i,n), ++ tot;rep0(i,0,tot) que_ptr[i] = que[i];rep(i,1,n){radius[i] = readint();cost[i] = -readint(); // negated}ans[1] = 0, vis[1] = true;pq.push(PII{cost[1],1});while(!pq.empty()){int x = pq.top().second; pq.pop();rep0(j,0,LOGN) if(fa[x][j]) // existfor(int* &i=group[fa[x][j]]; ~(*i); ++i){if(dep[j][*i]+dep[j][x] > radius[x]) break;if(vis[*i]) continue; // updatedans[*i] = ans[x]+cost[x], vis[*i] = true;pq.push(PII{ans[*i]+cost[*i],*i});}rep0(j,0,tot) for(int* &i=que_ptr[j]; i!=que[j]+n; ++i){if(dis[j][*i]+dis[j][x] > radius[x]) break;if(vis[*i]) continue; // updatedans[*i] = ans[x]+cost[x], vis[*i] = true;pq.push(PII{ans[*i]+cost[*i],*i});}}rep(i,2,n) printf("%lld\n",-ans[i]);return 0;
}int UFS::find(int a){if(a == fa[a]) return a;return fa[a] = find(fa[a]);
}
bool UFS::merge(int a, int b){if(find(a) == find(b)) return false;fa[fa[a]] = fa[b]; return true;
}

http://www.ppmy.cn/news/617452.html

相关文章

耐材展会|2022年广州国际耐火材料展览会

2022年广州国际耐火材料展览会 同期举办&#xff1a;第二十三届广州国际冶金工业展览会 主办单位&#xff1a;广州巨浪展览策划有限公司 中国耐材行业首选推广洽谈平台 广州国际耐火材料展览会&#xff0c;经过多年的发展&#xff0c;已逐步成为国内乃至亚洲具有影响力的行业…

Urban NeRF

本文首发于馆主君晓的博客&#xff0c;文章链接 简要介绍 这是谷歌和多伦多大学合作的一篇发表在CVPR2022上的工作&#xff0c;延续NeRF重建的相关思路。考虑到之前的一些工作要么是在合成数据集上进行的NeRF重建&#xff0c;要么就是用到真实的场景&#xff0c;但是场景很小&a…

欧盟电源适配器外部电源2019/1782/EU ERP欧洲能效认证

欧盟电源适配器外部电源2019/1782/EU ERP欧洲能效认证 欧洲委员会&#xff0c;考虑到《欧洲联盟运作条约》第114条&#xff0c; 2019年10月25日,欧洲委员会正式发布了外部电源ErP更新法规(EU) 2019/1782,旨在取代现行ErP法规(EC) No 278/2009。新法规将于2020年4月1日起强制实…

pnpm 简介

本文引用自 摸鱼wiki 1. 与npm&#xff0c;yarn性能比较 actioncachelockfilenode_modulesnpmpnpmYarnYarn PnPinstall33.8s20.1s20.3s40.7sinstall✔✔✔2.1s1.4s2.6sn/ainstall✔✔9.1s5.3s7.8s1.7sinstall✔13.5s9.3s14.1s7.7sinstall✔15s17.2s14.2s33.4sinstall✔✔2.5s3s…

Linux学习之进程概念和ps命令

进程概念和启动关闭进程 进程就是运行中的程序 在C语言中进程只能只能从main()函数开始运行。 进程终止的方式有两种&#xff1a; 正常终止&#xff1a;从main()函数返回、调用exit()等方式 异常终止&#xff1a;调用abort、接收信号等。有可能 ps ps是“process status”的缩…

IDEA下Logback.xml自动提示功能配置

首先打开logback的配置文件&#xff0c;在configuration标签中加入xsd的配置 <configuration xmlns"http://ch.qos.logback/xml/ns/logback"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://ch.qos.logback/xml…

Linux ❀ Ubuntu开机报错 pciehp:cannot get irq -1 for the hotplug / unknown chipset

"pciehp: cannot get irq -1 for the hotplug" 错误信息表明 PCIe 热插拔&#xff08;hotplug&#xff09;模块无法获取正确的 IRQ&#xff08;中断请求&#xff09; 禁用 PCIe 热插拔&#xff1a;进入恢复模式或命令行模式&#xff0c;并 sudo nano /etc/default/gr…

游戏音乐存在的价值

游戏音乐是文化产业中兴起的数字音乐产业与热门电子游戏产业相碰撞而形成的数字音乐&#xff0c;游戏音乐在游戏中占据不可缺少的位置&#xff0c;今天我们来聊聊游戏音乐存在的价值。 一、游戏音乐能勾勒美好的回忆 87年日本科乐美公司发行的经典FC游戏《魂斗罗…

用 Python 写游戏有什么优势?

简单&#xff0c;简单&#xff0c;还是tm的简单 简单到什么程度&#xff0c;我带着我的小学生&#xff0c;几乎能使用python复刻所有的2D游戏 先看看&#xff0c;我们写过的游戏 上面机会覆盖所有80、90后童年的游戏 意味着现在孩子的童年都能写出家长沉迷的游戏当中 对此&…

真正的头号玩家——游戏AI

从雅达利游戏机到如今的手游&#xff0c;电子游戏已经走过了数十年的发展史&#xff0c;从青少年的“毒品”变成了社会主流的新娱乐。去年以来&#xff0c;《绝地求生》席卷了国内&#xff0c;似乎人人口中都念叨着“吃鸡”两个字。此后相关的手游也层出不穷&#xff0c;但玩家…

100个开源游戏

街机游戏 1、Andys Super Great Park 骑在过山车上&#xff0c;躲避障碍的同时收集气球。游戏有25关&#xff0c;另外还有18关需要得到高分才能解锁。支持的操作系统&#xff1a;Windows,Linux,Android。 2、Armagetron Advanced 这是Tron的3D克隆版。在游戏中&#xff0c;你需…

一个自律的产品经理,如何抵抗游戏的吸引力?

游戏&#xff0c;真好玩。 一个时代有一个时代的代表。从掌机俄罗斯方块到游戏机的魂斗罗&#xff0c;从单机的红警CS到MMORPG的魔兽世界&#xff0c;从MOBA的英雄联盟到称霸的王者荣耀。 一个时代有一个时代的发展。游戏群体一路过关斩将&#xff0c;从最初的网瘾少年到现在全…

浅析目前网络游戏音乐概况

随着网络技术和计算机技术的迅速发展&#xff0c;网络小说、网络游戏等网络文化成为人们生活中的重要组成部分。尤其是网络游戏&#xff0c;近几年如同雨后春笋般层出不穷&#xff0c;同时游戏音乐也随之成为一个不可忽视的主体。游戏音乐一直处于被忽视的地位&#xff0c;粗制…

用Python制作十款经典的童年游戏(不会吧不会吧,不会真有人没玩过吧)

不知道大家童年是怎么度过的&#xff0c;黑羽的童年是在游戏世界里度过。这里黑羽分享一下十个python可以制作的经典游戏&#xff0c;看看有没有你的菜。 对了以下游戏皆是小学六年级的代码水平~~~ 如有不适&#xff0c;赶快学习 1、小鸟管道 使用模块&#xff1a;pygame代码长…

游戏开发之路(一):游戏开发概述

视频连接:游戏开发入门系列&#xff08;一&#xff09;&#xff1a;游戏开发概述 这是看了视频以及一个博主的笔记&#xff0c;自己总结的笔记留存使用。 视频梗概(提炼了一些有用的问题) 课程的目标是什么&#xff1f; 开始游戏开发之路 游戏是如何开发的,开发流程是什么&am…

通过游戏策划阶段防治游戏外挂

网络游戏外挂的名字一提起来是让很多网络游戏从业者和玩家都很愤怒的一件事&#xff0c;正是这些网络游戏外挂让我们游戏从业者天天背着众多玩家的责骂不说&#xff0c;更不可原谅的是我们辛苦的劳动成果遭受到了摧残&#xff0c;并且还要和因为网络游戏外挂而带来的诸多游戏问…

python没有pygame_Python制作十款经典的童年游戏(附源码)

不知道行友们每年六一是怎么度过的&#xff0c;行哥的童年是在游戏世界里度过。这里行哥分享一下十个python可以制作的经典游戏&#xff0c;看看有没有你的菜&#xff0c;代码链接放在文末 对了以下游戏皆是小学六年级的代码水平 如有不适&#xff0c;赶快学习 1、小鸟管道 使用…

110种有趣的游戏和应用

又一次&#xff0c;我们庆祝夏天的到来&#xff0c;和夏天一同来到的还有一系列开源的高品质游戏。今年的最佳游戏列表在去年的基础上&#xff0c;增加了一些好玩的游戏&#xff0c;同时删除了一些不再处于活跃开发状态的游戏。在这个列表中&#xff0c;你会发现街机类游戏&…

100个精彩的开源游戏

街机游戏 1、Andys Super Great Park 骑在过山车上&#xff0c;躲避障碍的同时收集气球。游戏有25关&#xff0c;另外还有18关需要得到高分才能解锁。支持的操作系统&#xff1a;Windows,Linux,Android。 2、Armagetron Advanced 这是Tron的3D克隆版。在游戏中&#xff0c;你需…

windows7经典开机音乐_那些经典的单机游戏背景音乐,带你找寻童年记忆

《超级玛丽》BGM 如果要列举最经典的游戏角色&#xff0c;那么相信马里奥兄弟一定榜上有名。这款发并于1985年出品的著名横版过关游戏&#xff0c;最早在红白机上推出&#xff0c;有多款后续作品&#xff0c;迄今多个版本合共销量已突破5亿4000万套&#xff0c;承载了几代人的记…
最新文章