oj.uz

Submission #417976

# Submission time Handle Problem Language Result Execution time Memory
417976 2021-06-04T18:04:18 Z gs14004 Rooted MST (innopolis2021_final_E) C++17
10 / 100
 4000 ms 43320 KB 
// 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 11 ms 440 KB Output is correct
5 Correct 41 ms 556 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 33400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3152 ms 6704 KB Output is correct
2 Correct 3137 ms 9580 KB Output is correct
3 Correct 3036 ms 4268 KB Output is correct
4 Execution timed out 4057 ms 43320 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4057 ms 43000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4057 ms 43000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4058 ms 28496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 11 ms 440 KB Output is correct
5 Correct 41 ms 556 KB Output is correct
6 Execution timed out 4070 ms 21584 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 11 ms 440 KB Output is correct
5 Correct 41 ms 556 KB Output is correct
6 Execution timed out 4043 ms 33400 KB Time limit exceeded
7 Halted 0 ms 0 KB -