Submission #963772

#	Time	Username	Problem	Language	Result	Execution time	Memory
963772		Nhoksocqt1	도로 폐쇄 (APIO21_roads)	C++17	100 / 100	160 ms	72836 KiB

roads

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

class DisjointSet {
    private:
        vector<int> lab;

    public:
        DisjointSet(int _n = 0) {
            lab.assign(_n + 7, -1);
        }

        int find(int u) {
            return (lab[u] < 0) ? u : (lab[u] = find(lab[u]));
        }

        bool join(int u, int v) {
            u = find(u), v = find(v);
            if(u == v)
                return (false);

            if(lab[u] > lab[v])
                swap(u, v);

            lab[u] += lab[v];
            lab[v] = u;
            return (true);
        }
} dsu;

struct Edge {
    int u, v, w;
} edge[MAXN];

vector<int> B[MAXN], idw[MAXN];
vector<ii> adj[MAXN];
li *fen[MAXN];
ll dp[MAXN][2], f[2003][2003][2];
int sz[MAXN], pa[MAXN], deg[MAXN], numNode;
bool dx[MAXN];

vector<ll> sub1(void) {
    sort(edge, edge + numNode - 1, [](const Edge &a, const Edge &b) {
        return (a.w > b.w);
    });

    vector<ll> ans;
    ll sumCost(0);
    for (int i = 0; i < numNode - 1; ++i)
        sumCost += edge[i].w;

    for (int i = 0; i < numNode; ++i) {
        ans.push_back(sumCost);
        sumCost -= edge[i].w;
    }

    return ans;
}

vector<ll> sub2(void) {
    vector<ll> ans;
    ll sumCost(0);

    dp[0][0] = dp[0][1] = 0;
    for (int i = 0; i < numNode - 1; ++i) {
        sumCost += edge[i].w;
        dp[i + 1][0] = max(dp[i][1], dp[i][0]);
        dp[i + 1][1] = dp[i][0] + edge[i].w;
    }

    ans.push_back(sumCost);
    ans.push_back(sumCost - max(dp[numNode - 1][0], dp[numNode - 1][1]));

    for (int i = 2; i < numNode; ++i)
        ans.push_back(0);

    return ans;
}

typedef pair<ll, ll> pll;
void dfsDP(int u) {
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it].fi), w(adj[u][it].se);
        if(v != pa[u]) {
            pa[v] = u;
            dfsDP(v);
            f[u][0][0] += f[v][0][0];
            f[u][0][1] += f[v][0][1];
        }
    }

    for (int i = 1; i < numNode; ++i) {
        vector<pll> p;
        for (int it = 0; it < sz(adj[u]); ++it) {
            int v(adj[u][it].fi), w(adj[u][it].se);
            if(v != pa[u])
                p.push_back(pll(max(f[v][i - 1][1], f[v][i][0]) + w, max(f[v][i][0], f[v][i][1])));
        }

        sort(p.begin(), p.end(), [](const pll &a, const pll &b) {
            return a.fi - a.se > b.fi - b.se;
        });

        f[u][i][0] = -1e18;
        for (int j = 0; j < sz(p); ++j) {
            f[u][i][0] = max(f[u][i][0] + (j < i ? max(p[j].fi, p[j].se) : p[j].se), (j < i ? f[u][i][1] + p[j].se : 0LL));
            f[u][i][1] += (j < i) ? max(p[j].fi, p[j].se) : p[j].se;
        }

        if(sz(p) < i)
            f[u][i][0] = max(f[u][i][0], f[u][i][1]);
    }
}

vector<ll> sub4(void) {
    ll sumCost(0);
    for (int i = 0; i + 1 < numNode; ++i) {
        int u(edge[i].u), v(edge[i].v), w(edge[i].w);
        adj[u].push_back(ii(v, w));
        adj[v].push_back(ii(u, w));
        sumCost += w;
    }

    pa[0] = -1;
    dfsDP(0);

    vector<ll> ans;
    for (int i = 0; i < numNode; ++i)
        ans.push_back(sumCost - max(f[0][i][0], f[0][i][1]));

    return ans;
}

void modify(li fen[], int i, int n, li v) {
    for (; i <= n; i += i & -i)
        fen[i] = {fen[i].fi + v.fi, fen[i].se + v.se};
}

li get(li fen[], int i) {
    li res = {0, 0};
    for (; i > 0; i -= i & -i)
        res = {res.fi + fen[i].fi, res.se + fen[i].se};

    return res;
}

ll getKMaximum(li fen[], int n, int k) {
    li res = {0, 0};
    int i(0), cnt(0);
    for (int j = 31 - __builtin_clz(n); j >= 0; --j) {
        if(i + (1 << j) <= n && fen[i + (1 << j)].se + res.se <= k) {
            i += (1 << j);
            res = {res.fi + fen[i].fi, res.se + fen[i].se};
        }
    }

    k -= res.se;
    if(k > 0 && i < n) {
        li ans = get(fen, i + 1);
        ans = {ans.fi - res.fi, ans.se - res.se};
        //cout << ',' << ans.fi << '\n';
        res.fi += ans.fi / ans.se * k;
    }

    return res.fi;
}

void dfs(int u, int p, int k) {
    dp[u][0] = dp[u][1] = dx[u] = 0;

    vector<ll> pw;
    ll sumAdd(0);
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it].fi), w(adj[u][it].se);
        if(sz(adj[v]) <= k)
            break;

        if(v != p) {
            dfs(v, u, k);
            sumAdd += dp[v][0];
            pw.push_back(dp[v][1] + w - dp[v][0]);
        }
    }

    sort(pw.begin(), pw.end(), greater<ll>());
    for (int i = 0; i <= min(sz(pw), k); ++i) {
        dp[u][0] = max(dp[u][0], sumAdd + getKMaximum(fen[u], sz(idw[u]), k - i));

        if(i < k)
            dp[u][1] = max(dp[u][1], sumAdd + getKMaximum(fen[u], sz(idw[u]), k - i - 1));

        if(i < sz(pw))
            sumAdd += pw[i];
    }
}

