Submission #1185263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185263		vito	Nestabilnost (COI23_nestabilnost)	C++17	7 / 100	165 ms	440 KiB

code1

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define F first
#define S second
#define sz(x) int(x.size())
const ll INF=1e18+5;
const int MAX=25;
vector<int> gr[MAX];
int bio[MAX];
int par[MAX];
int up[MAX][MAX];
int n;
vector<int> t;
void dfs(int v, int p) {
	for(auto &u : gr[v]) {
		if(u!=p) {
			par[u]=v;
			dfs(u, v);
		}
	}
}
void siri(int v, int p) {
	for(auto &u : gr[v]) {
		if(u!=p && up[v][u]==0 && bio[u]==0) {
			t.push_back(u);
			bio[u]=1;
			// cout << v << " -> " << u << '\n';
			siri(u, v);
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	if(n>20) {
		cout << "skibidi\n";
		return 0;
	}
	vector<int> a(n+1);
	for(int i=1; i<=n; i++) {
		cin >> a[i];
	}
	vector<ll> f(n+1);
	for(int k=1; k<=n; k++) {
		cin >> f[k];
	}
	vector<ll> suff(n+1);
	suff[n]=f[n];
	for(int i=n-1; i>=1; i--) {
		suff[i]=min(suff[i+1], f[i]);
	}
	vector<pair<int, int>> ed(n-1);
	for(int i=0; i<n-1; i++) {
		cin >> ed[i].F >> ed[i].S;
		gr[ed[i].F].push_back(ed[i].S);
		gr[ed[i].S].push_back(ed[i].F);
	}
	dfs(1, 1);
	ll out=INF;
	for(int mask=0; mask<(1<<(n-1)); mask++) {
		for(int i=0; i<n-1; i++) {
			if(mask&(1<<i)) {
				up[ed[i].F][ed[i].S]=1;
				up[ed[i].S][ed[i].F]=1;
			}
		}
		for(int i=1; i<=n; i++) {
			bio[i]=0;
		}
		int ok=1;
		ll cost=0;
		for(int i=1; ok && i<=n; i++) {
			if(bio[i]==0) {
				bio[i]=1;
				t={i};
				siri(i, i);
				// cout << "t: ";
				// for(auto &j : t) {
				// 	cout << j << ' ' << par[j] << '\n';
				// }
				// cout << '\n';
				int mx=0;
				int mora=n+5;
				for(auto &j : t) {
					mx=max(mx, a[j]);
					if(j==1) {
						continue;
					}
					if(up[par[j]][j]==0) {
						int pro=a[par[j]];
						int sad=a[j];
						if(sad<=pro && sad!=0) {
							// cout << "v = " << j << '\n';
							ok=0;
							break;
						}
						if(pro+1==sad) {
							if(sad>=mora) {
								ok=0;
								// cout << "v = " << j << '\n';
								break;
							}
						}
						else if(sad==0) {
							if(mora==n+5) {
								mora=pro+1;
								if(mora<=mx) {
									ok=0;
									// cout << "v = " << j << '\n';
									break;
								}
							}
							else {
								if(mora!=pro+1) {
									ok=0;
									// cout << "v = " << j << '\n';
									break;
								}
							}
						}
						else {
							ok=0;
							// cout << "v = " << j << '\n';
							break;
						}
					}
				}
				if(mora==n+5) {
					cost+=suff[mx+1];
				}
				else {
					cost+=f[mora];
				}
				// cout << "mora = " << mora << '\n';
				// cout << "ok = " << ok << '\n';
				// cout << "cost = " << cost << '\n';
				// break;
			}
		}
		if(ok) {
			out=min(out, cost);
			// if(cost==2) {
			// 	auto mm=mask;
			// 	while(mm) {
			// 		cout << mm%2;
			// 		mm/=2;
			// 	}
			// 	cout << '\n';
			// }
		}
		for(int i=0; i<n-1; i++) {
			if(mask&(1<<i)) {
				up[ed[i].F][ed[i].S]=0;
				up[ed[i].S][ed[i].F]=0;
			}
		}
	}
	cout << out << '\n';
	return 0;
}

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