이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fastInput ios::sync_with_stdio(false); cin.tie(nullptr);
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
const int inf = 1e9 + 7;
struct CentroidDecomposition {
vvp graph;
vi subSize;
int n;
int centroid = -1;
void init(int N, vvp& g) {
n = N;
graph = g;
subSize.resize(n + 1);
}
void dfs(int v, int p) {
subSize[v] = 1;
for (int i = 0; i < graph[v].size(); i++) {
int u = graph[v][i].first;
if (u != p) {
dfs(u, v);
subSize[v] += subSize[u];
}
}
}
int findCentroid(int v, int p) {
for (int i = 0; i < graph[v].size(); i++) {
int u = graph[v][i].first;
if (u != p && subSize[u] > n / 2) {
return findCentroid(u, v);
}
}
return v;
}
int getCentroid() {
if (centroid == -1) {
dfs(1, 1);
centroid = findCentroid(1, 1);
}
return centroid;
}
};
struct segmentTree {
vi st;
int size;
void init(int n) {
for (size = 1; size < n; size *= 2) {}
st.resize(2 * size);
}
void update(int index, int val) {
index += size;
st[index] = val;
for (index /= 2; index; index /= 2) {
st[index] = min(st[index * 2], st[index * 2 + 1]);
}
}
int query(int l, int r) {
int ans = INT_MAX;
for (l += size, r += size; l <= r; l /= 2, r /= 2) {
if (l % 2) {
ans = min(ans, st[l]);
l++;
}
if (r % 2 == 0) {
ans = min(ans, st[r]);
r--;
}
}
return ans;
}
};
vector<vp> graph;
vll weight;
vb visited;
segmentTree st;
int lastTrue(int s,int k, int lo, int hi) {
lo--;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
bool curr = k <= st.query(s, mid);
if (curr) {
lo = mid;
}
else {
hi = mid - 1;
}
}
return lo;
}
int firstTrue(int s, int k, int lo, int hi) {
hi++;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
bool curr = k <= st.query(mid, s);
if (curr) {
hi = mid;
}
else {
lo = mid + 1;
}
}
return lo;
}
inline int findAmount(int root, int k, int n) {
int ans = 1;
int left = lastTrue(root, k, root, n - 1);
ans += left - root + 1;
int right = firstTrue(root - 1, k, 1, root - 1);
ans += root - 1 - right + 1;
return ans;
}
inline void mergeSets(set<pii> &a, set<pii> &b, int w) {
auto it = b.begin();
for (int i = 0; i < b.size(); i++) {
pii curr = *it;
if (curr.first > w)curr.first = w;
auto f = a.lower_bound({ curr.first,-1 });
if (f != a.end() && ((pii)*f).first == curr.first) {
pii val = { curr.first, curr.second + ((pii)*f).second };
a.erase(f);
a.insert(val);
}
else {
a.insert(curr);
}
it++;
}
}
vp bridges;
vp par;
vi depth;
vector<set<pii>> hold;
void dfs(int v, int p, int d, int wp) {
depth[v] = d;
par[v] = { p,wp };
hold[v].insert({ inf,1 });
for (int i = 0; i < graph[v].size(); i++) {
int u = graph[v][i].first;
ll w = weight[graph[v][i].second];
if (u != p) {
dfs(u, v, d + 1, graph[v][i].second);
mergeSets(hold[v], hold[u], w);
}
}
}
inline void updatehold(int index) {
pii edge = bridges[index];
int upper = edge.first;
int lower = edge.second;
if (depth[upper] > depth[lower]) swap(upper, lower);
int v = lower;
while (par[v].first != v) {
v = par[v].first;
hold[v].clear();
hold[v].insert({ inf,1 });
for (int i = 0; i < graph[v].size(); i++) {
int u = graph[v][i].first;
ll w = weight[graph[v][i].second];
if (u != par[v].first) {
mergeSets(hold[v], hold[u], w);
}
}
}
}
inline int getsub(int v, int w) {
int ans = 0;
auto it = hold[v].end();
it--;
for (int i = 0; i < hold[v].size(); i++) {
pii curr = *it;
if (w > curr.first) return ans;
ans += curr.second;
it--;
}
return ans;
}
inline int maxReach(int v, int w) {
if (v == par[v].first)return v;
if (w <= weight[par[v].second]) {
return maxReach(par[v].first, w);
}
return v;
}
inline int queryCount(int s, int w) {
int p = maxReach(s, w);
int pc = getsub(p, w);
int sc = getsub(s, w);
if (p == par[s].first) sc = 1;
int ans = pc - sc + 1;
return ans;
}
int main() {
fastInput;
int n, m;
cin >> n >> m;
//st.init(n);
graph.resize(n + 1);
weight.resize(m + 1);
bridges.resize(m + 1);
par.resize(n + 1);
depth.resize(n + 1);
hold.resize(n + 1);
int a, b, d;
for (int i = 1; i <= m; i++) {
cin >> a >> b >> d;
graph[a].push_back({ b,i });
graph[b].push_back({ a,i });
bridges[i] = { a,b };
weight[i] = d;
//st.update(i, d);
}
CentroidDecomposition cd;
cd.init(n + 1, graph);
int root = cd.getCentroid();
dfs(root, root, 1, -1);
int q;
cin >> q;
int t;
for (int i = 0; i < q; i++) {
cin >> t;
if (t == 1) {
int r;
cin >> b >> r;
weight[b] = r;
updatehold(b);
}
else {
int s, w;
cin >> s >> w;
int ans = queryCount(s, w);
cout << ans << endl;
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bridges.cpp: In member function 'void CentroidDecomposition::dfs(int, int)':
bridges.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i = 0; i < graph[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
bridges.cpp: In member function 'int CentroidDecomposition::findCentroid(int, int)':
bridges.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i < graph[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void mergeSets(std::set<std::pair<int, int> >&, std::set<std::pair<int, int> >&, int)':
bridges.cpp:145:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int i = 0; i < b.size(); i++) {
| ~~^~~~~~~~~~
bridges.cpp: In function 'void dfs(int, int, int, int)':
bridges.cpp:168:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for (int i = 0; i < graph[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void updatehold(int)':
bridges.cpp:191:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | for (int i = 0; i < graph[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int getsub(int, int)':
bridges.cpp:207:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for (int i = 0; i < hold[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
# | 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... |