| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 774631 | Magikarp4000 | Radio Towers (IOI22_towers) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n'
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
struct Query {
int idx,x,y;
};
const int MAXN = 1e5+1, BLOCK = 400;
int n,m,q;
int p[MAXN], sz[MAXN], res[MAXN];
vector<pair<PII,PII>> e;
vector<Query> qu1, qu2;
int ans, mp[MAXN];
set<PII> h;
vector<PII> edges;
int wt[MAXN];
vector<int> v[MAXN];
int val[MAXN];
bool z[MAXN], z1[MAXN], z2[MAXN], z3[MAXN];
bool prnt[MAXN];
int finds(int a) {
if (p[a] != a) p[a] = finds(p[a]);
return p[a];
}
void unite(int a, int b) {
a = finds(a);
b = finds(b);
if (a != b) {
if (sz[a] < sz[b]) swap(a,b);
p[b] = a;
sz[a] += sz[b];
}
}
void dfs(int s) {
if (z[s]) return;
z[s] = 1;
ans += sz[s];
FORX(u,v[s]) {
dfs(u);
}
}
bool cmp(const Query& a, const Query& b) {
return a.y > b.y;
}
signed main() {
OPTM;
cin >> n >> m;
FOR(i,0,m) {
int a,b,w; cin >> a >> b >> w;
e.PB({{w,i},{a,b}});
h.insert({-w,i});
edges.PB({a,b});
wt[i] = w;
}
cin >> q;
int i = 0;
while (i < q) {
int bruh = 0;
FORX(u,h) {
e[bruh] = {{-u.F,u.S},edges[u.S]};
bruh++;
}
FOR(l,0,m) mp[e[l].F.S] = l;
qu1.clear(); qu2.clear();
FOR(l,1,n+1) {
p[l] = l;
sz[l] = 1;
}
int j = 0;
vector<int> vis;
while (j < BLOCK && i < q) {
int t,s,w; cin >> t >> s >> w;
if (t == 1) {
qu1.PB({i,s-1,w});
if (!z3[s-1]) {
z3[s-1] = 1;
vis.PB(s-1);
}
}
else {
qu2.PB({i,s,w});
prnt[i] = 1;
}
j++; i++;
}
sort(ALL(qu2),cmp);
vector<pair<int,PII>> e1;
FOR(j,0,m) if (!z3[e[j].F.S]) e1.PB({e[j].F.F,e[j].S});
int en = e1.size();
int q1n = qu1.size(), q2n = qu2.size();
int k = 0;
FOR(j,0,q2n) {
while (k < en && e1[k].F >= qu2[j].y) {
unite(e1[k].S.F, e1[k].S.S);
k++;
}
ans = 0;
FOR(l,0,q1n) {
int pos = mp[qu1[l].x], w = qu1[l].y;
if (qu1[l].idx < qu2[j].idx) val[pos] = w;
else if (!val[pos]) val[pos] = e[pos].F.F;
}
vector<int> toclear;
FOR(l,0,q1n) {
int pos = mp[qu1[l].x];
if (!z1[pos] && val[pos] >= qu2[j].y) {
int a = finds(e[pos].S.F), b = finds(e[pos].S.S);
z1[pos] = 1;
v[a].PB(b);
v[b].PB(a);
if (!z2[a]) {
z2[a] = 1;
toclear.PB(a);
}
if (!z2[b]) {
z2[b] = 1;
toclear.PB(b);
}
}
}
int start = finds(qu2[j].x);
dfs(start);
if (!z2[start]) {
z2[start] = 1;
toclear.PB(start);
}
res[qu2[j].idx] = ans;
FORX(u,toclear) {
z[u] = z2[u] = 0;
v[u].clear();
}
FORX(u,vis) z3[u] = 0;
FOR(l,0,q1n) val[mp[qu1[l].x]] = z1[mp[qu1[l].x]] = 0;
}
FOR(l,0,q1n) {
int pos = qu1[l].x;
h.erase({-wt[pos],pos});
wt[pos] = qu1[l].y;
h.insert({-wt[pos],pos});
}
}
FOR(i,0,q) if (prnt[i]) cout << res[i] << ln;
}