oj.uz

Submission #58083

# Submission time Handle Problem Language Result Execution time Memory
58083 2018-07-16T18:48:37 Z wilwxk Chase (CEOI17_chase) C++11
70 / 100
 3930 ms 172120 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
const int MAXK=102;
vector<int> g[MAXN];
int pai[MAXN], v[MAXN];
long long soma[MAXN], dp[MAXN][MAXK][2];
int n, x;

void predfs(int cur, int p) {
    soma[cur]=0; pai[cur]=p;
    for(auto viz : g[cur]) {
        if(viz==p) continue;
        predfs(viz, cur);
        soma[cur]+=v[viz];
    }
}
int readInt () {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}
long long fazdp(int cur, int k, int flag) {
    if(k<0||(k==0&&flag==0)) return 0;
    if(dp[cur][k][flag]!=-1) return dp[cur][k][flag];
    long long resp=0;

    if(flag) {
        resp=soma[cur];
        for(auto viz : g[cur]) {
            if(viz==pai[cur]) continue;
            resp=max(resp, fazdp(viz, k, 0)+soma[cur]);
            resp=max(resp, fazdp(viz, k-1, 1)+soma[cur]);
        }
    }
    else {
        for(auto viz : g[cur]) {
            if(viz==pai[cur]) continue;
            resp=max(resp, fazdp(viz, k, 0));
            resp=max(resp, fazdp(viz, k-1, 1));
        }
    }

    //printf("%d %d %d -> %lld\n", cur, k, flag, resp);
    return dp[cur][k][flag]=resp;
}

int main() {
    scanf("%d %d", &n, &x); srand(time(NULL));
    for(int i=1; i<=n; i++) v[i]=readInt();
    for(int i=0; i<n-1; i++) {
        int a, b; scanf("%d %d", &a, &b);
        g[a].push_back(b); g[b].push_back(a);
    }

    long long respf=0;
    for(int cur=1; cur<=1; cur++) {
            predfs(cur, cur);
            for(int i=1; i<=n; i++) for(int j=0; j<=x; j++) for(int k=0; k<2; k++) dp[i][j][k]=-1;
            for(int i=0; i<=x; i++) respf=max(respf, fazdp(cur, i, 0));
            for(int i=1; i<=x; i++) respf=max(respf, fazdp(cur, i-1, 1));
    }
    if(n<=1005) {
        for(int cur=2; cur<=n; cur++) {
            predfs(cur, cur); if(cur>=750) cur+=(rand()%3);
            for(int i=1; i<=n; i++) for(int j=0; j<=x; j++) for(int k=0; k<2; k++) dp[i][j][k]=-1;
            for(int i=0; i<=x; i++) respf=max(respf, fazdp(cur, i, 0));
            for(int i=1; i<=x; i++) respf=max(respf, fazdp(cur, i-1, 1));
        }
    }


    printf("%lld\n", respf);

}
/*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
*/

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &x); srand(time(NULL));
     ~~~~~^~~~~~~~~~~~~~~~~
chase.cpp:69:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2700 KB Output is correct
2 Correct 5 ms 2804 KB Output is correct
3 Correct 4 ms 2868 KB Output is correct
4 Correct 4 ms 2868 KB Output is correct
5 Correct 4 ms 2868 KB Output is correct
6 Correct 4 ms 2868 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2700 KB Output is correct
2 Correct 5 ms 2804 KB Output is correct
3 Correct 4 ms 2868 KB Output is correct
4 Correct 4 ms 2868 KB Output is correct
5 Correct 4 ms 2868 KB Output is correct
6 Correct 4 ms 2868 KB Output is correct
7 Correct 3930 ms 4592 KB Output is correct
8 Correct 176 ms 4648 KB Output is correct
9 Correct 127 ms 4648 KB Output is correct
10 Correct 3834 ms 4648 KB Output is correct
11 Correct 1012 ms 4664 KB Output is correct
12 Correct 444 ms 4664 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2981 ms 172080 KB Output is correct
2 Correct 3011 ms 172120 KB Output is correct
3 Correct 1954 ms 172120 KB Output is correct
4 Correct 280 ms 172120 KB Output is correct
5 Correct 3265 ms 172120 KB Output is correct
6 Correct 3400 ms 172120 KB Output is correct
7 Correct 3194 ms 172120 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2700 KB Output is correct
2 Correct 5 ms 2804 KB Output is correct
3 Correct 4 ms 2868 KB Output is correct
4 Correct 4 ms 2868 KB Output is correct
5 Correct 4 ms 2868 KB Output is correct
6 Correct 4 ms 2868 KB Output is correct
7 Correct 3930 ms 4592 KB Output is correct
8 Correct 176 ms 4648 KB Output is correct
9 Correct 127 ms 4648 KB Output is correct
10 Correct 3834 ms 4648 KB Output is correct
11 Correct 1012 ms 4664 KB Output is correct
12 Correct 444 ms 4664 KB Output is correct
13 Correct 2981 ms 172080 KB Output is correct
14 Correct 3011 ms 172120 KB Output is correct
15 Correct 1954 ms 172120 KB Output is correct
16 Correct 280 ms 172120 KB Output is correct
17 Correct 3265 ms 172120 KB Output is correct
18 Correct 3400 ms 172120 KB Output is correct
19 Correct 3194 ms 172120 KB Output is correct
20 Incorrect 3276 ms 172120 KB Output isn't correct
21 Halted 0 ms 0 KB -