Submission #1294031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294031		heyder_7	Paprike (COI18_paprike)	C++20	0 / 100	1095 ms	1114112 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
//#define int unsigned long long
//#define vector deque
#define int long long
#define tt true
#define ff false
#define F first
#define S second
#define endl '\n'
#define ins insert
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define srt(p) sort(p.begin() , p.end())
#define rvr(p) reverse(p.begin() , p.end())

const int MAX = 3e5, MOD = 1e9 + 7;
int G[MAX + 1];
vector<int> vts1;
vector<bool> vts(MAX);

/*

int pw(int a, int b) {
	int ans = 1;
	while(b > 0) {
		if(b % 2 == 1) {
			ans *= a;
		}
		a *= a;
		b /= 2;
	}
	return ans;
}

/*

int factorial(int n) {
	if(n == 0 || n == 1) return 1;
	return n * factorial(n - 1);
}

bool is_prime(int n) {
	if(n == 1 or n == 0) return false;
	if(n == 2) return true;
	if(n % 2 == 0) return false;
	for(int i = 3; i <= sqrt(n); i+=2) {
		if(n % i == 0) return false;
	}
	return true;
}

void sieve() {
	vts[0] = tt;
	vts[1] = tt;
	for(int i = 2; i <= sqrt(MAX); i++) {
		if(vts[i] == ff) {
			for(int j = i * i; j <= MAX; j += i) {
				vts[j] = tt;
			}
		}
	}
	for(int i = 0; i < MAX; i++) {
		if(!vts[i]) {
			vts1.push_back(i);
		}
	}
}

vector<int> sieve_massiv() {
	int n = MAX;
	vector<int> ans;
	vector<bool> ans2(MAX, true);
	ans2[0] = false;
	ans2[1] = false;
	for(int i = 2; i <= n; i++) {
		if(ans2[i]) {
			ans.push_back(i);
			for(int j = i * i; j <= n; j += i) {
				ans2[j] = false;
			}
		}
	}
	return ans;
}

vector<int> divisors(int n) {
	vector<int> divi;
	for(int i = 1; i <= sqrt(n); i++) {
		if(n % i == 0) {
			divi.push_back(i);
			if(i != n / i) divi.push_back(n / i);
		}
	}
	sort(divi.begin(), divi.end());
	return divi;
}


int phi(int n) {
	int ans = n;
	for(int i = 2; i * i <= n; i++) {
		if(n % i == 0) {
			while(n % i == 0) {
				n /= i;
			}
			ans -= ans / i;
		}
	}
	if(n > 1) {
		ans -= ans / n;
	}
	return ans;
}


string binaryaplsub(string a, string b) {
	int n = a.size(), m = b.size();
	int maxi = max(n, m);
	string ans = "";
	int yadda = 0;
	while(a.size() < maxi) {
		a = "0" + a;
	}
	while(b.size() < maxi) {
		b = "0" + b;
	}
	for(int i = maxi - 1; i >= 0; i--) {
		int A = a[i] - '0';
		int B = b[i] - '0';
		int sum = A + B + yadda;
		if(sum == 0) {
			ans = "0" + ans;
			yadda = 0;
		}
		else if(sum == 1) {
			ans = "1" + ans;
			yadda = 0;
		}
		else if(sum == 2) {
			ans = "0" + ans;
			yadda = 1;
		}
		else if(sum == 3) {
			ans = "1" + ans;
			yadda = 1;
		}
	}
	if(yadda != 0) ans = "1" + ans;
	return ans;
}

int pfc(int n) {
	int cnt = 0;
	for(int i = 2; i <= sqrt(n); i++) {
		if((int64_t)i * i > n) break;
		if(n % i == 0) {
			while(n % i == 0) {
				n /= i;
				cnt++;
			}
		}
	}
	if(n > 1) cnt++;
	return cnt;
}

int primecntInterval(int a, int b) {
	int n = b - a + 1;
	int n1 = sqrt(b) + 1;
	vector<bool> isPrime(n, true);
	if(a == 0) {
		isPrime[0] = false;
		if(n > 1) isPrime[1] = false;
	}
	else if(a == 1) {
		isPrime[0] = false;
	}
	vector<bool> vtt(n1 + 1, false);
	vector<int> vt;
	for(int i = 2; i <= n1; i++) {
		if(!vtt[i]) {
			vt.push_back(i);
			for(int j = i * i; j <= n1; j += i) {
				vtt[j] = true;
			}
		}
	}
	for(int i = 0; i < vt.size(); i++) {
		int start = max(vt[i] * vt[i], ((a + vt[i] - 1) / vt[i]) * vt[i]);
		for(int j = start; j <= b; j += vt[i]) {
			isPrime[j - a] = false;
		}
	}
	int smd = 0;
	for(int i = 0; i < n; i++) {
		if(isPrime[i]) {
			smd++;
		}
	}
	return smd;
}

void pppp() {
	vector<int> phi_arr(MAX + 1);
	for(int i = 0; i <= MAX; i++) phi_arr[i] = i;
	for(int i = 2; i <= MAX; i++) {
		if(phi_arr[i] == i) {
			for(int j = i; j <= MAX; j += i) {
				phi_arr[j] -= phi_arr[j] / i;
			}
		}
	}
	for(int i = 1; i <= MAX; i++) {
		for(int j = i; j <= MAX; j += i) {
			G[j] += i * phi_arr[j / i];
		}
	}
	for(int i = 1; i <= MAX; i++) {
		G[i] += G[i - 1] - i;
	}
}

string bitwise(int n) {
	string s = "";
	while(n > 0) {
		int qaliq = n % 2;
		if(qaliq == 1) s += '1';
		else s += '0';
		n /= 2;
	}
	reverse(s.begin(), s.end());
	return s;
}

bool is_palindrome(string s) {
    string t = s;
    reverse(t.begin(), t.end());
    return t == s;
}

//vector<int> vts1 = sieve_massiv();



/* ------------FOR DP----------
int n;
vector<int> vt;
int dp[MAX];

int dpp(int i){
    if(dp[i] != 0) return dp[i];
    int best = 1;
    for(int j = 0; j < i; ++j){
        if(vt[j] <= vt[i]){
            best = max(best , dpp(j) + 1);
        }
    }
    return dp[i] = best;
}
*/

