NOI2015D1T1 | 程式自动分析

Portal

OI 中离散化方法很多,常见的有 std::sort std::unique,然后 std::find 查找键值对,也可以用 std::map<key,val> 直接进行 insert()find() 。不过 map 不吸氧气几乎要 T 掉,sort unique 也不算快。观察数据范围发现最多只有 100,000 对关系,不同的数最多只有 200,000 种,可以考虑进行简单取膜 hash,取一个稍大于 200,000 的素数作为膜数,取膜后扔进并查集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <utility>
typedef std::pair<int,int> pii;
const int _=1e5+1,P=200003;
int n,cnt,flag,f[P+1];pii ieq[_];
int read() {
int x=0,c=getchar();
while(c<48||c>57) c=getchar();
while(c>47&&c<58) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x;
}
void init() {for(int i=0;i<=P;f[++i]=i);cnt=0;flag=1;}
int get(int x) {while(f[x]^x) x=f[x]=f[f[x]];return x;}
void unite(const int& x,const int& y) {f[get(x)]=get(y);}
int main() {
for(int t=read();t;--t) {
n=read();init();
for(int i=0,x,y,opt;i<n;++i) {
x=(read()%P)+1,y=(read()%P)+1,opt=read();
if(opt) unite(x,y);
else ieq[++cnt]=(pii){x,y};
}
for(int i=1;i<=cnt;++i)
if(get(ieq[i].first)==get(ieq[i].second)) {flag=0;break;}
puts(flag? "YES":"NO");
}
return 0;
}

Download

虽然很容易运行时间 rank 1,但是还是有一点风险。

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。