Submission #418483

#	Time	Username	Problem	Language	Result	Execution time	Memory
418483		gs14004	Rooted MST (innopolis2021_final_E)	C++17	100 / 100	1000 ms	117708 KiB

Main

// shirley smokes weed
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 600005;

struct edg{
	int s, e, x;
	bool operator<(const edg &e)const{
		return x < e.x;
	}
};

struct disj{
	int pa[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[p] = q; return 1;
	}
}disj;

int n, m;
int l[MAXN], r[MAXN], a[MAXN];
vector<lint> vect;
int rev[MAXN];

void dfs(int v){
	if(v <= n){
		vect.push_back(a[v]);
		rev[v] = sz(vect) - 1;
		return;
	}
	dfs(l[v]);
	vect.push_back(-a[v]);
	dfs(r[v]);
}

struct node{
	lint a[2][2];
	void init_pos(lint x){
		a[0][0] = 0;
		a[0][1] = x;
		a[1][0] = 1e18;
		a[1][1] = x;
	}
	void init_neg(lint x){
		a[0][0] = a[1][0] = 0;
		a[0][1] = 1e18;
		a[1][1] = x;
	}
	void init(int pos, lint x){
		if(pos % 2) init_neg(x);
		else init_pos(x);
	}
	node operator+(const node &n)const{
		node x;
		memset(x.a, 0x3f, sizeof(x.a));
		for(int i=0; i<2; i++){
			for(int j=0; j<2; j++){
				for(int k=0; k<2; k++){
					x.a[i][k] = min(x.a[i][k], a[i][j] + n.a[j][k]);
				}
			}
		}
		return x;
	}
}tree[1 << 21];

void init(int s, int e, int p){
	if(s == e){
		tree[p].init(s, vect[s]);
		return;
	}
	int m = (s+e)/2;
	init(s, m, 2*p);
	init(m+1, e, 2*p+1);
	tree[p] = tree[2*p] + tree[2*p+1];
}

void upd(int pos, int s, int e, int p){
	if(s == e){
		tree[p].init(s, vect[s]);
		return;
	}
	int m = (s+e)/2;
	if(pos <= m) upd(pos, s, m, 2*p);
	else upd(pos, m+1, e, 2*p+1);
	tree[p] = tree[2*p] + tree[2*p+1];
}

void upd(int pos, lint val){
	vect[pos] += val;
	upd(pos, 0, sz(vect) - 1, 1);
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
	vector<edg> v;
	for(int i=0; i<m; i++){
		int s, e, x; scanf("%d %d %d",&s,&e,&x);
		if(s > e) swap(s, e);
		v.push_back({s, e, x});
	}
	for(int i = 2; i <= n; i++) v.push_back({1, i, int(2e9)});
	sort(all(v));
	disj.init(2*n);
	int q = n;
	lint kek = 0;
	for(auto &i : v){
		int L = disj.find(i.s);
		int R = disj.find(i.e);
		if(L == R) continue;
		q++;
		kek += i.x;
		l[q] = L; r[q] = R; a[q] = i.x;
		disj.uni(L, q);
		disj.uni(R, q);
	}
	dfs(q);
	vect.push_back(-1e18);
	kek -= vect.back();
	for(int i=0; i+1<sz(vect); i++){
		vect[i] += vect[i + 1];
		if(i % 2 == 1) vect[i] *= -1;
	}
	init(0, sz(vect) - 1, 1);
	int Q; scanf("%d",&Q);
	while(Q--){
		int pos, val;
		scanf("%d %d",&pos,&val);
		int delta = val - a[pos];
		a[pos] += delta;
		upd(rev[pos], delta);
		if(rev[pos]) upd(rev[pos] - 1, -delta);
		printf("%lld\n", tree[1].a[0][0]  + kek);
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
Main.cpp:109:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
      |                              ~~~~~^~~~~~~~~~~~
Main.cpp:112:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   int s, e, x; scanf("%d %d %d",&s,&e,&x);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:139:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |  int Q; scanf("%d",&Q);
      |         ~~~~~^~~~~~~~~
Main.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |   scanf("%d %d",&pos,&val);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 20 / 20
• Subtask 8: 20 / 20