제출 #106089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106089		Alexa2001	Designated Cities (JOI19_designated_cities)	C++17	23 / 100	28 ms	17664 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5;
typedef long long ll;

struct edge
{
    int to, toy, fromy;
};
vector<edge> v[Nmax];

ll ans[Nmax];
int n;


namespace special_case_for_one
{
    ll dfs(int node, int dad = 0)
    {
        ll sum = 0;
        for(auto it : v[node])
            if(it.to != dad)
                sum += it.fromy + dfs(it.to, node);
        return sum;
    }

    ll get_best(int node, int dad, ll now)
    {
        ll best = now;

        for(auto it : v[node])
            if(it.to != dad)
                best = max(best, get_best(it.to, node, now + it.toy - it.fromy));
        return best;
    }

    ll solve1()
    {
        return get_best(1, 0, dfs(1));
    }
}

namespace special_case
{
    int root;
    ll best2 = 0;

    pair<ll, int> best[Nmax];
    int w[Nmax], subarb[Nmax];
    ll c[Nmax];
    bool used[Nmax];
    int S;

    void dfs0(int node, int dad = 0)
    {
        w[node] = 1;
        for(auto it : v[node])
            if(it.to != dad && !used[it.to])
            {
                dfs0(it.to, node);
                w[node] += w[it.to];
            }
    }

    pair<int,int> centroid(int node, int dad = 0)
    {
        int act = S - w[node];
        pair<int,int> best = {S, -1};

        for(auto it : v[node])
            if(it.to != dad && !used[it.to])
            {
                best = min(best, centroid(it.to, node));
                act = max(act, w[it.to]);
            }
        best = min(best, {act, node});
        return best;
    }

    ll dfs(int node, int dad = 0)
    {
        ll sum = 0;

        if(dad)
        {
            if(w[dad] == -1) subarb[node] = node;
                else subarb[node] = subarb[dad];
            best[subarb[node]] = max(best[subarb[node]], {c[node], node});
        }

        for(auto it : v[node])
            if(it.to != dad && !used[it.to])
            {
                c[it.to] = c[node] + it.toy;
                sum += it.fromy + dfs(it.to, node);
            }
        return sum;
    }

    void solve2(int node)
    {
        dfs0(node);
        S = w[node];

        node = centroid(node).second;
        c[node] = 0;
        w[node] = -1;

        for(auto it : v[node])
            if(!used[it.to])
                best[it.to] = {-1, -1};

        ll sum = dfs(node);

        vector< pair<ll,int> > now;

        for(auto it : v[node])
            if(!used[it.to])
                now.push_back(best[it.to]);

        if(now.size() >= 2)
        {
            nth_element(now.begin(), now.end() - 2, now.end());

            ll W = sum + now[now.size()-2].first + now[now.size()-1].first;

            if(W > best2)
            {
                best2 = W;
                root = now.back().second;
            }
        }

        if(now.size() >= 1)
        {
            ll W = sum + max_element(now.begin(), now.end())->first;

            if(W > best2)
            {
                best2 = W;
                root = node;
            }
        }

        used[node] = 1;
        for(auto it : v[node])
            if(!used[it.to]) solve2(it.to);
    }
}




pair<ll, int> operator + (pair<ll, int> a, ll b)
{
    a.first += b;
    return a;
}

#define mid ((st+dr)>>1)
#define left_son ((node<<1))
#define right_son ((node<<1)|1)

class SegTree
{
    pair<ll, int> a[Nmax<<2];
    ll lazy[Nmax<<2];

public:
    void update(int node, int st, int dr, int L, int R, int add)
    {
        if(L <= st && dr <= R)
        {
            lazy[node] += add;
            return;
        }

        if(L <= mid) update(left_son, st, mid, L, R, add);
        if(mid < R) update(right_son, mid+1, dr, L, R, add);

        a[node] = max(a[left_son] + lazy[left_son], a[right_son] + lazy[right_son]);
    }

    void build(int node, int st, int dr, ll D[])
    {
        lazy[node] = 0;
        if(st == dr)
        {
            a[node] = {D[st], st};
            return;
        }
        build(left_son, st, mid, D);
        build(right_son, mid+1, dr, D);
        a[node] = max(a[left_son], a[right_son]);
    }

    pair<ll, int> query()
    {
        return a[1] + lazy[1];
    }
};

namespace solve_for_all
{
    int up[Nmax];
    ll up_chain[Nmax];
    int tmp, in[Nmax], out[Nmax], t[Nmax];
    bool used[Nmax];

    ll which[Nmax];
    int ord[Nmax];

    SegTree aint;

    ll dfs(int node, int dad = 0)
    {
        t[node] = dad;
        in[node] = ++tmp;

        ll sum = 0;
        for(auto it : v[node])
            if(it.to != dad)
            {
                up[it.to] = it.toy;
                up_chain[it.to] = up[it.to] + up_chain[node];
                sum += it.fromy + dfs(it.to, node);
            }
        out[node] = tmp;
        return sum;
    }

    void solve(int node)
    {
        memset(used, 0, sizeof(used));
        tmp = 0;
        up_chain[node] = up[node] = 0;

        ll Ans = dfs(node);

        int i;
        for(i=1; i<=n; ++i) ord[in[i]] = i;
        for(i=1; i<=n; ++i) which[i] = up_chain[ord[i]];

        aint.build(1, 1, n, which);
        used[node] = 1;

        for(i=2; i<=n; ++i)
        {
            auto res = aint.query();
            Ans += res.first;
            ans[i] = max(ans[i], Ans);

            int x = ord[res.second];

            while(!used[x])
            {
                aint.update(1, 1, n, in[x], out[x], -up[x]);
                used[x] = 1;
                x = t[x];
            }
        }
    }
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    ll sum = 0;
    int i;

    cin >> n;
    for(i=1; i<n; ++i)
    {
        int x, y, c1, c2;
        cin >> x >> y >> c1 >> c2;
        v[x].push_back({y, c1, c2});
        v[y].push_back({x, c2, c1});
        sum += c1 + c2;
    }

    ans[1] = special_case_for_one :: solve1();
    special_case :: solve2(1);
    solve_for_all :: solve(special_case :: root);

  //  for(i=1; i<=n; ++i)
   //     solve_for_all :: solve(i);

    int q;
    cin >> q;
    while(q--)
    {
        int x;
        cin >> x;
        cout << sum - ans[x] << '\n';
    }

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 17 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44