题目描述

同CCY

思路

哈希，set操作

CCY提供的check函数~（因为我懒）~

tuple<>Wiki

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, ki, u, v, x, y, li, pi, qi, t;
struct Node {
	long long cnt;
	int ct;
	bool operator<(const Node& b) const {
		if (cnt != b.cnt) {
			return cnt > b.cnt;
		}
		return ct < b.ct;
	}
};
map<pair<int,int>, long long> adj;
set<Node> st[N];
vector<tuple<int, int, long long> > eve[N];
vector<int> q;
int no_out, city_dui;
bool has_out[N], add_dui[N];
inline void check(int u,int l_id) {
	if(!has_out[u]&&!st[u].empty()) {
		has_out[u]=1;
		no_out--;
	}
	if(has_out[u]&&(st[u].empty())) {
		has_out[u]=0;
		no_out++;
	}
	if(st[l_id].begin()->ct==u&&st[u].begin()->ct!=l_id) {
		city_dui--;
		add_dui[u]=0;
		add_dui[l_id]=0;
	}
	if(st[st[u].begin()->ct].begin()->ct==u&&!add_dui[st[u].begin()->ct]) {
		city_dui++;
		add_dui[u]=1;
		add_dui[st[u].begin()->ct]=1;
	}
}
inline void update(int& a, int& b, long long& oldc, long long& newc) {
	int l_id = st[a].size() ? st[a].begin()->ct : 0;
	if (oldc != 0) {
		st[a].erase({oldc, b});
	}
	if (newc != 0) {
		adj[ {a,b}] = newc;
		st[a].insert({newc, b});
	} else {
		adj[ {a,b}]=0;
	}
	check(a, l_id);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m;
	no_out = n;
	for(t = 1; t <= m; t++) {
		cin >> ki;
		if(t==41) {
			t++;
			t--;
		}
		for(int i = 0; i < ki; i++) {
			cin >> u >> v >> x >> y;
			long long old_u = adj[ {u,v}];
			long long old_v = adj[ {v,u}];
			long long new_u = old_u + x;
			long long new_v = old_v + x;
			update(u, v, old_u, new_u);
			update(v, u, old_v, new_v);
			if(t + y <= m) {
				eve[t + y].push_back( tuple<int, int, long long>(  u, v, (long long)(-x) ) );
			}
		}
		for (auto& e : eve[t]) {
			int u = get<0>(e);
			int v = get<1>(e);
			long long del = get<2>(e);
			long long old_u = adj[ {u,v}];
			long long old_v = adj[ {v,u}];
			long long new_u = old_u + del;
			long long new_v = old_v + del;
			update(u, v, old_u, new_u);
			update(v, u, old_v, new_v);
		}
		cin >> li;
		q.resize(li);
		for(int i = 0; i < li; i++) {
			cin >> q[i];
			cout << (st[q[i]].empty() ? 0 : st[q[i]].begin()->ct) << '\n';
		}
		cin >> pi >> qi;
		if (pi == 1) {
			cout << no_out << '\n';
		}
		if (qi == 1) {
			cout << city_dui << '\n';
		}
	}
	return 0;
}