oj.uz

Submission #646806

# Submission time Handle Problem Language Result Execution time Memory
646806 2022-09-30T17:56:14 Z notme Paths (RMI21_paths) C++14
19 / 100
 600 ms 4812 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 1005;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, k;
map < pair < long long, long long >, long long > mp;
long long c[MAXN];
vector < long long > g[MAXN];
vector < long long > v[MAXN];
void read()
{
    cin >> n >> k;
    long long xx, yy, cc;
    for (long long i = 1; i < n; ++ i)
    {
        cin >> xx >> yy >> cc;
        mp[make_pair(xx, yy)] = i;
        mp[make_pair(yy, xx)] = i;
        g[xx].push_back(yy);
        g[yy].push_back(xx);
        c[i] = cc;
    }
}
long long p[MAXN], used[MAXN];
vector < int > leafs;
void dfs(long long beg)
{
    used[beg] = 1;
    long long nb, cnt = 0;
    for (long long i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i];
        if(!used[nb])
        {
            cnt ++;
            dfs(nb);
            p[nb] = beg;
        }
    }
    if(!cnt)leafs.push_back(beg);
}
long long sum[MAXN];
long long r;
void jump(long long vertex)
{
    long long leaf = vertex;
    while(vertex != r)
    {
        long long nomer = mp[make_pair(vertex, p[vertex])];
        v[nomer].push_back(leaf);
        sum[leaf] += c[nomer];
        vertex = p[vertex];
    }
}
long long c1[MAXN];
void make_zero(long long vertex)
{
    long long leaf = vertex;
    while(vertex != r && vertex != 0)
    {
        //if(vertex)cout << vertex << endl;
        long long nomer = mp[make_pair(vertex, p[vertex])];
        for (long long j = 0; j < v[nomer].size(); ++ j)
        {
            sum[v[nomer][j]] -= c1[nomer];
           // c[nomer] = 0;
        }
        c1[nomer] = 0;
        int go = p[vertex];
        p[vertex] = p[p[vertex]];
        vertex = go;
    }
}
void solve_for_root(long long root)
{
    leafs.clear();
    memset(sum, 0, sizeof(sum));
    memset(used, 0, sizeof(used));
    memset(p, 0, sizeof(p));
    r = root;
    dfs(root);
    for (long long i = 1; i < n; ++ i)
        c1[i] = c[i];
    for (long long i = 1; i <= n; ++ i)
    {
       // cout << p[i] << " ";
        v[i].clear();
    }
    //cout << endl;
    for (long long i = 0; i < leafs.size(); ++ i)
    {
        jump(leafs[i]);
       // cout << sum[i] << " ";
    }
   // cout << endl;
   // cout << "nere???" << endl;
    long long ans = 0;
    long long sz = leafs.size();
    for (long long i = 0; i < min(sz, k); ++ i)
    {
        long long maxsum = 0, maxidx = 0;
        for (long long j = 0; j < leafs.size(); ++ j)
        {
            if(sum[leafs[j]] > maxsum)
            {
                maxsum = sum[leafs[j]];
                maxidx = leafs[j];
            }
        }
        //cout << "ended" << " " << maxidx << endl;
        ans += maxsum;
        make_zero(maxidx);
       /* for (long long j = 1; j <= n; ++ j)
            cout << sum[j] << " ";
        cout << endl;*/
    }
    cout << ans << endl;
}
int main()
{
    speed();

    read();
    for (long long i = 1; i <= n; ++ i)
        solve_for_root(i);
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(long long int)':
Main.cpp:36:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (long long i = 0; i < g[beg].size(); ++ i)
      |                           ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void make_zero(long long int)':
Main.cpp:69:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (long long j = 0; j < v[nomer].size(); ++ j)
      |                               ~~^~~~~~~~~~~~~~~~~
Main.cpp:64:15: warning: unused variable 'leaf' [-Wunused-variable]
   64 |     long long leaf = vertex;
      |               ^~~~
Main.cpp: In function 'void solve_for_root(long long int)':
Main.cpp:96:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (long long i = 0; i < leafs.size(); ++ i)
      |                           ~~^~~~~~~~~~~~~~
Main.cpp:108:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (long long j = 0; j < leafs.size(); ++ j)
      |                               ~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 10 ms 668 KB Output is correct
4 Correct 24 ms 616 KB Output is correct
5 Correct 7 ms 636 KB Output is correct
6 Correct 10 ms 524 KB Output is correct
7 Correct 10 ms 632 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 10 ms 668 KB Output is correct
4 Correct 24 ms 616 KB Output is correct
5 Correct 7 ms 636 KB Output is correct
6 Correct 10 ms 524 KB Output is correct
7 Correct 10 ms 632 KB Output is correct
8 Correct 482 ms 4812 KB Output is correct
9 Execution timed out 1089 ms 2764 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 10 ms 668 KB Output is correct
4 Correct 24 ms 616 KB Output is correct
5 Correct 7 ms 636 KB Output is correct
6 Correct 10 ms 524 KB Output is correct
7 Correct 10 ms 632 KB Output is correct
8 Correct 482 ms 4812 KB Output is correct
9 Execution timed out 1089 ms 2764 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 524 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 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 10 ms 668 KB Output is correct
4 Correct 24 ms 616 KB Output is correct
5 Correct 7 ms 636 KB Output is correct
6 Correct 10 ms 524 KB Output is correct
7 Correct 10 ms 632 KB Output is correct
8 Correct 482 ms 4812 KB Output is correct
9 Execution timed out 1089 ms 2764 KB Time limit exceeded
10 Halted 0 ms 0 KB -