이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)
using namespace std;
const int nax = 1e5 + 111;
const int M = 600;
int n, m, q;
struct edge {
int a, b, c;
};
edge e[nax];
struct gao {
int l, r, a, b, c;
gao () {}
gao (int l, int r, int a, int b, int c) : l(l), r(r), a(a), b(b), c(c) {}
};
vector <gao> v;
int p[nax];
int t[nax][3];
int ans[nax];
struct uf {
int p[nax];
int ile[nax];
void init() {
for(int i = 1; i <= n; ++i) {
p[i] = i;
ile[i] = 1;
}
}
int find(int x) {
if(x == p[x])
return x;
return p[x] = find(p[x]);
}
void unia(int x, int y) {
x = find(x);
y = find(y);
if(x != y) {
p[x] = y;
ile[y] += ile[x];
}
}
} ja;
struct qu {
int v, w, id;
};
vector <gao> big;
vector <gao> small;
vector <qu> qq;
vector <int> graf[nax];
vector <int> nodes;
bool odw[nax];
void dfs(int u) {
nodes.pb(u);
odw[u] = 1;
for(auto it : graf[u])
if(!odw[it])
dfs(it);
}
void add(int a, int b) {
graf[a].pb(b);
graf[b].pb(a);
}
void del(int a, int b) {
graf[a].pop_back();
graf[b].pop_back();
}
void solve(int L, int R) {
ja.init();
qq.clear();
small.clear();
big.clear();
for(auto it : v) {
if(it.l <= L && R <= it.r)
big.pb(it);
else if(!(it.r < L || R < it.l))
small.pb(it);
}
sort(big.begin(), big.end(), [](gao x, gao y) {
return x.c < y.c;
});
for(int i = L; i <= R; ++i)
if(t[i][0] == 2)
qq.pb({t[i][1], t[i][2], i});
sort(qq.begin(), qq.end(), [](qu x, qu y) {
return x.w < y.w;
});
int j = ss(big) - 1;
for(int i = ss(qq) - 1; 0 <= i; --i) {
qu on = qq[i];
while(0 <= j && on.w <= big[j].c) {
ja.unia(ja.find(big[j].a), ja.find(big[j].b));
j--;
}
for(auto it : small)
if(it.l <= on.id && on.id <= it.r && on.w <= it.c)
add(ja.find(it.a), ja.find(it.b));
nodes.clear();
dfs(ja.find(on.v));
for(auto it : nodes) {
odw[it] = 0;
ans[on.id] += ja.ile[it];
}
for(auto it : small)
if(it.l <= on.id && on.id <= it.r && on.w <= it.c)
del(ja.find(it.a), ja.find(it.b));
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; ++i) {
scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].c);
}
scanf("%d", &q);
for(int i = 1; i <= q; ++i) {
scanf("%d %d %d", &t[i][0], &t[i][1], &t[i][2]);
if(t[i][0] == 1) {
v.pb(gao(p[t[i][1]], i - 1, e[t[i][1]].a, e[t[i][1]].b, e[t[i][1]].c));
p[t[i][1]] = i;
e[t[i][1]].c = t[i][2];
}
}
for(int i = 1; i <= m; ++i)
v.pb(gao(p[i], q, e[i].a, e[i].b, e[i].c));
for(int i = 1; i <= q; i += M)
solve(i, min(q, i + M - 1));
for(int i = 1; i <= q; ++i)
if(t[i][0] == 2)
printf("%d\n", ans[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bridges.cpp: In function 'int main()':
bridges.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:146:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
bridges.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &t[i][0], &t[i][1], &t[i][2]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |