oj.uz

Submission #101590

# Submission time Handle Problem Language Result Execution time Memory
101590 2019-03-19T04:45:52 Z cheeheng Chase (CEOI17_chase) C++14
20 / 100
 1111 ms 525312 KB 
#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

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.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Runtime error 1022 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1111 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Runtime error 1022 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -