oj.uz

Submission #626547

# Submission time Handle Problem Language Result Execution time Memory
626547 2022-08-11T14:20:32 Z tamthegod Paths (RMI21_paths) C++14
19 / 100
 230 ms 72676 KB 
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, k;
vector<pair<int, int>> adj[maxN];
int f[maxN], dp[maxN];
void ReadInput()
{
    cin >> n >> k;
    for(int i=1; i<n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
}
void predfs(int u, int par)
{
    for(auto a : adj[u])
    {
        int v = a.fi, w = a.se;
        if(v == par) continue;
        predfs(v, u);
        f[u] = max(f[u], f[v] + w);
    }
}
void predfs1(int u, int par)
{
    vector<pair<int, int>> vc;
    for(auto a : adj[u])
    {
        int v = a.fi, w = a.se;
        if(v == par) continue;
        vc.pb({f[v] + w, v});
    }
    sort(vc.begin(), vc.end(), greater<pair<int, int>>());
    for(auto a : adj[u])
    {
        int v = a.fi, w = a.se;
        if(v == par) continue;
        if(v != vc[0].se) dp[v] = max(dp[u] + w, vc[0].fi + w);
        else dp[v] = max(dp[u] + w, vc[1].fi + w);
        predfs1(v, u);
    }
}
multiset<int, greater<int>> s, s1;
void dfs(int u, int par, int root)
{
    int _max = 0, id = 0;
    for(auto a : adj[u])
    {
        int v = a.fi, w = a.se;
        if(v == par) continue;
        dfs(v, u, root);
        if(f[v] + w > _max)
        {
            _max = f[v] + w;
            id = v;
        }
    }
   // cout << u << " " << _max << "\n";
    for(auto a : adj[u])
    {
        int v = a.fi, w = a.se;
        if(v == par || v == id) continue;
        s.insert(f[v] + w);
    }
    if(u == root) s.insert(f[u]);
}
int res[maxN], sum = 0;
void add(int val)
{
    auto it = s.end();
    it--;
    if(*it < val)
    {
        sum -= *it;
        sum += val;
        s1.insert(*it);
        s.erase(it);
        s.insert(val);
    }
    else s1.insert(val);
}
void del(int val)
{
    if(s.find(val) != s.end())
    {
        sum -= val;
        s.erase(s.find(val));
        if(s1.empty()) return;
        sum += *s1.begin();
        s.insert(*s1.begin());
        s1.erase(s1.begin());
    }
    else s1.erase(s1.find(val));
}
void reroot(int u, int par)
{
    res[u] = sum;
    for(auto a : adj[u])
    {
        int v = a.fi, w = a.se;
        if(v == par) continue;
        add(f[v]);
        add(dp[v]);
        del(f[v] + w);
        del(dp[v] - w);
        reroot(v, u);
        add(f[v] + w);
        add(dp[v] - w);
        del(dp[v]);
        del(f[v]);
    }
}
void Solve()
{
    predfs(1, 0);
    predfs1(1, 0);
    dfs(1, 0, 1);
    for(int v : s) sum += v;
    while(s.size() > k)
    {
        auto it = s.end();
        it--;
        sum -= *it;
        s1.insert(*it);
        s.erase(it);
    }
    reroot(1, 0);
    for(int i=1; i<=n; i++) cout << res[i] << '\n';
}
int32_t main()
{
   // freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Compilation message

Main.cpp: In function 'void Solve()':
Main.cpp:134:20: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  134 |     while(s.size() > k)
      |           ~~~~~~~~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23788 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23856 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23788 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23856 KB Output is correct
8 Runtime error 33 ms 48348 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23788 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23856 KB Output is correct
8 Runtime error 33 ms 48348 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 34744 KB Output is correct
2 Runtime error 145 ms 72676 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23788 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23856 KB Output is correct
8 Runtime error 33 ms 48348 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -