Submission #597791

#	Time	Username	Problem	Language	Result	Execution time	Memory
597791		ThegeekKnight16	Paths (RMI21_paths)	C++17	8 / 100	9 ms	724 KiB

Main

#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 (stderr)

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 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32