oj.uz

Submission #598463

# Submission time Handle Problem Language Result Execution time Memory
598463 2022-07-18T11:35:53 Z CaroLinda Paths (RMI21_paths) C++14
56 / 100
 425 ms 736 KB 
#include <bits/stdc++.h>

//testing the quadratic

#define ll long long

const int MAXN = 2010;

using namespace std;

int N, K;
int par[MAXN];
ll prof[MAXN];
vector<pair<int,ll> > adj[MAXN];
bool used[MAXN];
ll edgParent[MAXN];

void dfs(int x){
    for(auto &e: adj[x]){
        if(e.first == par[x])
            continue;
        par[e.first] = x;
        prof[e.first]= prof[x]+e.second;
        edgParent[e.first] = e.second;
        dfs(e.first);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for(int i= 1, a, b, c; i < N; i++){
        cin >> a >> b >> c;

        adj[a].push_back(make_pair(b,c));
        adj[b].push_back(make_pair(a,c));
    }

    vector<int> meuVec(N);
    iota(meuVec.begin(),meuVec.end(),1);

    for(int i =1 ; i <= N; i++){
        par[i] = -1;
        prof[i] = 0;
        edgParent[i] = 0;

        dfs(i);

        sort(meuVec.begin(), meuVec.end(), [&](int a, int b){
            return prof[a] > prof[b];
        });

        vector<ll> realVec;

        for(int j = 1; j <= N; j++)
            used[j] = false;

        for(auto j : meuVec){
            ll cur = 0;
            int k = j;


            while(!used[k] && k != i){
                used[k] = true;
                cur += edgParent[k];
                k = par[k];
            }

            realVec.push_back(cur);
        }

        sort(realVec.begin(), realVec.end() );

        ll ans = 0;
        for(int i = N-1; i >= N-K; i--){
            ans += realVec[i];
        }

        cout << ans << "\n";
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 372 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 108 ms 496 KB Output is correct
9 Correct 84 ms 544 KB Output is correct
10 Correct 75 ms 492 KB Output is correct
11 Correct 83 ms 492 KB Output is correct
12 Correct 88 ms 492 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 108 ms 496 KB Output is correct
9 Correct 84 ms 544 KB Output is correct
10 Correct 75 ms 492 KB Output is correct
11 Correct 83 ms 492 KB Output is correct
12 Correct 88 ms 492 KB Output is correct
13 Correct 425 ms 600 KB Output is correct
14 Correct 359 ms 664 KB Output is correct
15 Correct 300 ms 736 KB Output is correct
16 Correct 403 ms 588 KB Output is correct
17 Correct 352 ms 592 KB Output is correct
18 Correct 202 ms 556 KB Output is correct
19 Correct 411 ms 596 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 108 ms 496 KB Output is correct
9 Correct 84 ms 544 KB Output is correct
10 Correct 75 ms 492 KB Output is correct
11 Correct 83 ms 492 KB Output is correct
12 Correct 88 ms 492 KB Output is correct
13 Correct 425 ms 600 KB Output is correct
14 Correct 359 ms 664 KB Output is correct
15 Correct 300 ms 736 KB Output is correct
16 Correct 403 ms 588 KB Output is correct
17 Correct 352 ms 592 KB Output is correct
18 Correct 202 ms 556 KB Output is correct
19 Correct 411 ms 596 KB Output is correct
20 Runtime error 1 ms 596 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -