Submission #37053

#	Time	Username	Problem	Language	Result	Execution time	Memory
37053		DoanPhuDuc	Chase (CEOI17_chase)	C++98	0 / 100	0 ms	2016 KiB

chase

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 20;

int n, m;
int a[N], b[N], p[N], h[N];

vector <int> adj[N];

void DFS(int u) {
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k]; if (v == p[u]) continue;
        p[v] = u; h[v] = h[u] + 1;
        DFS(v);
    }
}

int Compute(int s, int t) {
    FOR(i, 1, n) b[i] = a[i];
    int s1 = 0, s2 = 0;
    while (t != s) {
        s2 += b[t];
        REP(k, 0, adj[t].size()) {
            int v = adj[t][k];
            b[t] += b[v];
            b[v] = 0;
        }
        t = p[t];
    }
    s2 += b[s];
    REP(k, 0, adj[s].size()) {
        int v = adj[t][k];
        b[s] += b[v];
        b[v] = 0;
    }
    return b[s] - s2;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("ans.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d", &n, &m);
    FOR(i, 1, n) scanf("%d", &a[i]);
    FOR(i, 1, n - 1) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int ans = 0;
    FOR(u, 1, n) {
        h[u] = 0;
        p[u] = 0;
        DFS(u);
        FOR(v, 1, n) if (h[v] - h[u] + 1 <= m) {
            ans = max(ans, Compute(u, v));
        }
    }
    printf("%d", ans);

    return 0;
}

Compilation message (stderr)

chase.cpp: In function 'void DFS(int)':
chase.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
chase.cpp:23:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
chase.cpp: In function 'int Compute(int, int)':
chase.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
chase.cpp:35:9: note: in expansion of macro 'REP'
         REP(k, 0, adj[t].size()) {
         ^
chase.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
chase.cpp:43:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[s].size()) {
     ^
chase.cpp:32:9: warning: unused variable 's1' [-Wunused-variable]
     int s1 = 0, s2 = 0;
         ^
chase.cpp: In function 'int main()':
chase.cpp:56:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
chase.cpp:57:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &a[i]);
                                    ^
chase.cpp:59:40: 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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30