제출 #1054752

#제출 시각아이디문제언어결과실행 시간메모리
1054752VMaksimoski008Dynamic Diameter (CEOI19_diameter)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> //#define int long long using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; struct SegTree { int n; vector<ll> tree, lazy; SegTree(int _n) : n(_n), tree(4*_n+50), lazy(4*_n+50) {} void push(int u, int tl, int tr) { if(!lazy[u]) return ; tree[u] += lazy[u]; if(tl != tr) { lazy[2*u] += lazy[u]; lazy[2*u+1] += lazy[u]; } lazy[u] = 0; } void update(int u, int tl, int tr, int l, int r, ll v) { push(u, tl, tr); if(l > tr || tl > r) return ; if(l <= tl && tr <= r) { lazy[u] += v; push(u, tl, tr); return ; } int tm = (tl + tr) / 2; update(2*u, tl, tm, l, r, v); update(2*u+1, tm+1, tr, l, r, v); tree[u] = max(tree[2*u], tree[2*u+1]); } ll query(int u, int tl, int tr, int l, int r) { if(l > tr || tl > r) return 0; if(l <= tl && tr <= r) return tree[u]; int tm = (tl + tr) / 2; return max(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r)); } void update(int l, int r, ll v) { update(1, 0, n-1, l, r, v); } ll query(int l, int r) { return query(1, 0, n-1, l, r); } }; ll n, W; int d[maxn], par[maxn], in[maxn], out[maxn], T[maxn], mx_dep=0, timer=0; ll val[maxn], dp[maxn][3], dist[maxn]; vector<pll> gshit[maxn]; vector<int> graph[maxn]; void dfs1(int u, int p, int c) { in[u] = timer++; T[u] = c; mx_dep = max(mx_dep, d[u]); for(auto &[v, w] : gshit[u]) { if(v == p) continue; d[v] = d[u] + 1; dist[v] = dist[u] + w; val[v] = w; par[v] = u; dfs1(v, u, (u==1?v:c)); } out[u] = timer-1; } void dfs(int u) { if(u == 0) return ; dp[u][0] = dp[u][1] = dp[u][2] = 0; ll mx1=0, mx2=0; for(int &v : graph[u]) { if(v == par[u]) continue; dp[u][0] = max(dp[u][0], dp[v][0] + val[v]); dp[u][2] = max(dp[u][2], dp[v][2]); if(dp[v][0] + val[v] >= mx1) { mx2 = mx1; mx1 = dp[v][0] + val[v]; } else if(dp[v][0] + val[v] >= mx2) { mx2 = dp[v][0] + val[v]; } } dp[u][1] = mx1 + mx2; dp[u][2] = max(dp[u][2], max(dp[u][0], dp[u][1])); dfs(par[u]); } void dfs2(int u, int p) { ll mx1=0, mx2=0; for(int &v : graph[u]) { if(v == p) continue; dfs2(v, u); dp[u][0] = max(dp[u][0], dp[v][0] + val[v]); dp[u][2] = max(dp[u][2], dp[v][2]); if(dp[v][0] + val[v] >= mx1) { mx2 = mx1; mx1 = dp[v][0] + val[v]; } else if(dp[v][0] + val[v] >= mx2) { mx2 = dp[v][0] + val[v]; } } dp[u][1] = mx1 + mx2; dp[u][2] = max(dp[u][2], max(dp[u][0], dp[u][1])); } signed main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int q; cin >> n >> q >> W; vector<array<ll, 3> > edges; for(int i=0; i<n-1; i++) { ll a, b, w; cin >> a >> b >> w; edges.push_back({ a, b, w }); gshit[a].push_back({ b, w }); gshit[b].push_back({ a, w }); graph[a].push_back(b); graph[b].push_back(a); } dfs1(1, 1, 0); for(auto &[a, b, w] : edges) if(d[a] > d[b]) swap(a, b); if(mx_dep <= 1) { multiset<ll> ms; for(auto &[a, b, w] : edges) ms.insert(w); ll last = 0; while(q--) { ll d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % W; ms.erase(ms.find(edges[d][2])); edges[d][2] = e; ms.insert(e); auto it = --ms.end(); ll ans = *it; if(it != ms.begin()) ans += *(--it); cout << ans << '\n'; last = ans; } return 0; } if(mx_dep <= 20 || (n <= 5000 && q <= 5000)) { ll last = 0; dfs2(1, 1); while(q--) { ll d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % W; val[edges[d][1]] = e; dfs(edges[d][0]); cout << dp[1][2] << '\n'; last = dp[1][2]; } return 0; } //mora niz kecot SegTree tree(n); multiset<ll> ms; for(int i=1; i<=n; i++) tree.update(in[i], in[i], dist[i]); for(int &v : graph[1]) ms.insert(tree.query(in[v], out[v])); ll last = 0; while(q--) { ll d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % W; int x = edges[d][1]; ms.erase(ms.find(in[T[x]], out[T[x]])); tree.update(in[x], out[x], -edges[d][2]); edges[d][2] = e; tree.update(in[x], out[x], edges[d][2]); ms.insert(tree.query(in[T[x]], out[T[x]])); auto it = --ms.end(); ll ans = *it; if(it != ms.begin()) ans += *(--it); cout << ans << '\n'; last = ans; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

