이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
#define N 50001
#define M 100001
int lnk[N], sz[N];
void build(int n){
fill(sz, sz+n+1, 1);
iota(lnk, lnk+n+1, 0);
}
int root(int x){
return lnk[x] == x ? x : (lnk[x] = root(lnk[x]));
}
void unite(int x, int y){
x = root(x), y = root(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
lnk[y] = x;
}
struct Edge {
int a, b, w, i;
bool operator < (const Edge &o) const { return make_pair(w, i) > make_pair(o.w, o.i); }
};
Edge edges[M], queries[M];
vector<int> adj[N];
bool vis[N];
int ans[M];
int32_t main(){
// input
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m; cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> edges[i].a >> edges[i].b >> edges[i].w;
edges[i].i = i;
}
int q; cin >> q;
for (int i = 1; i <= q; i++){
cin >> queries[i].a >> queries[i].b >> queries[i].w;
queries[i].i = i;
}
set<Edge> sorted;
for (int i = 1; i <= m; i++)
sorted.insert(edges[i]);
int bsz = ceil(sqrt(q));
for (int s = 1; s <= q; s += bsz){
build(n);
vector<Edge> qu;
map<int, int> changed;
for (int i = s; i < min(q+1, s+bsz); i++){
if (queries[i].a == 1)
changed[queries[i].b] = edges[queries[i].b].w;
else
qu.push_back(queries[i]);
}
sort(qu.begin(), qu.end());
auto it = sorted.begin();
for (auto [_, s, w, idx] : qu){
for (; it != sorted.end() && it->w >= w; it++)
if (!changed.count(it->i))
unite(it->a, it->b);
map<int, int> curr(changed);
for (int i = s; i < idx; i++)
if (queries[i].a == 1)
curr[queries[i].b] = queries[i].w;
vector<int> graph;
for (auto [ei, ew] : curr){
if (ew >= w && root(edges[ei].a) != root(edges[ei].b)){
adj[root(edges[ei].a)].push_back(root(edges[ei].b));
adj[root(edges[ei].b)].push_back(root(edges[ei].a));
graph.push_back(root(edges[ei].a));
graph.push_back(root(edges[ei].b));
}
}
queue<int> q;
q.push(root(s));
vis[root(s)] = true;
while (!q.empty()){
int u = q.front();
q.pop();
ans[idx] += sz[u];
for (int v : adj[u]){
if (!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
for (int i : graph) vis[i] = false;
for (auto [ei, ew] : curr){
adj[root(edges[ei].a)].clear();
adj[root(edges[ei].b)].clear();
}
}
for (int i = s; i < min(q+1, s+bsz); i++)
if (queries[i].a == 1)
changed[queries[i].b] = queries[i].w;
for (auto [i, w] : changed){
sorted.erase(edges[i]);
edges[i].w = w;
sorted.insert(edges[i]);
}
}
for (int i = 1; i <= q; i++)
if (ans[i])
cout << ans[i] << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |