Submission #101590

#	Time	Username	Problem	Language	Result	Execution time	Memory
101590		cheeheng	Chase (CEOI17_chase)	C++14	20 / 100	1111 ms	525312 KiB

chase

#include <bits/stdc++.h>

using namespace std;

long long p[100005];
long long p2[100005];
vector<int> AdjList[100005];

int parent[100005];
int dist[13];

int main(){
    int N, v;
    scanf("%d%d", &N, &v);

    for(int i = 1; i <= N; i ++){
        scanf("%d", &p[i]);
        p2[i] = p[i];
    }

    for(int i = 1; i < N; i ++){
        int a, b;
        scanf("%d%d", &a, &b);
        AdjList[a].push_back(b);
        AdjList[b].push_back(a);
    }

    long long ans = 0;
    for(int i = 1; i <= N; i ++){
        queue<int> q;
        q.push(i);
        memset(dist, -1, sizeof(dist));
        dist[i] = 0;
        parent[i] = -1;
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int v: AdjList[u]){
                if(dist[v] == -1){
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    q.push(v);
                }
            }
        }
        for(int j = i; j <= N; j ++){
            vector<int> path;

            int temp1 = j;
            do{
                path.push_back(temp1);
                temp1 = parent[temp1];
            }while(temp1 != -1);

            reverse(path.begin(), path.end());

            int size1 = path.size();
            for(int k = 0; k < (1<<size1); k ++){
                int cnt = 0;
                long long score = 0;
                for(int l = 0; l < size1; l ++){
                    if(k&(1<<l)){
                        cnt ++;
                    }
                }
                if(cnt > v){continue;}

                for(int k = 1; k <= N; k ++){
                    p2[k] = p[k];
                }
                for(int l = 0; l < size1; l ++){
                    score -= p2[path[l]];
                    if(k&(1<<l)){
                        // drop breadcrumb
                        long long temp = p2[path[l]];
                        for(int x: AdjList[path[l]]){
                            temp += p2[x];
                            p2[x] = 0;
                        }
                        p2[path[l]] = temp;
                    }else{
                        // do not drop breadcrumb
                    }
                }
                long long tom = 0;
                for(int l = 0; l < size1; l ++){
                    score += p2[path[l]];
                    tom += p2[path[l]];
                }
                /*if(i == 6 && j == 7){
                    for(int l = 0; l < size1; l ++){
                        printf("PATH: %d\n", path[l]);
                    }
                    printf("%lld %lld\n", score, tom);
                }*/
                ans = max(ans, score);
            }
        }
    }
    printf("%lld", ans);

    return 0;
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:17:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d", &p[i]);
                     ~~~~~^
chase.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &v);
     ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p[i]);
         ~~~~~^~~~~~~~~~~~~
chase.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30