oj.uz

답안 #169969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
169969 2019-12-23T13:01:49 Z Ruxandra985 Chase (CEOI17_chase) C++14
20 / 100
 823 ms 524292 KB 
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
vector <int> v[DIMN];
int val[DIMN] , frm , fth[DIMN];
long long dp[2][DIMN][110] , dp2[2][DIMN][110],part[2][DIMN][110] , part2[2][DIMN][110];
long long sol;
void dfs (int nod , int tt){
    int i , vecin , j;
    long long sum;
    sum = 0;
    fth[nod] = tt;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i];
        if (vecin != tt){
            sum += val[vecin];
        }
    }
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i];
        if (vecin != tt){

            dfs (vecin , nod);

            //if (nod == 7)
              //  printf ("a");

            for ( j = 0 ; j <= frm ; j++){

                /// caz 1 : ai venit de jos in nod, te duci in jos spre vecin

                sol = max(sol , dp[0][nod][j] + part2[0][vecin][frm - j]);
                if (frm - j)
                    sol = max(sol , dp[0][nod][j] + part2[1][vecin][frm - j]);

                if (j){
                    sol = max(sol , dp[1][nod][j] + part2[0][vecin][frm - j] + val[tt]);
                    sol = max(sol , dp[1][nod][j] + part2[1][vecin][frm - j] + val[tt]);
                }
                /// caz 2 : ai venit din jos spre vecin , te duci in nod apoi in jos

                sol = max(sol , dp2[0][nod][j] + part[0][vecin][frm - j]);
                if (frm - j)
                    sol = max(sol , dp2[0][nod][j] + part[1][vecin][frm - j] + val[nod]);

                if (j){
                    sol = max(sol , dp2[1][nod][j] + part2[0][vecin][frm - j] + val[tt] - val[vecin]);
                    if (frm - j)
                        sol = max(sol , dp2[1][nod][j] + part2[1][vecin][frm - j] + val[tt] + val[nod] - val[vecin]);
                }
            }

            //printf ("%d %lld\n",nod,sol);


            /// adaugi vecin la setul de vecini cu care ai uni alti vecini
            /// (ce coerenta fusei)



            /// presupunem ca din vecin vrei sa te duci in nod
            dp[1][nod][1] = max ( dp[1][nod][1] , sum );
            for (j = 0 ; j <= frm ; j++){ /// vrei ca pana in nod sa fi consumat j

                dp[0][nod][j] = max( dp[0][nod][j] , dp[0][vecin][j]);
                /// nu ai aplicat nici in nod nici in vecin , ok
                if (j)
                    dp[0][nod][j] = max( dp[0][nod][j] , dp[1][vecin][j] + val[nod]);
                /// daca ai aplicat inainte in vecin, jerry nu mai vede in nod

                if (j){ /// aplici in nod
                    /// daca nu am aplicat in vecin inainte
                    dp[1][nod][j] = max(dp[1][nod][j] , dp[0][vecin][j-1] + sum - val[vecin]);

                    /// daca am aplicat in vecin inainte
                    /// jerry nu o sa mai vada valoarea din nod, dra tom oricum o vede
                    if (j-1)
                        dp[1][nod][j] = max (dp[1][nod][j] , dp[1][vecin][j-1] + sum - val[vecin] + val[nod]);
                }
                sol = max(sol , dp[0][nod][j]);
                if (j)
                    sol = max(sol , dp[1][nod][j] + val[tt]);
                part[1][nod][j] = max(part[1][nod][j-1] , dp[1][nod][j]);
                part[0][nod][j] = max(part[0][nod][j-1] , dp[0][nod][j]);
            }


            /// acum calculez dp2 , incep din i, ma duc in jos , consum j
            dp2[1][nod][1] = max(dp2[1][nod][1] , sum);
            for (j = 0 ; j <= frm ; j++){ /// vrei ca pana in nod sa fi consumat j

                dp2[0][nod][j] = max( dp2[0][nod][j] , dp2[0][vecin][j]);
                /// nu ai aplicat nici in nod nici in vecin , ok
                if (j)
                    dp2[0][nod][j] = max( dp2[0][nod][j] , dp2[1][vecin][j]);
                /// daca ai aplicat inainte in vecin, jerry nu mai vede in nod

                if (j){ /// aplici in nod
                    /// daca nu am aplicat in vecin inainte
                    dp2[1][nod][j] = max(dp2[1][nod][j] , dp2[0][vecin][j-1] + sum);

                    /// daca am aplicat in vecin inainte
                    /// jerry nu o sa mai vada valoarea din nod, dra tom oricum o vede
                    if (j-1)
                        dp2[1][nod][j] = max (dp2[1][nod][j] , dp2[1][vecin][j-1] + sum);
                }
                sol = max(sol , dp2[0][nod][j]);
                if (j)
                    sol = max(sol , dp2[1][nod][j] + val[tt]);
                part2[1][nod][j] = max(part2[1][nod][j-1] , dp2[1][nod][j]);
                part2[0][nod][j] = max(part2[0][nod][j-1] , dp2[0][nod][j]);
            }

            //printf ("%d %lld\n",nod,sol);

        }
    }


}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i , x , y;
    fscanf (fin,"%d%d",&n,&frm);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d",&val[i]);
    for (i=1;i<n;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs (1 , 0);

    fprintf (fout,"%lld" , sol);
    return 0;
}

Compilation message

chase.cpp: In function 'void dfs(int, int)':
chase.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
chase.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:126:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&frm);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:128:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&val[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
chase.cpp:130:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 12 ms 6392 KB Output is correct
8 Correct 11 ms 6392 KB Output is correct
9 Correct 8 ms 2808 KB Output is correct
10 Incorrect 16 ms 8572 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 765 ms 360324 KB Output is correct
2 Correct 823 ms 360248 KB Output is correct
3 Correct 464 ms 8536 KB Output is correct
4 Runtime error 777 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 12 ms 6392 KB Output is correct
8 Correct 11 ms 6392 KB Output is correct
9 Correct 8 ms 2808 KB Output is correct
10 Incorrect 16 ms 8572 KB Output isn't correct
11 Halted 0 ms 0 KB -