Submission #498658

#	Time	Username	Problem	Language	Result	Execution time	Memory
498658		model_code	Paths (RMI21_paths)	C++17	56 / 100	221 ms	604 KiB

Main

// paths_subtask4_alexandra.cpp

//N^2 logN
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define DIM 2005
using namespace std;
int n, k, i, j, nr, x, y, c;
long long lantMax[DIM], lanturi[DIM], sum;
vector< pair<int, int> > v[DIM];
void dfs(int nod, int t) {
    for (int i = 0; i < v[nod].size(); i++) {
        int fiu = v[nod][i].first;
        if (fiu == t) {
            continue;
        }
        dfs(fiu, nod);
        lantMax[nod] = max(lantMax[nod], lantMax[fiu] + v[nod][i].second);
    }
    bool ok = false;
    for (int i = 0; i < v[nod].size(); i++) {
        int fiu = v[nod][i].first;
        if (fiu == t) {
            continue;
        }
        if (lantMax[nod] != lantMax[fiu] + v[nod][i].second || ok) {
            lanturi[++nr] = lantMax[fiu] + v[nod][i].second;
        }
        else {
            ok = true;
        }
    }
}
int main() {
    cin>> n >> k;
    for (i = 1; i < n; i++) {
        cin>> x >> y >> c;
        v[x].push_back(make_pair(y, c));
        v[y].push_back(make_pair(x, c));
    }
    for (i = 1; i <= n; i++) {
        nr = 0;
        memset(lantMax, 0, sizeof(lantMax));
        dfs(i, 0);
        lanturi[++nr] = lantMax[i];
        sum = 0;
        sort(lanturi + 1, lanturi + nr + 1);
        for (j = nr; j >= nr - k + 1; j--) {
            sum += lanturi[j];
        }
        cout<< sum <<"\n";
    }
}

Compilation message (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32