結果

問題 No.3025 Chocol∀te
コンテスト
ユーザー 👑 binap
提出日時 2025-02-14 22:23:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,282 bytes
コンパイル時間 4,526 ms
コンパイル使用メモリ 272,468 KB
実行使用メモリ 33,188 KB
最終ジャッジ日時 2025-02-14 22:24:47
合計ジャッジ時間 98,002 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 60 TLE * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef long double ld;
typedef pair<int, int> P;

template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}
template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}
template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;}
template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}
template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;}
template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}

template<typename T> void chmin(T& a, T b){a = min(a, b);}
template<typename T> void chmax(T& a, T b){a = max(a, b);}

// Square Division
// Divide into D setions
// l[0] = 0, r[i] = l[i + 1], r[D - 1] = N
// [l[i], r[i])

// divide [lq, rq)
// if [lq, rq) is in a single section
// [[lq, lq + 1, ..., rq - 1], [], []]
// else
// [[lq, lq + 1, ..., r[a - 1] - 1], [a, a + 1, ..., b - 1], [l[b], l[b] + 1, ..., rq - 1]]

struct SquareDivision{
	int n, D;
	vector<int> l, r;
	SquareDivision(int n, int D = -1) : n(n), D(D) {}
	bool initialized = false;
	void init(){
		assert(n > 0);
		initialized = true;
		if(D == -1) D = sqrt(n);
		assert(D >= 1 and D <= n);
		l.resize(D);
		r.resize(D);
		l[0] = 0;
		int width = n / D;
		assert(width > 0);
		rep(i, D - 1){
			r[i] = l[i] + width;
			l[i + 1] = r[i];
		}
		r[D - 1] = n;
	}
	tuple<vector<int>, vector<int>, vector<int>> divide(int lq, int rq){
		vector<int> minor_left;
		vector<int> major;
		vector<int> minor_right;
		
		int i = lower_bound(l.begin(), l.end(), lq) - l.begin();
		
		{
			int next;
			if(i == D) next = n;
			else next = l[i];
			if(rq <= next){
				for(int idx = lq; idx < rq; idx++) minor_left.push_back(idx);
				return make_tuple(minor_left, major, minor_right);
			}else{
				for(int idx = lq; idx < next; idx++) minor_left.push_back(idx);
			}
		}
		for(; i < D; i++){
			if(r[i] <= rq){
				major.push_back(i);
			}else{
				for(int idx = l[i]; idx < rq; idx++){
					minor_right.push_back(idx);
				}
				return make_tuple(minor_left, major, minor_right);
			}
		}
		return make_tuple(minor_left, major, minor_right);
		
	}
};

int main(){
	int n, m;
	cin >> n >> m;
	vector<set<int>> G(n);
	rep(i, m){
		int u, v;
		cin >> u >> v;
		u--; v--;
		G[u].insert(v);
		G[v].insert(u);
	}
	vector<long long> a(n);
	cin >> a;
	int q;
	cin >> q;
	vector<tuple<int, int, int>> Query;
	rep(i, q){
		int t, var1, var2;
		cin >> t;
		if(t == 1){
			cin >> var1 >> var2;
			var1--; var2--;
		}
		if(t == 2){
			cin >> var1 >> var2;
			var1--;
		}
		if(t == 3){
			cin >> var1;
			var1--;
		}
		Query.emplace_back(t, var1, var2);
	}
	
	int D = max(1, int(sqrt(n)));
	
	SquareDivision sq(q, D);
	sq.init();
	
	rep(i, D){
		map<int, long long> s;
		
		set<int> list;
		for(int j = sq.l[i]; j < sq.r[i]; j++){
			auto [t, var1, var2] = Query[j];
			if(t == 3) list.insert(var1);
		}
		
		for(int u : list){
			for(int v : G[u]){
				s[u] += a[v];
			}
		}
		
		for(int j = sq.l[i]; j < sq.r[i]; j++){
			auto [t, var1, var2] = Query[j];
			if(t == 1){
				if(G[var1].find(var2) == G[var1].end()){
					G[var1].insert(var2);
					G[var2].insert(var1);
					if(list.find(var1) != list.end()) s[var1] += a[var2];
					if(list.find(var2) != list.end()) s[var2] += a[var1];
				}else{
					G[var1].erase(var2);
					G[var2].erase(var1);
					if(list.find(var1) != list.end()) s[var1] -= a[var2];
					if(list.find(var2) != list.end()) s[var2] -= a[var1];
				}
			}
			if(t == 2){
				for(int v : list){
					if(G[v].find(var1) != G[v].end()) s[v] += var2 - a[var1];
				}
				a[var1] = var2;
			}
			if(t == 3){
				cout << s[var1] << "\n";
			}
		}
	}
	
	
	return 0;
}
0