Submission #1121034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121034		Mousa_Aboubaker	Nile (IOI24_nile)	C++17	67 / 100	2061 ms	18964 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
	vector<int> w = W, a = A, b = B, e = E;
	int n = w.size(), q = e.size();
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int l, int r)
			{
				return w[l] < w[r];
			});
	vector<long long> RES(q);
	for(int i = 0; i < q; i++)
	{
		vector<int> par(n), sz(n + 1, 1);
		iota(par.begin(), par.end(), 0);
		auto find = [&](auto self, int u) -> int
		{
			return par[u] = (par[u] == u ? u : self(self, par[u]));
		};
		auto unite = [&](int u, int v) -> bool
		{
			u = find(find, u);
			v = find(find, v);
			if(u == v)
				return false;
			if(sz[u] > sz[v])
				swap(u, v);
			sz[v] += sz[u];
			par[u] = v;
			return true;
		};
		int d = e[i];
		for(int j = 0; j + 1 < n; j++)
		{
			int k = ord[j];
			int l = ord[j + 1];
			if(w[l] - w[k] <= d)
			{
				unite(l, k);
			}
		}
		map<int, vector<int>> mp;
		for(int j = 0; j < n; j++)
		{
			int k = ord[j];
			k = find(find, k);
			mp[k].push_back(ord[j]);
		}
		long long res = 0;
		for(auto [f, s]: mp)
		{
			if((int)s.size() % 2 == 0)
			{
				for(int j = 0; j < (int)s.size(); j++)
					res += b[s[j]];
			}
			else
			{
				for(int j = 0; j < (int)s.size(); j++)
					res += b[s[j]];
				long long mn = LLONG_MAX;
				int idx = -1;
				for(int j = 0; j < (int)s.size(); j++)
				{
					if(!(j & 1))
					{
						mn = min(mn, (long long)a[s[j]] - b[s[j]]);	
					}
					else
					{
						if(w[s[j + 1]] - w[s[j - 1]] <= d)
						{
							mn = min(mn, (long long)a[s[j]] - b[s[j]]);
						}
					}
				}
				res += mn;
			}
		}

		RES[i] = res;
	}
	return RES;
}

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:66:9: warning: unused variable 'idx' [-Wunused-variable]
   66 |     int idx = -1;
      |         ^~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18