이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
using ll = long long;
using int128 = __int128_t;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define TRAV(e, a) for (const auto &e : a)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;
template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
out << "[";
for (auto it = obj.begin(); it != obj.end(); it++) {
out << &", "[2 * (it == obj.begin())] << *it;
}
return out << "]";
}
template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
return out << "(" << obj.first << ", " << obj.second << ")";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
bool st2 = true, st4 = true;
ll n, m;
cin >> n >> m;
st2 &= (m == n - 1);
vec<vec<pll>> graph(n + 1);
vec<ll> w(m + 1);
CFOR(i, 1, m) {
ll a, b;
cin >> a >> b >> w[i];
graph[a].push_back({b, i});
graph[b].push_back({a, i});
st2 &= (a + 1 == b);
}
ll q;
cin >> q;
vec<vec<ll>> queries(q, vec<ll>(4));
FOR(i, 0, q) {
cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
queries[i][3] = i;
st4 &= (queries[i][0] == 2);
}
if (st2) {
const ll SZ = 3;
vec<ll> b(n / SZ + 1, 1e9);
CFOR(i, 0, n - 1) b[i / SZ] = min(b[i / SZ], w[i]);
FOR(i, 0, q) {
if (queries[i][0] == 1) {
ll bind = queries[i][1] / SZ;
w[queries[i][1]] = queries[i][2];
b[bind] = 1e9;
FOR(i, bind * SZ, min((bind + 1) * SZ, n)) {
b[bind] = min(b[bind], w[i]);
}
} else {
ll bind = queries[i][1] / SZ;
if (queries[i][2] > b[bind]) {
ll l = queries[i][1], r = queries[i][1];
while (1 < l && w[l - 1] >= queries[i][2]) l--;
while (r < n && w[r] >= queries[i][2]) r++;
cout << r - l + 1 << "\n";
} else {
ll bl = bind, br = bind;
while (0 < bl && b[bl - 1] >= queries[i][2]) bl--;
while (br < b.size() && b[br] >= queries[i][2]) br++;
ll l = bl * SZ;
ll r = min(br * SZ, n);
while (1 < l && w[l - 1] >= queries[i][2]) l--;
while (r < n && w[r] >= queries[i][2]) r++;
cout << r - l + 1 << "\n";
}
}
}
} else if (st4) {
sort(all(queries), [&](const vec<ll> &o1, const vec<ll> &o2) {
return o1[2] > o2[2];
});
vec<ll> parent(n + 1), sz(n + 1, 1);
iota(all(parent), 0ll);
function<ll(ll)> find = [&](ll x) -> ll {
if (x != parent[x]) parent[x] = find(parent[x]);
return parent[x];
};
function<void(ll, ll)> unify = [&](ll x, ll y) {
x = find(x);
y = find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
if (graph[y].size() > graph[x].size()) swap(graph[x], graph[y]);
parent[y] = x;
sz[x] += sz[y];
TRAV(e, graph[y]) {
if (find(x) != find(e.first)) graph[x].push_back(e);
}
};
vec<ll> ans(q);
FOR(i, 0, q) {
set<ll> visited;
function<void(ll)> dfs = [&](ll curr) {
visited.insert(curr);
TRAV(e, graph[curr]) {
if (visited.count(find(e.first)) ||
queries[i][2] > w[e.second])
continue;
dfs(find(e.first));
}
};
dfs(find(queries[i][1]));
TRAV(e, visited) unify(e, *visited.begin());
ans[queries[i][3]] = sz[find(queries[i][1])];
}
TRAV(e, ans) cout << e << "\n";
} else {
vec<bool> visited(n + 1);
FOR(i, 0, q) {
if (queries[i][0] == 1) {
w[queries[i][1]] = queries[i][2];
} else {
fill(all(visited), 0ll);
function<void(ll)> dfs = [&](ll curr) {
visited[curr] = 1;
TRAV(e, graph[curr]) {
if (visited[e.first] || queries[i][2] > w[e.second])
continue;
dfs(e.first);
}
};
dfs(queries[i][1]);
cout << accumulate(all(visited), 0ll) << "\n";
}
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
bridges.cpp: In function 'int main()':
bridges.cpp:85:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while (br < b.size() && b[br] >= queries[i][2]) br++;
| ~~~^~~~~~~~~~
# | 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... |