이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int SIZ = 300;
int n, m, q, br;
int tip[MAXN], qx[MAXN], qv[MAXN];
int a[MAXN], b[MAXN], w[MAXN], sol[MAXN];
set < pair <int, int> > st;
set < pair <int, int> > :: iterator it;
int par[MAXN], siz[MAXN], na[MAXN], nb[MAXN], novi[MAXN], bio[MAXN];
bool ok[MAXN];
vector < pair <int, int> > upiti;
vector <int> curr, magic, visited;
vector <pair <int, int> > v[MAXN];
void load () {
cin >> n >> m;
for (int i=1; i<=m; i++) {
cin >> a[i] >> b[i] >> w[i];
st.insert(make_pair(w[i], i));
}
st.insert(make_pair(0, 0));
cin >> q;
for (int i=1; i<=q; i++) {
cin >> tip[i] >> qx[i] >> qv[i];
}
}
int nadi (int x) {
if (x == par[x]) return x;
return par[x] = nadi(par[x]);
}
void spoji (int x, int y) {
x = nadi(x); y = nadi(y);
if (x == y) return;
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
par[y] = x;
}
int lim;
void dfs (int x) {
if (bio[x]) return;
bio[x] = 1;
visited.push_back(x);
br += siz[x];
for (auto sus : v[x]) {
if (sus.second >= lim) dfs(sus.first);
}
}
void obradi_upit (int ind) {
for (auto e : magic) novi[e] = w[e];
for (auto i : curr) {
if (i >= ind) break;
novi[qx[i]] = qv[i];
}
for (auto e : magic) {
na[e] = nadi(a[e]);
nb[e] = nadi(b[e]);
//cout << "edge " << e << " " << na[e] << " " << nb[e] << " " << novi[e] << endl;
}
for (auto e : magic) {
v[na[e]].push_back(make_pair(nb[e], novi[e]));
v[nb[e]].push_back(make_pair(na[e], novi[e]));
}
visited.clear();
br = 0; lim = qv[ind];
dfs(nadi(qx[ind]));
sol[ind] = br;
for (auto x : visited) {
bio[x] = 0;
}
for (auto e : magic) {
v[na[e]].clear();
v[nb[e]].clear();
}
}
void obradi_bucket (int ll, int rr) {
for (int i=1; i<=n; i++) {
par[i] = i; siz[i] = 1;
}
upiti.clear(); curr.clear(); magic.clear();
for (int i = ll; i <= rr; i++) {
if (tip[i] == 1) {
ok[qx[i]] = 1;
magic.push_back(qx[i]);
curr.push_back(i);
} else {
upiti.push_back(make_pair(qv[i], i));
}
}
sort(magic.begin(), magic.end());
magic.erase(unique(magic.begin(), magic.end()), magic.end());
sort(upiti.begin(), upiti.end());
it = st.end(); it--;
for (int i = (int)upiti.size()-1; i >= 0; i--) {
int ind = upiti[i].second;
//cout << "sad na upitu " << ind << " " << qv[ind] << endl;
while ((it -> first) >= qv[ind]) {
if (ok[it -> second] == 0) spoji(a[it -> second], b[it -> second]);
it--;
}
//cout << "sad cu ga obradit" << endl;
obradi_upit(ind);
}
for (auto i : curr) {
ok[qx[i]] = 0;
st.erase(make_pair(w[qx[i]], qx[i]));
w[qx[i]] = qv[i];
st.insert(make_pair(w[qx[i]], qx[i]));
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
load();
for (int i=1; i<=q; i += SIZ) {
obradi_bucket(i, min(i + SIZ - 1, q));
}
for (int i=1; i<=q; i++) {
if (tip[i] == 2) cout << sol[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... |