oj.uz

답안 #153059

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153059 2019-09-11T21:00:58 Z luciocf Transport (COCI19_transport) C++14
130 / 130
 540 ms 15932 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 1e5+10;

int n;
ll ans;

int a[maxn];

int bit[maxn], id[maxn];

int sz[maxn];

bool mark[maxn];

vector<pii> grafo[maxn]; 
vector<pair<ll, int>> tot;

void upd(int x, int v)
{
	for (; x <= n; x += (x&-x))
		bit[x] += v;
}

int soma(int x)
{
	int ans = 0;
	for (; x > 0; x -= (x&-x))
		ans += bit[x];
	return ans;
}

void dfs(int u, int p)
{
	sz[u] = 1;

	for (auto pp: grafo[u])
	{
		int v = pp.first, w = pp.second;
		if (v == p || mark[v]) continue;

		dfs(v, u);

		sz[u] += sz[v];
	}
}

int centroid(int u, int p, int S)
{
	for (auto pp: grafo[u])
	{
		int v = pp.first;
		if (v == p || mark[v]) continue;

		if (sz[v] > S/2) return centroid(v, u, S);
	}

	return u;
}

void dfs_up(int u, int p, ll cost, ll sum)
{
	if (cost >= 0)
	{
		ans++;
		tot.push_back({sum, u});
	}

	for (auto pp: grafo[u])
	{
		int v = pp.first, w = pp.second;
		if (v == p || mark[v]) continue;

		dfs_up(v, u, min(cost+1ll*a[v]-1ll*w, 1ll*a[v]-1ll*w), sum+1ll*a[v]-1ll*w);
	}
}

void dfs_add(int u, int p, ll cost, int add)
{
	if (cost >= 0)
		upd(id[u], add);

	for (auto pp: grafo[u])
	{
		int v = pp.first, w = pp.second;
		if (v == p || mark[v]) continue;

		dfs_add(v, u, min(cost+1ll*a[v]-1ll*w, 1ll*a[v]-1ll*w), add);
	}
}

void dfs_down(int u, int p, ll cost, ll sum)
{
	if (cost >= 0)
		ans++;

	if (lower_bound(tot.begin(), tot.end(), make_pair(-cost, 0)) != tot.end())
	{
		int pos = (int) (lower_bound(tot.begin(), tot.end(), make_pair(-cost, 0))-tot.begin())+1;
		ans += 1ll*(soma(n)-soma(pos-1));
	}

	for (auto pp: grafo[u])
	{
		int v = pp.first, w = pp.second;
		if (v == p || mark[v]) continue;

		dfs_down(v, u, min(cost, sum+1ll*a[u]-1ll*w), sum+1ll*a[u]-1ll*w);
	}
}

void decompose(int u)
{
	dfs(u, 0);

	int c = centroid(u, 0, sz[u]);
	mark[c] = 1;

	for (auto v: grafo[c])
		if (!mark[v.first])
			dfs_up(v.first, c, 1ll*(a[v.first]-v.second), 1ll*(a[v.first]-v.second));

	sort(tot.begin(), tot.end());

	for (int i = 0; i < tot.size(); i++)
		id[tot[i].second] = i+1;

	for (auto v: grafo[c])
		if (!mark[v.first])
			dfs_add(v.first, c, 1ll*(a[v.first]-v.second), 1);

	for (auto pp: grafo[c])
	{
		int v = pp.first, w = pp.second;
		if (mark[v]) continue;

		dfs_add(v, c, 1ll*(a[v]-w), -1);

		dfs_down(v, c, 1ll*(a[c]-w), 1ll*(a[c]-w));

		dfs_add(v, c, 1ll*(a[v]-w), 1);
	}

	for (auto v: grafo[c])
		if (!mark[v.first])
			dfs_add(v.first, c, 1ll*(a[v.first]-v.second), -1);

	tot.clear();

	for (auto v: grafo[c])
		if (!mark[v.first])
			decompose(v.first);
}

int main(void)
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	for (int i = 1; i < n; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);

		grafo[u].push_back({v, w});
		grafo[v].push_back({u, w});
	}

	decompose(1);

	printf("%lld\n", ans);
}

Compilation message

transport.cpp: In function 'void dfs(int, int)':
transport.cpp:44:21: warning: unused variable 'w' [-Wunused-variable]
   int v = pp.first, w = pp.second;
                     ^
transport.cpp: In function 'void decompose(int)':
transport.cpp:130:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < tot.size(); i++)
                  ~~^~~~~~~~~~~~
transport.cpp: In function 'int main()':
transport.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
transport.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
transport.cpp:170:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 2936 KB Output is correct
2 Correct 10 ms 3064 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3192 KB Output is correct
2 Correct 14 ms 3320 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 7920 KB Output is correct
2 Correct 96 ms 7952 KB Output is correct

Subtask #4
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 9460 KB Output is correct
2 Correct 168 ms 11676 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 283 ms 11924 KB Output is correct
2 Correct 260 ms 15932 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 4604 KB Output is correct
2 Correct 52 ms 4728 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 5748 KB Output is correct
2 Correct 182 ms 5904 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 6168 KB Output is correct
2 Correct 211 ms 7928 KB Output is correct

Subtask #9
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 389 ms 7028 KB Output is correct
2 Correct 325 ms 9076 KB Output is correct

Subtask #10
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 540 ms 8548 KB Output is correct
2 Correct 441 ms 10052 KB Output is correct