oj.uz

Submission #643915

# Submission time Handle Problem Language Result Execution time Memory
643915 2022-09-23T08:37:51 Z Neacsu_Mihai Paths (RMI21_paths) C++14
19 / 100
 600 ms 9588 KB 
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

#define NMAX 100000 //o suta de mii
#define INFINIT 100000000000000 //10^14

using namespace std;

vector< pair<int, int> > G[NMAX + 1];
vector <int> frunza;
int tt[NMAX + 1];
int costtt[NMAX + 1];

void DFS(int node, int tata){
    
    for(auto it : G[node]){
        if(it.first != tata){
            tt[it.first] = node;
            costtt[it.first] = it.second;
            DFS(it.first, node);
        }
    }
    
    if(G[node].size() == 1){
        ///este frunza
        frunza.push_back(node);
    }
    
}

long long cost_to_radacina(int node){
    long long rez = 0;
    while(tt[node] != 0){
        rez = rez + 1LL * costtt[node];
        node = tt[node];   
    }
    
    return rez;
}

void update_to_radacina(int node){
    while(tt[node] != 0){
        costtt[node] = 0;
        node = tt[node];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    cin >> N >> K;
    
    for(int i = 1; i <= N - 1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    
    for(int rad = 1; rad <= N; rad++){
        frunza.clear();
        for(int i = 1; i <= N; i++){
            tt[i] = 0;
            costtt[i] = 0;
        }
        DFS(rad, 0);
            
        long long bestfinal = 0;
        for(int rep = 1; rep <= K; rep++){
            long long crbest = 0;
            int crnode = -1;
            for(auto it : frunza){
                long long ctorad = cost_to_radacina(it);
                
                if(ctorad > crbest){
                    crbest = ctorad;
                    crnode = it;
                }
            }
            
            bestfinal = bestfinal + crbest;
            update_to_radacina(crnode);
        }
        
        cout << bestfinal << "\n";
    }
        
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 9 ms 2644 KB Output is correct
4 Correct 24 ms 2692 KB Output is correct
5 Correct 6 ms 2644 KB Output is correct
6 Correct 6 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 9 ms 2644 KB Output is correct
4 Correct 24 ms 2692 KB Output is correct
5 Correct 6 ms 2644 KB Output is correct
6 Correct 6 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct
8 Execution timed out 1082 ms 2860 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 9 ms 2644 KB Output is correct
4 Correct 24 ms 2692 KB Output is correct
5 Correct 6 ms 2644 KB Output is correct
6 Correct 6 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct
8 Execution timed out 1082 ms 2860 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 9588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 9 ms 2644 KB Output is correct
4 Correct 24 ms 2692 KB Output is correct
5 Correct 6 ms 2644 KB Output is correct
6 Correct 6 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct
8 Execution timed out 1082 ms 2860 KB Time limit exceeded
9 Halted 0 ms 0 KB -