Submission #417976

#	Time	Username	Problem	Language	Result	Execution time	Memory
417976		gs14004	Rooted MST (innopolis2021_final_E)	C++17	10 / 100	4070 ms	43320 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;

struct group{
	int s, e;
};

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 foo{
	int type, s, e; lint cost;
	bool operator<(const foo &f)const{
		return cost < f.cost;
	}
};

priority_queue<foo> pq;

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;
	}
	int Q; scanf("%d",&Q);
	while(Q--){
		int pos, val;
		scanf("%d %d",&pos,&val);
		int delta = val - a[pos];
		a[pos] += delta;
		vect[rev[pos]] += delta;
		if(rev[pos]) vect[rev[pos]-1] -= delta;
		vector<lint> dp(n + 1), curmax(n + 1);
		vector<lint> sum(n + 1);
		dp[0] = 0;
		for(int i = 1; i <= n; i++){
			dp[i] = min(dp[i-1], curmax[i - 1] + vect[2*i-2] + sum[i - 1]);
			sum[i] = sum[i-1] + vect[2*i-2] + vect[2*i-1];
			curmax[i] = min(curmax[i - 1], dp[i] - sum[i]);
		}
		printf("%lld\n", dp[n]  + kek);
	}
}

Compilation message (stderr)

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

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