oj.uz

답안 #1108780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1108780 2024-11-05T04:02:03 Z cpptowin Paths (RMI21_paths) C++17
100 / 100
 259 ms 40148 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 100010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
#define UNIQUE(v) v.erase(unique(all(v)), v.end())
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if (x < 0)
        x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if (x < 0)
        x += mod;
}
vii ke[maxn];
int n, k;
pair<int,int> down[maxn], up[maxn];
int f[maxn];
int par[maxn][20];
int a[maxn];
int num[maxn];
int h[maxn];
vi leaves;
int ans, res[maxn];
set<pair<int,int>> q, q1;
void dfs(int u)
{
    if(ss(ke[u]) > 1 or (u == 1)) up[u].fi = -1;
    up[u].se = u;
    for (auto [v, w] : ke[u])
        if (v != par[u][0])
        {
            par[v][0] = u;
            h[v] = h[u] + 1;
            f[v] = f[u] + w;
            fo(i, 1, 19) par[v][i] = par[par[v][i - 1]][i - 1];
            dfs(v);
            if (maximize(up[u].fi, up[v].fi + w))
                up[u].se = up[v].se;
        }
}
void dfsdown(int u)
{
    vector<pair<int,int>> suf(ss(ke[u]) + 2, {0, 0});
    suf[ss(ke[u]) + 1] = down[u];
    pair<int,int> pre = {-1, -1};
    fod(i, ss(ke[u]), 1)
    {
        auto [v, w] = ke[u][i - 1];
        suf[i] = suf[i + 1];
        if (v == par[u][0])
            continue;
        if (maximize(suf[i].fi, up[v].fi + w))
            suf[i].se = up[v].se;
    }
    fo(i, 1, ss(ke[u]))
    {
        auto [v, w] = ke[u][i - 1];
        if (v == par[u][0])
            continue;
        down[v] = {pre.fi + w, pre.se};
        if (maximize(down[v].fi, suf[i + 1].fi + w))
            down[v].se = suf[i + 1].se;
        if (maximize(pre.fi, up[v].fi + w))
            pre.se = up[v].se;
    }
    for (auto [v, w] : ke[u])
        if (v != par[u][0])
        {
            dfsdown(v);
        }
}
int find(int u)
{
    int cc = u;
    fod(i, 19, 0) if (up[par[u][i]].se == cc)
    {
        u = par[u][i];
    }
    return par[u][0];
}
vector<pair<int,int>> event;
void to(int x, int y)
{
    int u = down[y].se;
    event.pb(u, num[u]);
    if (q.find({num[u], u}) != q.end())
    {
        q.erase(q.find({num[u], u}));
        num[u] = down[y].fi;
        q.insert({num[u], u});
    }
    else if (q1.find({num[u], u}) != q1.end())
    {
        q1.erase(q1.find({num[u], u}));
        ans -= num[u];
        num[u] = down[y].fi;
        ans += num[u];
        q1.insert({num[u], u});
    }
    u = up[y].se;
    event.pb(u, num[u]);
    if (q.find({num[u], u}) != q.end())
    {
        q.erase(q.find({num[u], u}));
        num[u] = up[y].fi;
        q.insert({num[u], u});
    }
    else if (q1.find({num[u], u}) != q1.end())
    {
        q1.erase(q1.find({num[u], u}));
        ans -= num[u];
        num[u] = up[y].fi;
        ans += num[u];
        q1.insert({num[u], u});
    }
    if (ss(q) and ss(q1) and q1.begin()->fi < q.rbegin()->fi)
    {
        ans -= q1.begin()->fi;
        ans += q.rbegin()->fi;
        pii it = *q1.begin();
        pii it1 = *q.rbegin();
        q1.erase(q1.find(it));
        q.erase(q.find(it1));
        q1.insert(it1);
        q.insert(it);
    }
}
void rollback()
{
    int u = event.back().fi;
    int du = event.back().se;
    event.pop_back();
    if (q.find({num[u], u}) != q.end())
    {
        q.erase(q.find({num[u], u}));
        num[u] = du;
        q.insert({num[u], u});
    }
    else if (q1.find({num[u], u}) != q1.end())
    {
        q1.erase(q1.find({num[u], u}));
        ans -= num[u];
        num[u] = du;
        ans += num[u];
        q1.insert({num[u], u});
    }
    u = event.back().fi;
    du = event.back().se;
    event.pop_back();
    if (q.find({num[u], u}) != q.end())
    {
        q.erase(q.find({num[u], u}));
        num[u] = du;
        q.insert({num[u], u});
    }
    else if (q1.find({num[u], u}) != q1.end())
    {
        q1.erase(q1.find({num[u], u}));
        ans -= num[u];
        num[u] = du;
        ans += num[u];
        q1.insert({num[u], u});
    }
    if (ss(q) and ss(q1) and q1.begin()->fi < q.rbegin()->fi)
    {
        ans -= q1.begin()->fi;
        ans += q.rbegin()->fi;
        pii it = *q1.begin();
        pii it1 = *q.rbegin();
        q1.erase(q1.find(it));
        q.erase(q.find(it1));
        q1.insert(it1);
        q.insert(it);
    }
}
void dfs1(int u)
{
    res[u] = ans;
    for (auto [v, w] : ke[u])
        if (v != par[u][0])
        {
            to(u, v);
            dfs1(v);
            rollback();
        }
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    fo(i, 1, n - 1)
    {
        int u, v, w;
        cin >> u >> v >> w;
        ke[u].pb(v, w);
        ke[v].pb(u, w);
    }
    dfs(1);
    down[1] = {0,1};
    dfsdown(1);
    fo(i, 1, n) if (ss(ke[i]) == 1) leaves.pb(i);
    for (int it : leaves)
    {
        a[it] = find(it);
        if(!a[it]) a[it] = 1;
        num[it] = f[it] - f[a[it]];
        // cout << it << ' ' << a[it];en;
        q.insert({num[it], it});
    }
    down[1] = {0, 1};
    int cc = k;
    while (ss(q) and cc > 0)
    {
        ans += q.rbegin()->fi;
        q1.insert(*q.rbegin());
        q.erase(q.find(*q.rbegin()));
        cc--;
    }
    dfs1(1);
    fo(i, 1, n) cout << res[i] << "\n";
}

