이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define ll long long
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define readl(_s) getline(cin, (_s));
#define boost() cin.tie(0); cin.sync_with_stdio(0)
struct edge {
int u = 0, v = 0, w = 0, i = 0, t = 0;
};
struct query {
int t = 0, u = 0, v = 0, i = 0;
};
bool cmp(edge x, edge y) {
return x.w > y.w;
}
bool cmq(query x, query y) {
return x.u > y.u;
}
const int MN = 50005, MM = 100005, SQRT = 700;
int n, m, q, par[MN], sz[MN], unst[MM], ans[MM], tmp, vis[MN];
edge e[MM], E[MM];
query Q[MM];
vector<int> a[MN];
int find(int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
inline bool merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (sz[x] > sz[y]) {
par[y] = par[x];
sz[x] += sz[y];
} else {
par[x] = par[y];
sz[y] += sz[x];
}
return true;
}
void dfs(int cur) {
vis[cur] = 1;
tmp += sz[cur];
for (int nxt : a[cur]) if (!vis[nxt]) dfs(nxt);
}
void sfd(int cur) {
vis[cur] = 0;
for (int nxt : a[cur]) if (vis[nxt]) sfd(nxt);
}
int main() {
boost();
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w; e[i].i = i;
E[i] = e[i];
}
cin >> q;
for (int i = 1; i <= q; i++) {
cin >> Q[i].t >> Q[i].u >> Q[i].v; Q[i].i = i;
if (Q[i].t == 2) swap(Q[i].u, Q[i].v);
}
for (int I = 1; I <= q; I += SQRT) {
int lft = I, rit = min(q, I + SQRT - 1); //range of currently processed block
for (int i = 1; i <= m; i++) e[i] = E[i], unst[i] = 0;
sort(e + 1, e + m + 1, cmp);
vector<query> qs;
deque<edge> edges;
vector<int> chg;
for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
for (int i = lft; i <= rit; i++) {
if (Q[i].t == 1) {
unst[Q[i].u] = 1;
chg.push_back(Q[i].u);
edges.push_front({E[Q[i].u].u, E[Q[i].u].v, Q[i].v, i, Q[i].u});
} else {
qs.push_back(Q[i]);
}
}
sort(chg.begin(), chg.end());
chg.erase(unique(chg.begin(), chg.end()), chg.end());
sort(qs.begin(), qs.end(), cmq);
int id = 1;
for (query cur : qs) { //maybe we try to run dfs instead of dsu + undo will get rid of log?
while (id <= m && e[id].w >= cur.u) {
if (!unst[e[id].i]) merge(e[id].u, e[id].v);
id++;
}
vector<pii> add;
for (edge ed : edges) {
if (ed.i > cur.i || !unst[ed.t]) continue;
unst[ed.t] = 0;
if (ed.w >= cur.u) { //add this as an edge to the graph
int u = find(ed.u), v = find(ed.v);
if (u == v) continue;
a[u].push_back(v);
a[v].push_back(u);
add.push_back({u, v});
}
}
for (int i : chg) {
if (unst[i] && E[i].w >= cur.u) { //add this as an edge to the graph
int u = find(E[i].u), v = find(E[i].v);
if (u == v) continue;
a[u].push_back(v);
a[v].push_back(u);
add.push_back({u, v});
}
}
tmp = 0; dfs(find(cur.v));
ans[cur.i] = tmp;
//reset all ur stuff
sfd(find(cur.v));
for (pii p : add) a[p.f].pop_back(), a[p.s].pop_back();
for (int i : chg) unst[i] = 1;
}
for (int i = lft; i <= rit; i++) {
if (Q[i].t == 1) E[Q[i].u].w = Q[i].v;
else printf("%d\n", ans[i]);
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bridges.cpp:2:0: warning: ignoring #pragma GCC option [-Wunknown-pragmas]
#pragma GCC option("arch=native","tune=native","no-zero-upper")
# | 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... |