oj.uz

Submission #597791

# Submission time Handle Problem Language Result Execution time Memory
597791 2022-07-16T21:54:17 Z ThegeekKnight16 Paths (RMI21_paths) C++17
8 / 100
 9 ms 724 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 10;
int Dist[MAXN];
vector<int> folhas;
vector<int> grafo[MAXN];
vector<long long int> pesos[MAXN];
vector<int> Marc[MAXN];
int pai[MAXN], indicesPai[MAXN];

void dfs(int v) 
{
    for (int i = 0; i < grafo[v].size(); i++)
    {
        int viz = grafo[v][i];
        int p = pesos[v][i];
        if (viz == pai[v]) continue;
        if (Marc[v][i]) p = 0;
        pai[viz] = v; indicesPai[viz] = i;
        Dist[viz] = Dist[v] + p;
        dfs(viz);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    for (int i = 1; i < N; i++)
    {
        int X, Y;
        long long int P;
        cin >> X >> Y >> P;
        grafo[X].push_back(Y);
        pesos[X].push_back(P);
        grafo[Y].push_back(X);
        pesos[Y].push_back(P);
        Marc[X].push_back(0);
        Marc[Y].push_back(0);
    }
    
    for (int i = 1; i <= N; i++) if (grafo[i].size() == 1) folhas.push_back(i);
    
    long long int resp = 0;
    for (int v = 1; v <= N; v++)
    {
        resp = 0;
        //cerr << "v: " << v << '\n';
        for (int k = 1; k <= K; k++)
        {
            Dist[v] = 0; pai[v] = v;
            dfs(v);
            
            int aux = -1; int auxF = 0;
            for (int folha : folhas)
            {
                if (folha == v) continue;
                if (Dist[folha] > aux)
                {
                    aux = Dist[folha];
                    auxF = folha;
                }
            }
            resp += aux;
            while (auxF != v)
            {
                //cerr << auxF << " " << pai[auxF] << " " << indicesPai[auxF] << '\n';
                Marc[pai[auxF]][indicesPai[auxF]] = 1;
                auxF = pai[auxF];
            }
            //cerr << '\n';
        }
        
        cout << resp << '\n';
        
        for (int i = 1; i <= N; i++)
        {
            for (int j = 0; j < Marc[i].size(); j++) Marc[i][j] = 0;
        }
    }
}

Compilation message

Main.cpp: In function 'void dfs(int)':
Main.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < grafo[v].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:80:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             for (int j = 0; j < Marc[i].size(); j++) Marc[i][j] = 0;
      |                             ~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Incorrect 9 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Incorrect 9 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Incorrect 9 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 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 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Incorrect 9 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -