预言

userId_undefined

复仇者_帅童

CSP-J一等奖出题人

2025-07-18 20:39:18

发布于：湖南

22阅读
0回复
0点赞

https://codeforces.com/contest/2126/submission/329515825

This submission will time limit exceeded on test 51.

code:

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <cmath>
#define int long long
using namespace std;
vector <pair <int, int>> v[200005];
vector <int> big;
int idx[200005];
map <int, int> cont[505];
vector <pair <int, int>> v2[200005];
int siz;
int a[200005];
void solve(){
	int n, m;
	cin >> n >> m;
	siz = sqrt(n);
	for(int i = 1; i <= n; i++) cin >> a[i];
	int ans = 0;
	
	for(int i = 1; i < n; i++){
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back({y, z});
		v[y].push_back({x, z});
		if(a[x] != a[y]) ans += z;
	}
	
	for(int i = 1; i <= n; i++){
		if(v[i].size() >= siz){
			big.push_back(i), idx[i] = big.size() - 1;
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(auto j:v[i]){
			if(v[j.first].size() >= siz){
				v2[i].push_back(j);
				cont[idx[j.first]][a[i]] -= j.second;
				cont[idx[j.first]][0] += j.second;
			}
		}
	}
	//cout << ans << '\n';
	
	while(m--){
		int x, y;
		cin >> x >> y;
		if(v[x].size() < siz){
			for(auto i:v[x]){
				if(a[i.first] != a[x]) ans -= i.second;
				if(a[i.first] != y) ans += i.second;
			}
		}else{
			ans -= (cont[idx[x]][0] + cont[idx[x]][a[x]]);
			ans += (cont[idx[x]][0] + cont[idx[x]][y]);
		}
		for(auto i:v2[x]){
			cont[idx[i.first]][a[x]] += i.second;
			cont[idx[i.first]][y] -= i.second;
		}
		a[x] = y;
		cout << ans << '\n';
	}
	
	for(int i = 1; i <= n; i++){
		v[i].clear();
		v2[i].clear();
		idx[i] = 0;
	}
	for(int i = 0; i < big.size(); i++){
		cont[i].clear();
	}
	big.clear();
} 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();
	
	return 0;
}

时间复杂度 O(∑nnlog⁡n)O(\sum n\sqrt n\log n)。
注意到当 n=2×105n=2\times10^5 时，nnlog⁡n≈1.5×109n\sqrt n\log n\approx 1.5\times 10^9。

userId_undefined
去预览
0/2000

全部评论 5

热门讨论