bool ok1(vector<int> wreath , int k) {
    for(int i = 0; i < wreath.size(); ++ i) {
        if(wreath[i] > k) {
            return false;
        }
    }
    return true;
}

bool ok2(vector<pair<int , int>> edges , int x , int y) {
    for(int i = 0; i < edges.size(); ++ i) {
        if((edges[i].F == x && edges[i].S == y) || (edges[i].F == y && edges[i].S == x)) {
            return true;
        }
    }
    return false;
}

void solve() {
    int n , k , SAY = 0;
    cin >> n >> k;
    vector<int> vt(n);
    int cem = 0;
    for(int i = 0; i < n; ++ i) {
        cin >> vt[i];
        cem += vt[i];
    }
    vector<pair<int , int>> edges(n - 1);
    for(int i = 0; i < n - 1; ++ i) {
        int x , y;
        cin >> x >> y;
        edges[i].F = x;
        edges[i].S = y;
    }
    vector<int> wreath;
    wreath.pb(cem);
    while(!ok1(wreath , k)) {
        int mini = INT_MAX;
        int a;
        for(int i = 0; i < n; ++ i) {
            int x = edges[i].F;
            int y = edges[i].S;
            int sum = 0 , sum1 = 0;
            int say = 0 , say1 = 0;
            vector<int> vt1 , vt2;
            //////////////////////
            int A = -1;
            bool ok = false;
            for(int j = 0; j < n; ++ j) {
                if(i == j) {
                    continue;
                }
                if(ok2(edges , x , j + 1)) {
                    say++;
                    sum += vt[j];
                    if(A == -1) A = j + 1;
                }
            }
            for(int j = 0; j < n; ++ j) {
                if(i == j) {
                    continue;
                }
                if(ok2(edges , y , j + 1)) {
                    say1++;
                    sum1 += vt[j];
                    if(j + 1 == A) {
                        ok = true;
                        break;
                    }
                }
            }
            //////////////////////
            if(mini > abs(sum - sum1)) {
                mini = abs(sum - sum1);
                a = i;
            }
        }
        edges.erase(edges.begin() + a);
        SAY++;
        wreath.clear();
        vector<bool> vis(n + 1 , false);
        for(int i = 1; i <= n; ++ i) {
            if(vis[i] == true) {
                continue;
            }
            vis[i] = true;
            int sum = vt[i - 1];
            int cem = vt[i - 1];
            queue<int> q;
            q.push(i);
            while(!q.empty()) {
                int u = q.front();
                q.pop();
                for(int i = 0; i < edges.size(); ++ i) {
                    int x = edges[i].F , y = edges[i].S;
                    int Z = -1;
                    if(x == u && vis[y] != false) Z = y;
                    if(y == u && vis[x] != false) Z = x;
                    if(x != -1) {
                        vis[Z] = true;
                        sum += vt[Z - 1];
                        q.push(Z);
                    }
                }
                wreath.pb(sum);
            }
        }
    }
    cout << SAY << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//sieve();
	//pppp();
	int t = 1;
	//cin >> t;
	//int n;
	for(int i = 0; i < t; ++i) {
		solve();
	}
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49