Compilation message

Main.cpp:232:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  232 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:237:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  237 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:238:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct
8 Correct 3 ms 9040 KB Output is correct
9 Correct 3 ms 9040 KB Output is correct
10 Correct 5 ms 9040 KB Output is correct
11 Correct 4 ms 9040 KB Output is correct
12 Correct 3 ms 9040 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct
8 Correct 3 ms 9040 KB Output is correct
9 Correct 3 ms 9040 KB Output is correct
10 Correct 5 ms 9040 KB Output is correct
11 Correct 4 ms 9040 KB Output is correct
12 Correct 3 ms 9040 KB Output is correct
13 Correct 5 ms 9296 KB Output is correct
14 Correct 5 ms 9592 KB Output is correct
15 Correct 4 ms 9296 KB Output is correct
16 Correct 5 ms 9296 KB Output is correct
17 Correct 4 ms 9296 KB Output is correct
18 Correct 4 ms 9296 KB Output is correct
19 Correct 4 ms 9296 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 35404 KB Output is correct
2 Correct 205 ms 37828 KB Output is correct
3 Correct 144 ms 32148 KB Output is correct
4 Correct 202 ms 35284 KB Output is correct
5 Correct 188 ms 36488 KB Output is correct
6 Correct 189 ms 35452 KB Output is correct

Subtask #6
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct
8 Correct 3 ms 9040 KB Output is correct
9 Correct 3 ms 9040 KB Output is correct
10 Correct 5 ms 9040 KB Output is correct
11 Correct 4 ms 9040 KB Output is correct
12 Correct 3 ms 9040 KB Output is correct
13 Correct 5 ms 9296 KB Output is correct
14 Correct 5 ms 9592 KB Output is correct
15 Correct 4 ms 9296 KB Output is correct
16 Correct 5 ms 9296 KB Output is correct
17 Correct 4 ms 9296 KB Output is correct
18 Correct 4 ms 9296 KB Output is correct
19 Correct 4 ms 9296 KB Output is correct
20 Correct 203 ms 35404 KB Output is correct
21 Correct 205 ms 37828 KB Output is correct
22 Correct 144 ms 32148 KB Output is correct
23 Correct 202 ms 35284 KB Output is correct
24 Correct 188 ms 36488 KB Output is correct
25 Correct 189 ms 35452 KB Output is correct
26 Correct 209 ms 35792 KB Output is correct
27 Correct 213 ms 37708 KB Output is correct
28 Correct 236 ms 38256 KB Output is correct
29 Correct 140 ms 32328 KB Output is correct
30 Correct 241 ms 35600 KB Output is correct
31 Correct 202 ms 35780 KB Output is correct
32 Correct 248 ms 38980 KB Output is correct
33 Correct 243 ms 37828 KB Output is correct
34 Correct 117 ms 34120 KB Output is correct
35 Correct 259 ms 37668 KB Output is correct
36 Correct 206 ms 40148 KB Output is correct