oj.uz

Submission #851126

# Submission time Handle Problem Language Result Execution time Memory
851126 2023-09-18T14:49:56 Z Itamar Paths (RMI21_paths) C++14
56 / 100
 599 ms 3668 KB 
// greedy cat.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
using namespace std;
#include <vector>
#define ll long long
#define pll pair<ll,ll>
#define vll vector<ll>
#include <queue>
const int siz = 2000;
vector<pll> fr[siz];
ll ans[siz];
int N,K;
#include <algorithm>
#include <set>
pll dfs(int i, vector<pll>&pad,vector<vll>&vec) {
    pll ansi={0,i};
    for (pll j: fr[i]) {
        if (j.first != pad[i].first) {
            pad[j.first] = { i,j.second };
            pll k =dfs(j.first, pad, vec);
            //s.insert({ -k.first - j.second,k.second });
            vec.push_back({ -k.first - j.second,k.second,i });
            ansi = max(ansi, { k.first + j.second,k.second });

        }
    }
    return ansi;
}
bool visi[siz][siz];
void calc(int r) {
    //vector<vector<bool>> visi(N, vector<bool>(N));
    set<pll> s;
    vector<vll> vec;
    vector<pll> pad(N,{-1,-1});
    dfs(r,pad,vec);
    sort(vec.begin(), vec.end());
    //for (pll p : vec)s.insert(p);
    vector<bool> vis(N);
    vis[r] = 1;
    int it = 0;
    vector<pll> cl;
    for (int i = 0; i < K; i++) {
        if (it == vec.size())break;
        while (visi[vec[it][1]][vec[it][2]]){ 
            it++;
            if (it == vec.size())break;
        }
        if (it == vec.size())break;
        //visi[vec[it][1]][vec[it][2]] = 1;
        //vis[vec[it][2]] = 1;
        vll v = vec[it];
        ans[r] -= v[0];
        ll cur = 0;
        int x = v[1];
        while (!vis[x]) {
            cur += pad[x].second;
            vis[x] = 1;
            visi[v[1]][pad[x].first] = 1;
            cl.push_back({ v[1],pad[x].first });
            x = pad[x].first;
            //if (x == r)break;else x = pad[x].first;
        }
    }
    for (pll p : cl)visi[p.first][p.second] = 0;
}

int main()
{
    int n,k;
    cin >> n >> k;
    N = n, K =k;
    for (int i = 0; i < n - 1; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        x--, y--;
        fr[x].push_back({ y,c });
        fr[y].push_back({ x,c });
    }
    for(int r = 0; r < n; r++)calc(r);
    for (int i = 0; i < n; i++)cout << ans[i] << "\n";
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Compilation message

Main.cpp: In function 'void calc(int)':
Main.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if (it == vec.size())break;
      |             ~~~^~~~~~~~~~~~~
Main.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             if (it == vec.size())break;
      |                 ~~~^~~~~~~~~~~~~
Main.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if (it == vec.size())break;
      |             ~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 6 ms 600 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 6 ms 600 KB Output is correct
8 Correct 123 ms 1072 KB Output is correct
9 Correct 113 ms 856 KB Output is correct
10 Correct 116 ms 848 KB Output is correct
11 Correct 115 ms 1012 KB Output is correct
12 Correct 117 ms 1056 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 6 ms 600 KB Output is correct
8 Correct 123 ms 1072 KB Output is correct
9 Correct 113 ms 856 KB Output is correct
10 Correct 116 ms 848 KB Output is correct
11 Correct 115 ms 1012 KB Output is correct
12 Correct 117 ms 1056 KB Output is correct
13 Correct 580 ms 3116 KB Output is correct
14 Correct 510 ms 1616 KB Output is correct
15 Correct 495 ms 1112 KB Output is correct
16 Correct 564 ms 2640 KB Output is correct
17 Correct 599 ms 2176 KB Output is correct
18 Correct 287 ms 1372 KB Output is correct
19 Correct 595 ms 3668 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 6 ms 600 KB Output is correct
8 Correct 123 ms 1072 KB Output is correct
9 Correct 113 ms 856 KB Output is correct
10 Correct 116 ms 848 KB Output is correct
11 Correct 115 ms 1012 KB Output is correct
12 Correct 117 ms 1056 KB Output is correct
13 Correct 580 ms 3116 KB Output is correct
14 Correct 510 ms 1616 KB Output is correct
15 Correct 495 ms 1112 KB Output is correct
16 Correct 564 ms 2640 KB Output is correct
17 Correct 599 ms 2176 KB Output is correct
18 Correct 287 ms 1372 KB Output is correct
19 Correct 595 ms 3668 KB Output is correct
20 Runtime error 1 ms 600 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -