結果
| 問題 | No.3025 Chocol∀te |
| ユーザー |
 ぷら
|
| 提出日時 | 2025-02-14 22:20:36 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 586 ms / 2,000 ms |
| コード長 | 6,082 bytes |
| コンパイル時間 | 1,719 ms |
| コンパイル使用メモリ | 152,244 KB |
| 実行使用メモリ | 10,136 KB |
| 最終ジャッジ日時 | 2025-02-14 22:21:20 |
| 合計ジャッジ時間 | 33,216 ms |
|
ジャッジサーバーID （参考情報） |
judge7 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 77 |
ソースコード
#include <string.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <ctime>#include <deque>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <list>#include <map>#include <memory>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;template <typename T> using vc = vector<T>;template <typename T> using vvc = vector<vector<T>>;template <typename T> using vvvc = vector<vector<vector<T>>>;template<class T> using pq = priority_queue<T,vector<T>,greater<T>>;template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }int dx4[] = {1,0,-1,0};int dy4[] = {0,1,0,-1};#define overload5(a, b, c, d, e, name, ...) name#define overload4(a, b, c, d, name, ...) name#define REP0(n) for(ll jidlsjf = 0; jidlsjf < n; ++jidlsjf)#define REP1(i, n) for(ll i = 0; i < (n); ++i)#define REP2(i, a, b) for(ll i = (a); i < (b); ++i)#define REP3(i, a, b, c) for(ll i = (a); i < (b); i += (c))#define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)#define per0(n) for(int jidlsjf = 0; jidlsjf < (n); ++jidlsjf)#define per1(i, n) for(ll i = (n)-1; i >= 0; --i)#define per2(i, a, b) for(ll i = (a)-1; i >= b; --i)#define per3(i, a, b, c) for(ll i = (a)-1; i >= (b); i -= (c))#define per(...) overload4(__VA_ARGS__, per3, per2, per1, per0)(__VA_ARGS__)#define fi first#define se second#define pb push_back#define ppb pop_back#define ppf pop_front#define drop(s) cout << #s << endl, exit(0)#define si(c) (int)(c).size()#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))#define rng(v, l, r) v.begin() + (l), v.begin() + (r)#define all(c) c.begin(), c.end()#define rall(c) c.rbegin(), c.rend()#define SORT(v) sort(all(v))#define REV(v) reverse(all(v))#define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end())#define MIN(v) *min_element(all(v))#define MAX(v) *max_element(all(v))#define overload2(_1, _2, name, ...) name#define vec(type, name, ...) vector<type> name(__VA_ARGS__)#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))int cn1[200200];int cn2[200200];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin >> n >> m;vc<int>x(m),y(m);vc<pii>tmp;rep(i,m) {cin >> x[i] >> y[i];x[i]--;y[i]--;tmp.pb({x[i],y[i]});}int B = 300;vc<int>a(n);rep(i,n) {cin >> a[i];}int q;cin >> q;vc<array<int,3>>query(q);rep(i,q) {cin >> query[i][0];if(query[i][0] == 1) {cin >> query[i][1] >> query[i][2];query[i][1]--;query[i][2]--;tmp.pb({query[i][1],query[i][2]});}if(query[i][0] == 2) {cin >> query[i][1] >> query[i][2];query[i][1]--;}if(query[i][0] == 3) {cin >> query[i][1];query[i][1]--;}}UNIQUE(tmp);int L = si(tmp);vc<int>f(L);rep(i,m) {int it = lb(tmp,make_pair(x[i],y[i]));f[it] = 1;}vc<int>id(q);rep(i,q) {if(query[i][0] == 1) {id[i] = lb(tmp,make_pair(query[i][1],query[i][2]));}}rep(i,0,q,B) {int r = min((int)i+B,q);vc<ll>sum(n);rep(j,L) {if(f[j]) {sum[tmp[j].fi] += a[tmp[j].se];sum[tmp[j].se] += a[tmp[j].fi];}}vc<int>cmp1,cmp2;rep(j,i,r) {if(query[j][0] == 1) {cmp1.pb(id[j]);}if(query[j][0] == 2) {cmp2.pb(query[j][1]);cn2[query[j][1]] = a[query[j][1]];}}UNIQUE(cmp1);UNIQUE(cmp2);rep(j,i,r) {if(query[j][0] == 1) {cn1[id[j]] ^= 1;}if(query[j][0] == 2) {cn2[query[j][1]] = query[j][2];}if(query[j][0] == 3) {int now = query[j][1];ll ans = sum[now];for(int k:cmp1) {if(cn1[k] && (tmp[k].fi == now || tmp[k].se == now)) {int nxt = (tmp[k].fi^tmp[k].se)^now;if(f[k]) {ans -= a[nxt];}else {ans += a[nxt];}}}for(int k:cmp2) {pii now2 = minmax(k,now);int it = lb(tmp,now2);if(it == si(tmp) || tmp[it] != now2) {continue;}if((cn1[it]^f[it])) {int nxt = (tmp[it].fi^tmp[it].se)^now;ans -= a[nxt];ans += cn2[nxt];}}cout << ans << "\n";}}rep(j,i,r) {if(query[j][0] == 1) {f[id[j]] ^= 1;cn1[id[j]] = 0;}if(query[j][0] == 2) {a[query[j][1]] = query[j][2];}}}}