結果
問題 | No.2311 [Cherry 5th Tune] Cherry Month |
ユーザー |
![]() |
提出日時 | 2023-05-19 22:25:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 388 ms / 4,600 ms |
コード長 | 4,952 bytes |
コンパイル時間 | 2,950 ms |
コンパイル使用メモリ | 214,712 KB |
最終ジャッジ日時 | 2025-02-13 02:18:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 51 |
ソースコード
#line 1 "template/template.hpp"#include<bits/stdc++.h>using namespace std;using int64 = long long;const int mod = 1e9 + 7;const int64 infll = (1LL << 62) - 1;const int inf = (1 << 30) - 1;struct IoSetup {IoSetup() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);cerr << fixed << setprecision(10);}} iosetup;template< typename T1, typename T2 >ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {os << p.first << " " << p.second;return os;}template< typename T1, typename T2 >istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second;return is;}template< typename T >ostream &operator<<(ostream &os, const vector< T > &v) {for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");}return os;}template< typename T >istream &operator>>(istream &is, vector< T > &v) {for(T &in : v) is >> in;return is;}template< typename T1, typename T2 >inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template< typename T1, typename T2 >inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }template< typename T = int64 >vector< T > make_v(size_t a) {return vector< T >(a);}template< typename T, typename... Ts >auto make_v(size_t a, Ts... ts) {return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));}template< typename T, typename V >typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {t = v;}template< typename T, typename V >typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {for(auto &e : t) fill_v(e, v);}template< typename F >struct FixPoint : F {explicit FixPoint(F &&f) : F(forward< F >(f)) {}template< typename... Args >decltype(auto) operator()(Args &&... args) const {return F::operator()(*this, forward< Args >(args)...);}};template< typename F >inline decltype(auto) MFP(F &&f) {return FixPoint< F >{forward< F >(f)};}#line 2 "structure/union-find/union-find.hpp"struct UnionFind {vector< int > data;UnionFind() = default;explicit UnionFind(size_t sz) : data(sz, -1) {}bool unite(int x, int y) {x = find(x), y = find(y);if(x == y) return false;if(data[x] > data[y]) swap(x, y);data[x] += data[y];data[y] = x;return true;}int find(int k) {if(data[k] < 0) return (k);return data[k] = find(data[k]);}int size(int k) {return -data[find(k)];}bool same(int x, int y) {return find(x) == find(y);}vector< vector< int > > groups() {int n = (int) data.size();vector< vector< int > > ret(n);for(int i = 0; i < n; i++) {ret[find(i)].emplace_back(i);}ret.erase(remove_if(begin(ret), end(ret), [&](const vector< int > &v) {return v.empty();}), end(ret));return ret;}};int main() {int N;cin >> N;vector< int64 > A(N);cin >> A;int T;cin >> T;vector< int > O(T), X(T), K(T);vector< int > deg(N);for (int i = 0; i < T; i++) {cin >> O[i] >> X[i] >> K[i];--X[i];if (O[i] == 1) {--K[i];deg[X[i]]++;deg[K[i]]++;}}int Q;cin >> Q;vector< vector< pair< int, int > > > qs(T + 1);for (int i = 0; i < Q; i++) {int s, t;cin >> s >> t;--t;qs[s].emplace_back(t, i);}vector< int64 > ans(Q);UnionFind uf(N);vector< vector< int > > vs(N);vector< int64 > sub(N);vector< vector< pair< int, int > > > g(N);vector< vector< pair< int, int64 > > > lazy(N);for (int i = 0; i < N; i++) {vs[i] = {i};lazy[i] = {{-1, 0ll}};}for(int i = 0; i <= T; i++) {for(auto& [k, id] : qs[i]) {int64 now = A[k];now -= sub[uf.find(k)];for(auto& [p, t] : g[k]) {for(auto& [y, x] : lazy[p]) {if(t <= y) {now -= x;}}}chmax(now, 0ll);ans[id] = now;}if(i < T) {if(O[i] == 1) {int x = uf.find(X[i]);int y = uf.find(K[i]);if(make_pair(deg[X[i]], X[i]) < make_pair(deg[K[i]], K[i])) {g[X[i]].emplace_back(K[i], i);} else {g[K[i]].emplace_back(X[i], i);}if(x == y) continue;uf.unite(x, y);int New = uf.find(x);int Old = x ^ y ^ New;for(auto& v: vs[Old]) {A[v] -= sub[Old];A[v] += sub[New];vs[New].emplace_back(v);}vs[Old].clear();} else if(O[i] == 2) {A[X[i]] -= K[i];} else if(O[i] == 3) {A[X[i]] -= K[i];for(auto& [p,_] : g[X[i]]) A[p] -= K[i];//auto sum = lazy[X[i]].empty() ? 0 : lazy[X[i]].back().second;lazy[X[i]].emplace_back(i, K[i]);} else {sub[uf.find(X[i])] += K[i];}}}for(auto& p : ans) cout << p << "\n";}