diameter.cpp: In function 'int main()':
diameter.cpp:198:45: error: no matching function for call to 'std::multiset<long long int>::find(int&, int&)'
  198 |         ms.erase(ms.find(in[T[x]], out[T[x]]));
      |                                             ^
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from diameter.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:775:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::find(const key_type&) [with _Key = long long int; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<long long int, long long int, std::_Identity<long long int>, std::less<long long int>, std::allocator<long long int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::key_type = long long int]'
  775 |       find(const key_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_multiset.h:775:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_multiset.h:779:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::const_iterator std::multiset<_Key, _Compare, _Alloc>::find(const key_type&) const [with _Key = long long int; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<long long int, long long int, std::_Identity<long long int>, std::less<long long int>, std::allocator<long long int> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::key_type = long long int]'
  779 |       find(const key_type& __x) const
      |       ^~~~
/usr/include/c++/10/bits/stl_multiset.h:779:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_multiset.h:785:2: note: candidate: 'template<class _Kt> decltype (std::multiset<_Key, _Compare, _Alloc>::iterator{((std::multiset<_Key, _Compare, _Alloc>*)this)->std::multiset<_Key, _Compare, _Alloc>::_M_t._M_find_tr(__x)}) std::multiset<_Key, _Compare, _Alloc>::find(const _Kt&) [with _Kt = _Kt; _Key = long long int; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>]'
  785 |  find(const _Kt& __x)
      |  ^~~~
/usr/include/c++/10/bits/stl_multiset.h:785:2: note:   template argument deduction/substitution failed:
diameter.cpp:198:45: note:   candidate expects 1 argument, 2 provided
  198 |         ms.erase(ms.find(in[T[x]], out[T[x]]));
      |                                             ^
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from diameter.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:791:2: note: candidate: 'template<class _Kt> decltype (std::multiset<_Key, _Compare, _Alloc>::const_iterator{((const std::multiset<_Key, _Compare, _Alloc>*)this)->std::multiset<_Key, _Compare, _Alloc>::_M_t._M_find_tr(__x)}) std::multiset<_Key, _Compare, _Alloc>::find(const _Kt&) const [with _Kt = _Kt; _Key = long long int; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>]'
  791 |  find(const _Kt& __x) const
      |  ^~~~
/usr/include/c++/10/bits/stl_multiset.h:791:2: note:   template argument deduction/substitution failed:
diameter.cpp:198:45: note:   candidate expects 1 argument, 2 provided
  198 |         ms.erase(ms.find(in[T[x]], out[T[x]]));
      |                                             ^