oj.uz

Submission #1114078

# Submission time Handle Problem Language Result Execution time Memory
1114078 2024-11-18T07:31:07 Z NotLinux Nestabilnost (COI23_nestabilnost) C++17
41 / 100
 263 ms 197452 KB 
// Author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int N = 5e3 + 7;
const int inf = 1e18 + 7;
int n , arr[N] , fk[N] , dp[N][N] , mini[N];
vector < int > tree[N];
void f(int node , int par){
	for(auto itr : tree[node]){
		if(itr == par)continue;
		f(itr , node);
	}
	int tmp[n+1] = {0};
	for(int i = 1;i<=n;i++){
		for(auto itr : tree[node]){
			if(itr == par)continue;
			int local_ans = mini[itr];// new component
			if((arr[node] + 1) % i == arr[itr] and dp[itr][i] != inf){// continuing same component
				local_ans = min(local_ans , dp[itr][i]);
				// cout << node << " -> " << itr << " with an " << i << endl;
			}
			tmp[i] += local_ans;
		}
	}
	mini[node] = inf;
	for(int i = 1;i<=n;i++){
		if(arr[node] < i){
			mini[node] = min(mini[node] , tmp[i] + fk[i]);
			dp[node][i] = tmp[i];
		}
		else{
			dp[node][i] = inf;
		}
		// cout << node+1 << " " << i << " : " << tmp[i] << " ( + " << fk[i] << ")" << endl;
	}
	// cout << "mini " << node+1 << " : " << mini[node] << endl;
}
void solve(){
	cin >> n;
	for(int i = 0;i<n;i++)cin >> arr[i];
	for(int i = 1;i<=n;i++)cin >> fk[i];
	for(int i = 1;i<n;i++){
		int a,b;
		cin >> a >> b;
		a-- , b--;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	f(0,0);
	cout << mini[0] << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 197360 KB Output is correct
2 Correct 242 ms 197448 KB Output is correct
3 Correct 248 ms 197408 KB Output is correct
4 Correct 240 ms 197364 KB Output is correct
5 Correct 216 ms 197452 KB Output is correct
6 Correct 212 ms 197372 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 1 ms 2640 KB Output is correct
6 Correct 1 ms 2640 KB Output is correct
7 Correct 1 ms 2640 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 197360 KB Output is correct
2 Correct 242 ms 197448 KB Output is correct
3 Correct 248 ms 197408 KB Output is correct
4 Correct 240 ms 197364 KB Output is correct
5 Correct 216 ms 197452 KB Output is correct
6 Correct 212 ms 197372 KB Output is correct
7 Correct 2 ms 2640 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 1 ms 2640 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 1 ms 2640 KB Output is correct
12 Correct 1 ms 2640 KB Output is correct
13 Correct 1 ms 2640 KB Output is correct
14 Correct 247 ms 196852 KB Output is correct
15 Correct 235 ms 196896 KB Output is correct
16 Correct 238 ms 196956 KB Output is correct
17 Correct 232 ms 196940 KB Output is correct
18 Correct 260 ms 196936 KB Output is correct
19 Correct 228 ms 196936 KB Output is correct
20 Correct 226 ms 192860 KB Output is correct
21 Correct 233 ms 196880 KB Output is correct
22 Correct 218 ms 196680 KB Output is correct
23 Correct 228 ms 196764 KB Output is correct
24 Correct 233 ms 196936 KB Output is correct
25 Correct 228 ms 193096 KB Output is correct
26 Correct 240 ms 196816 KB Output is correct
27 Correct 216 ms 196952 KB Output is correct

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 197360 KB Output is correct
2 Correct 242 ms 197448 KB Output is correct
3 Correct 248 ms 197408 KB Output is correct
4 Correct 240 ms 197364 KB Output is correct
5 Correct 216 ms 197452 KB Output is correct
6 Correct 212 ms 197372 KB Output is correct
7 Incorrect 2 ms 592 KB Output isn't correct
8 Halted 0 ms 0 KB -