- [NOI2015] 程序自动分析
1
- @ 2026-7-20 10:24:03
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct DSU {
vector<int> sz, f;
DSU(int n) {
sz.assign(n + 1, 1);
f.assign(n + 1, 0);
for (int i = 1; i <= n; i++) f[i] = i;
}
int root(int u) {
if (u == f[u]) return u;
return root(f[u]);
}
void merge(int u, int v) {
u = root(u), v = root(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
sz[v] += sz[u];
f[u] = v;
}
int size(int u) {
return sz[root(u)];
}
bool same(int u, int v) {
return root(u) == root(v);
}
};
void solve() {
int m;
cin >> m;
vector<array<int, 3>> opt;
vector<int> b;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
b.push_back(x);
b.push_back(y);
opt.push_back({x, y, z});
}
sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end());
for (auto &[x, y, z] : opt) {
x = lower_bound(b.begin(), b.end(), x) - b.begin();
y = lower_bound(b.begin(), b.end(), y) - b.begin();
}
int n = b.size();
DSU dsu(n);
for (auto [x, y, z] : opt) {
if (z == 1) dsu.merge(x, y);
}
for (auto [x, y, z] : opt) {
if (z == 0) {
if (dsu.same(x, y)) {
cout << "NO\n"; return;
}
}
}
cout << "YES\n";
}
signed main() {
int t = 1;
cin >> t;
while (t--) solve();
}
/*
g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt
*/
1 条评论
-
刘皓丞 可达班2025 Lv.初识 @ 2026-8-3 9:34:05#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+100; int n,m;int fa[N]; struct aaa{ int a,b,op; }g[N]; unordered_map<int,int> mp; int father(int x){ if(x==fa[x]) return fa[x]; else return fa[x]=father(fa[x]); } void un(int a,int b){ int A=father(a),B=father(b); if(A==B) return ; fa[B]=A; } int o(int x){ if(mp.count(x)==false) mp[x]=++m; return mp[x]; } void so(){ cin>>n; mp.clear(); for(int i=1;i<N;i++) fa[i]=i; m=0; for(int i=1;i<=n;i++){ int x,y,op;cin>>x>>y>>op; g[i]={o(x),o(y),op}; if(op==1){ un(o(x),o(y)); } } for(int i=1;i<=n;i++){ int idx=g[i].op; if(idx==0){ if(father(g[i].a)==father(g[i].b)){ cout<<"NO"<<"\n"; return ; } } } cout<<"YES"<<"\n"; return; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int _;cin>>_; while(_--){ so(); } }
- 1
信息
- ID
- 484
- 时间
- ms
- 内存
- MiB
- 难度
- 6
- 标签
- 递交数
- 169
- 已通过
- 49
- 上传者