oj.uz

Submission #260885

# Submission time Handle Problem Language Result Execution time Memory
260885 2020-08-11T06:59:29 Z super_j6 Transport (COCI19_transport) C++14
130 / 130
 272 ms 18912 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
#define vi vector<ll>
#define all(x) x.begin(), x.end()

void mrg(vi &x, vi &y){
	vi v(x.size() + y.size());
	merge(all(x), all(y), v.begin());
	swap(x, v);
}

const int mxn = 100000;
int n;
ll a[mxn], s[mxn], s1[mxn], s2[mxn], sz[mxn], vis[mxn];
vi v1, v2, r1, r2;
vector<pi> g[mxn];

int dfsc(int c, int p){
	sz[c] = 1;
	for(pi i : g[c]) if(i.f != p && !vis[i.f]) sz[c] += dfsc(i.f, c);
	return sz[c];
}

int dfsc2(int c, int p){
	for(pi i : g[c]){
		if(i.f == p || vis[i.f] || 2 * sz[i.f] <= sz[c]) continue;
		sz[i.f] = sz[c];
		return dfsc2(i.f, c);
	}
	return c;
}

void dfs(int c, int p){
	s1[c] = min(s1[c], s[c]), s2[c] = max(s2[c], s[c] += a[c]);
	r1.push_back(s1[c]);
	if(s[c] >= s2[c]) r2.push_back(s[c]);
	for(pi i : g[c]){
		if(i.f == p || vis[i.f]) continue;
		s[i.f] = s[c] - i.s, s1[i.f] = s1[c], s2[i.f] = s2[c];
		dfs(i.f, c);
	}
}

ll f(vi &x, vi &y){
	ll nx = x.size(), ny = y.size(), ret = nx * (ny - 1);
	for(int i = 0, j = ny - 1; i < nx; i++){
		while(~j && x[i] + y[j] >= 0) j--;
		ret -= j;
	}
	return ret;
}

ll sol(int c){
	dfsc(c, -1);
	vis[c = dfsc2(c, -1)] = 1;
	
	s[c] = s1[c] = s2[c] = 0;
	v1.assign(1, s1[c]), v2.assign(1, a[c]);
	ll ret = -f(v1, v2);
	for(pi i : g[c]){
		if(vis[i.f]) continue;
		s[i.f] = s[c] - i.s, s1[i.f] = s1[c], s2[i.f] = s2[c];
		r1.clear(), r2.clear();
		dfs(i.f, c);
		
		sort(all(r1)), sort(all(r2));
		for(ll &j : r2) j += a[c];
		ret -= f(r1, r2);
		mrg(v1, r1), mrg(v2, r2);
	}
	ret += f(v1, v2);
	
	for(pi i : g[c]) if(!vis[i.f]) ret += sol(i.f);
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n - 1; i++){
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	
	cout << sol(0) << endl;

	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3072 KB Output is correct
2 Correct 9 ms 3328 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3328 KB Output is correct
2 Correct 9 ms 3584 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 9856 KB Output is correct
2 Correct 65 ms 9088 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 12532 KB Output is correct
2 Correct 114 ms 13500 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 16128 KB Output is correct
2 Correct 175 ms 18912 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 6184 KB Output is correct
2 Correct 45 ms 5740 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 8988 KB Output is correct
2 Correct 109 ms 7944 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 10708 KB Output is correct
2 Correct 190 ms 10636 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 12516 KB Output is correct
2 Correct 247 ms 12464 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 15528 KB Output is correct
2 Correct 243 ms 13828 KB Output is correct