제출 #1190956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190956		kerem	Nestabilnost (COI23_nestabilnost)	C++20	32 / 100	92 ms	52052 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 300000
 
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],pre[N+5],ind[N+5];
vector<int> g[N+5];
pii End;

void dfs(int x,int ata,int k){
	ind[k]=x;
	int c=0;
	for(auto i:g[x]){
		if(i==ata) continue;
		c=i;
		dfs(i,x,k+1);
		if(a[x]==a[i]-1) d[x]=d[i];
		else d[x]=d[i]+pre[a[x]+1];
	}
	if(a[x]==a[c]-1) return;
	if(!c){
		d[x]=pre[a[x]+1];
		End.fr=0;
		End.sc=a[x]+1;
		return;
	}
	if(a[c] || End.sc>a[x]+1){
		End.fr=c;
		End.sc=a[x]+1;
		return;
	}
	if(End.sc==a[x]+1)
		d[x]=min(d[x],f[a[x]+1]+d[End.fr]);
	else if(End.sc<a[x]+1){
		d[x]=min(d[x],f[a[x]+1]+d[ind[k+End.sc+1]]);
		End.fr=ind[k+End.sc+1];
		End.sc=a[x]+1;
	}
}
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];
	pre[n]=f[n];
	for(int i=n-1;i>=1;i--)
		pre[i]=min(f[i],pre[i+1]);
	for(int i=1;i<n;i++){
		int x,y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs(1,0,1);
	cout << d[1];
}

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