vector<ll> magicFunc(void) {
    vector<int> perm;
    for (int i = 0; i < numNode; ++i) {
        perm.push_back(i);
        if(i + 1 < numNode) {
            int u(edge[i].u), v(edge[i].v), w(edge[i].w);
            adj[u].push_back(ii(v, w));
            adj[v].push_back(ii(u, w));
        }
    }

    sort(perm.begin(), perm.end(), [](const int &a, const int &b) {
        return (sz(adj[a]) > sz(adj[b]));
    });

    ll sumCost(0);
    for (int i = 0; i + 1 < numNode; ++i)
        sumCost += edge[i].w;

    for (int i = 0; i < numNode; ++i) {
        for (int it = 0; it < sz(adj[i]); ++it) {
            int j(adj[i][it].fi), w(adj[i][it].se);
            idw[i].push_back(w);
        }

        sort(idw[i].begin(), idw[i].end());
        idw[i].erase(unique(idw[i].begin(), idw[i].end()), idw[i].end());

        sort(adj[i].begin(), adj[i].end(), [](const ii &a, const ii &b) {
            return (sz(adj[a.fi]) > sz(adj[b.fi]));
        });

        fen[i] = new li[sz(idw[i]) + 1];
        for (int j = 0; j <= sz(idw[i]); ++j)
            fen[i][j] = {0, 0};

        B[sz(adj[i])].push_back(i);
        dx[i] = 0;
    }

    vector<ll> ans;
    ans.push_back(sumCost);

    ll sumAdd(0);
    for (int k = 1; k < numNode; ++k) {
        for (int it = 0; it < sz(B[k]); ++it) {
            int u(B[k][it]);
            for (int jt = 0; jt < sz(adj[u]); ++jt) {
                int v(adj[u][jt].fi), w(adj[u][jt].se);
                //cout << k << ' ' << u << ' ' << v << ' ' << w << ' ' << sz(adj[u]) << ' ' << sz(adj[v]) << '\n';
                if(sz(adj[v]) <= k) {
                    sumAdd += (sz(adj[u]) != sz(adj[v]) || u < v) * w;
                    //cout << "+ " << k << ' ' << w << '\n';
                } else {
                    // insert w to node v
                    int pos = upper_bound(idw[v].begin(), idw[v].end(), w) - idw[v].begin();
                    modify(fen[v], sz(idw[v]) - pos + 1, sz(idw[v]), li(w, 1));
                    //cout << "+ " << k << ' ' << v << ' ' << sz(idw[v]) - pos + 1 << ' ' << w << '\n';
                }
            }
        }

        for (int it = 0; it < sz(perm); ++it) {
            int u(perm[it]);
            if(sz(adj[u]) <= k)
                break;

            dx[u] = 1;
        }

        ll result(sumAdd);
        for (int it = 0; it < sz(perm); ++it) {
            int u(perm[it]);
            if(sz(adj[u]) <= k)
                break;

            if(dx[u]) {
                dfs(u, -1, k);
                result += dp[u][0];
            }
        }

        ans.push_back(sumCost - result);
    }

    return ans;
}

vector<ll> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W) {
    numNode = _N;

    bool check_sub1(1), check_sub2(1);
    for (int i = 0; i + 1 < numNode; ++i) {
        edge[i] = {_U[i], _V[i], _W[i]};
        if(edge[i].u > edge[i].v)
            swap(edge[i].u, edge[i].v);

        check_sub1 &= (edge[i].u == 0);
        check_sub2 &= (edge[i].u == i && edge[i].v == i + 1);
    }

    if(check_sub1)
        return sub1();

    if(check_sub2)
        return sub2();

    if(numNode <= 2000)
        return sub4();

    return magicFunc();
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "roads"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> u, v, w;
    int n;
    cin >> n;
    //n = Random(10, 1000); cout << n << '\n';

    u.resize(n - 1), v.resize(n - 1), w.resize(n - 1);
    for (int i = 0; i + 1 < n; ++i) {
        cin >> u[i] >> v[i] >> w[i];
        //u[i] = Random(0, i), v[i] = i + 1, w[i] = Random(1, 100); cout << u[i] << ' ' << v[i] << ' ' << w[i] << '\n';
    }

    vector<ll> ans = minimum_closure_costs(n, u, v, w);
    cout << "ANSWER: ";
    for (int it = 0; it < sz(ans); ++it)
        cout << ans[it] << ' '; cout << '\n';

    return 0;
}

#endif // Nhoksocqt1

Compilation message (stderr)

roads.cpp: In function 'void dfsDP(int)':
roads.cpp:103:31: warning: unused variable 'w' [-Wunused-variable]
  103 |         int v(adj[u][it].fi), w(adj[u][it].se);
      |                               ^
roads.cpp: In function 'll getKMaximum(li*, int, int)':
roads.cpp:169:15: warning: unused variable 'cnt' [-Wunused-variable]
  169 |     int i(0), cnt(0);
      |               ^~~
roads.cpp: In function 'std::vector<long long int> magicFunc()':
roads.cpp:238:17: warning: unused variable 'j' [-Wunused-variable]
  238 |             int j(adj[i][it].fi), w(adj[i][it].se);
      |                 ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22