oj.uz

답안 #103751

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103751 2019-04-02T12:38:38 Z E869120 Chase (CEOI17_chase) C++14
0 / 100
 94 ms 7852 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

int N, V, p[1 << 17], c[1 << 17], ret1, ret2, maxn = 0;
vector<int>X[1 << 17];
bool used[1 << 17];

void dfs(int pos, int dep) {
	maxn = max(maxn, abs(ret1 - ret2));
	used[pos] = true;
	if (dep == V) return;

	for (int to : X[pos]) {
		if (used[to] == true) continue;
		for (int r : X[to]) { c[r]++; if (c[r] == 1) ret2 += p[r]; }
		ret1 += p[to];
		dfs(to, dep + 1);
		ret1 -= p[to];
		for (int r : X[to]) { c[r]--; if (c[r] == 0) ret2 -= p[r]; }
	}
}

int main() {
	scanf("%d%d", &N, &V);
	for (int i = 1; i <= N; i++) scanf("%d", &p[i]);
	for (int i = 1; i <= N - 1; i++) {
		int u, v; scanf("%d%d", &u, &v);
		X[u].push_back(v);
		X[v].push_back(u);
	}
	for (int i = 1; i <= N; i++) X[i].push_back(i);

	for (int i = 1; i <= N; i++) {
		if (N >= 2000 && i >= 2) break;
		for (int j = 1; j <= N; j++) used[j] = false;
		ret1 = p[i]; ret2 = 0;
		for (int j = 1; j <= N; j++) c[j] = 0;
		for (int j : X[i]) { c[j] = 1; ret2 += p[j]; }
		dfs(i, 1);
	}
	cout << maxn << endl;
	return 0;
}

Compilation message

chase.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
chase.cpp: In function 'int main()':
chase.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &V);
  ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:28:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; i++) scanf("%d", &p[i]);
                               ~~~~~^~~~~~~~~~~~~
chase.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 94 ms 7852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -