Submission #1045315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045315		_rain_	Transport (COCI19_transport)	C++14	0 / 130	101 ms	20688 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
const int maxn = 2e5;
std::vector<pair<int,i64>> graph[maxn+2];
int a[maxn+2] , n;

	i64 BIT[maxn+2];
	void upd(int pos , int val)
	{
		for (; pos <= maxn;  pos += pos&-pos)
			BIT[pos] += val;
		return;
	}
	i64 get(int id)
	{
		i64 sum = 0;
		for (; id ; id -= id&-id)
			sum += BIT[id];
		return sum;
	}
	i64 sum_range(int l , int r)
	{
		return get(r) - get(l);
	}


	int sub[maxn+2] ;
	bool mark[maxn+2];
	std::vector<pair<i64,int>> cost;
	std::vector<i64> down;
	int id[maxn+2];
	i64 answer = 0;

	int get_centroid(int v , int p , int half)
	{
		for (auto& [to,w] : graph[v])
		{
			if (mark[to] || to == p) continue;
			if (sub[to] > half) return get_centroid(to,v,half);
		}
		return v;
	}

	void dfssize(int v , int p)
	{
		sub[v]=1;
		for (auto& [to,w] : graph[v])
		{
			if (to==p||mark[to]) continue;
			dfssize(to,v);
			sub[v]+=sub[to];
		}
		return;
	}

	void downforces(int v , int p , i64 mn , i64 used)
	{
			down.push_back(mn);
			for (auto& [to , w] : graph[v])
			{
				if (mark[to] || to == p) continue;
				downforces(to , v , min({mn , used + a[v] - w }) , used + a[v] - w);
			}
			return;
	}

	void build(int v , int p , i64 sum )
	{
		if (sum >= 0)
				cost.push_back({sum , v});
		for (auto& [to , w] : graph[v])
		{
			if (to==p || mark[to]) continue;
			if (a[to] - w >= 0)
				build(to , v , sum + a[to] - w);
		}
		return;
	}

	void centroid(int v)
	{
		dfssize(v,v);
		v = get_centroid(v,v,sub[v]/2);
		mark[v] = true;
		// cout << "BUCET IS : " << v << '\n';

		// DP 
			for (auto& [to,w] : graph[v])
			{
				if (mark[to]) continue;
				build(to , v , a[to] - w);
			}
			
			vector<i64> allcost ;
			std::sort(cost.begin() , cost.end());
			for (int i = 0; i < cost.size(); ++i)
			{
				id[cost[i].second] = i + 1;
				upd(id[cost[i].second] , 1);
				allcost.push_back(cost[i].first);
				++answer;
			}
			cost.clear();

			for (auto& [to , w] : graph[v])
			{
				
				if (mark[to]) continue;
				// cout << "VERTEX IS : " << to << '\n';
				build(to , v , a[to] - w);
				for (auto& [x,y] : cost) upd(id[y] , -1);
					downforces(to , v , a[v] - w , a[v] - w);
					for (auto& x : down)
					{
						if (x >= 0) ++answer;
						int pos = lower_bound(allcost.begin() , allcost.end() , -x) - allcost.begin() ;
						answer += sum_range(pos , allcost.size());
							// cout << x << ' ' << answer << ' ' << pos << '\n';
						// cout << x << ' ' << answer << '\n';
					}
					// cout << '\n';
					down.clear();
				for (auto& [x,y] : cost) upd(id[y] , 1);
				cost.clear();
			}

			for (int i = 0; i < allcost.size(); ++i) upd(i + 1 , -1);

		// cout << "\n VECTOR IS \n";
		// for (auto& x : allcost) cout << x << ' '; 
		// cout << '\n';
		// cout << "ANSWER IS : " << answer << '\n';
		
		for (auto& [to , w] : graph[v])
			if (!mark[to]) centroid(to);
	}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n ;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i < n; ++i)
	{
		int u , v , w; cin >> u >> v >> w;
		graph[u].push_back({v , w});
		graph[v].push_back({u , w});
	}
	centroid(1);
	cout << answer;
}

Compilation message (stderr)

transport.cpp: In function 'long long int get_centroid(long long int, long long int, long long int)':
transport.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |   for (auto& [to,w] : graph[v])
      |              ^
transport.cpp: In function 'void dfssize(long long int, long long int)':
transport.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |   for (auto& [to,w] : graph[v])
      |              ^
transport.cpp: In function 'void downforces(long long int, long long int, i64, i64)':
transport.cpp:61:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |    for (auto& [to , w] : graph[v])
      |               ^
transport.cpp: In function 'void build(long long int, long long int, i64)':
transport.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |   for (auto& [to , w] : graph[v])
      |              ^
transport.cpp: In function 'void centroid(long long int)':
transport.cpp:90:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   90 |    for (auto& [to,w] : graph[v])
      |               ^
transport.cpp:98:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |    for (int i = 0; i < cost.size(); ++i)
      |                    ~~^~~~~~~~~~~~~
transport.cpp:107:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |    for (auto& [to , w] : graph[v])
      |               ^
transport.cpp:113:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |     for (auto& [x,y] : cost) upd(id[y] , -1);
      |                ^
transport.cpp:125:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |     for (auto& [x,y] : cost) upd(id[y] , 1);
      |                ^
transport.cpp:129:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |    for (int i = 0; i < allcost.size(); ++i) upd(i + 1 , -1);
      |                    ~~^~~~~~~~~~~~~~~~
transport.cpp:136:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  136 |   for (auto& [to , w] : graph[v])
      |              ^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13