제출 #58085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58085		wilwxk	Chase (CEOI17_chase)	C++11	50 / 100	4024 ms	172244 KiB

chase

#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>=800) break;
            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
*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 0 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 30