Submission #1191317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191317		kerem	Nestabilnost (COI23_nestabilnost)	C++20	0 / 100	123 ms	197068 KiB

code1

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 5000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

int n,a[N+5],f[N+5],d[N+5][N+5];
vector<int> g[N+5];

int dfs(int x,int ata){
	for(int i=a[x]+1;i<=n;i++)
		d[x][i]=f[i];
	for(auto c:g[x]){
		if(c==ata) continue;
		int t=dfs(c,x);
		if(a[x]+1==a[c]){
			for(int i=a[x]+2;i<=n;i++)
				d[x][i]+=min(t,d[c][i]-f[i]);
			d[x][a[x]+1]+=t;
		}
		else if(a[c]==0){
			for(int i=a[x]+2;i<=n;i++)
				d[x][i]+=t;
			d[x][a[x]+1]+=min(t,d[c][a[x]+1]-f[a[x]+1]);
		}
		else{
			for(int i=a[x]+1;i<=n;i++)
				d[x][i]+=t;
		}
	}
	int ans=inf;
	for(int i=a[x]+1;i<=n;i++)
		ans=min(ans,d[x][i]);
	return ans;
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++) cin >> f[i];
	for(int i=1;i<n;i++){
		int x,y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	cout << dfs(1,0) << endl;
	for(int i=1;i<=n;i++)
		cout << i sp ":" sp d[i][1] sp d[i][2] sp d[i][3] << endl;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 20
• Subtask 3: 0 / 7
• Subtask 4: 0 / 22
• Subtask 5: 0 / 39