当前位置: 首页 > news >正文

【还未找到原题】宝石(GEM) - Harvey

题意

给定 \(m\) 对关系,表示 \(a\)\(b\) 小,此时问最先确定每一个点的排名的关系最小编号,如果最后还未确定排名,则此点输出-1。
由于没有原题,给个样例:
input:

4 4
2 4
3 1
4 1
2 3

output:

3 4 -1 -1

思路

首先容易想到建有向图,边权就是每一条边的编号。
考虑对于一个确定排名的点 \(u\),要确定它后面的点都比它大,则需要求它到每一个它后面的点的边权最大值,最后在所有它后面的点取个 \(max\) 就行。
但这样显然超时,考虑到每一个 \(u\) 编号后面的点中所有是由排名大于 \(u\) 的点指向另一个排名大于 \(u\) 的点的边都有可能成为答案边。所以可以简化成对于一个点 \(v\)\(v\)\(u\) 后面,排名不小于 \(u\) 的点指向 \(v\)的取个最小值,最后所有不小于 \(u\) 的点全部取个最大值就可以算出其中一半的答案,这里明显可以用两个 \(set\) 来维护,一个维护每个点的,一个维护整体的。
然后倒着连反边再做一遍可以算出前面的。

code

#include<bits/stdc++.h>
#define ll int
#define pll pair<ll,ll>
#define x first
#define y second
#define mp make_pairusing namespace std;const int N = 2e5+5,M = 8e5+5;struct edge{ll u,v;
}g[M];
struct Edge{int to,nxt;int w; 
}e[M];ll n,m;
int head[N];
int tot;
void add_Edge(int u,int v,int w){e[tot].to=v,e[tot].nxt=head[u];e[tot].w=w;head[u]=tot++;
}
ll du[N];
ll res[N],f[N];
set<ll> st[N],p;void init(){tot=0;memset(du,0,sizeof(du));memset(head,-1,sizeof(head));
}
void solve(){init();for(int i=1;i<=m;i++){ll u=g[i].u,v=g[i].v;add_Edge(u,v,i);st[v].insert(i);}queue<ll> q;for(int i=1;i<=n;i++){if(st[i].empty())q.push(i);else p.insert(*st[i].begin());}for(int i=1;i<=n;i++){ll u=q.front();q.pop();if(q.empty()){res[u]+=n-i;if(!p.empty())f[u]=max(f[u],*p.rbegin());}for(int j=head[u];~j;j=e[j].nxt){int v=e[j].to,w=e[j].w;p.erase(*st[v].begin());st[v].erase(w);if(!st[v].empty())p.insert(*st[v].begin());else q.push(v);}}
}
int main() {freopen("gem.in","r",stdin);freopen("gem.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++)cin>>g[i].u>>g[i].v;solve();for(int i=1;i<=m;i++)swap(g[i].u,g[i].v);solve();for(int i=1;i<=n;i++){if(res[i]!=n-1)cout<<"-1 ";else cout<<f[i]<<" ";}return 0;
} 
http://www.hskmm.com/?act=detail&tid=21009

相关文章:

  • 第八篇
  • C# AStar 算法 - 实际应用
  • nocobase 源码安装
  • 航司网站url后缀参数FECU分析
  • 子网掩码完全指南:从入门到精通
  • 微信群机器人API
  • 9月29号
  • 【CF19E】Fairy - Harvey
  • Python从入门到实战 (14):工具落地:用 PyInstaller 打包 Python 脚本为可执行文件 - 实践
  • Harmony实现流转开发之音乐播放器跨设备流转 - 实践
  • 软件工程中线性回归应用
  • 解决秒杀高并发的一些方案
  • 构建移动网关:Air780EPM用4G为WiFi和LAN设备供网
  • 9.29模拟赛总结
  • 多corner综合
  • 优化 if/else 的四种设计模式
  • Day11-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\oop\demo06
  • 牛客周赛 Round 111
  • OpenLayers地图交互 -- 章节十一:拖拽材料交互详解
  • 2025年人工智能与智能装备国际学术会议(AIIE 2025)
  • 通过IDOR实现权限提升导致未授权用户注入
  • APUE学习笔记之基础知识(一) - Invinc
  • Syslog日志集成搭建
  • 定义工业生产新范式!网易灵动发布全球首款全域智能无人装载机“灵载”
  • 国有银行人力资源数字化转型的合规突围与效能跃迁
  • Java 类类型
  • OpenFeign 继承FeignClient客户端注意事项
  • 9月29日
  • JVM调优实战及常量池详解
  • Cisco Identity Services Engine (ISE) 3.5 - 基于身份的网络访问控制和策略实施系统