Submission #106114

#	Time	Username	Problem	Language	Result	Execution time	Memory
106114		Alexa2001	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	19 ms	10752 KiB

designated_cities

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")

using namespace std;

const int Nmax = 2e5 + 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
{
    static 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;
    }

    static 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;
    }

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

namespace special_case
{
    int root;
    ll best2 = 0;

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

    static 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];
            }
    }

    static 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;
    }

    static 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;
    }

    static 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;
            }
        }
        else
        if(now.size() >= 1)
        {
            ll W = sum + now[0].first;

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

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




static 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)

namespace SegTree
{
    int n;
    vector<pair<ll, int>> a;
    vector<ll> lazy;

    static void up(int x){
        while(x /= 2)
            a[x] = max(a[2 * x], a[2 * x + 1]) + lazy[x];
    }

    static void add_lazy(int x, int delta){
        a[x].first += delta;
        lazy[x] += delta;
    }

    static void update(int st, int dr, int delta)
    {
        const int st0 = --st, dr0 = --dr;

        for(st += n, dr += n + 1; st < dr; st /= 2, dr /= 2){
            if(st % 2) add_lazy(st++, delta);
            if(dr % 2) add_lazy(--dr, delta);
        }

        up(st0);
        up(dr0);
    }

    static void build(int N, ll *which)
    {
        n = N;

        a.resize(2 * n);
        lazy.resize(n);
        for(int i = 0; i < n; ++i)
            a[i + n] = make_pair(which[i + 1], i + 1);
        for(int i = n - 1; i > 0; --i)
            a[i] = max(a[2 * i], a[2 * i + 1]);
    }

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

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

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

    static 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;
    }

    static 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]];

        SegTree::build(n, which);
        used[node] = 1;

        for(i=2; i<=n; ++i)
        {
            auto res = SegTree::query();
            if(!res.first) break;
            Ans += res.first;
            ans[i] = max(ans[i], Ans);

            int x = ord[res.second];

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

        for(; i<=n; ++i) ans[i] = max(ans[i], Ans);
    }
}


const int sz = 1e6;
char buf[sz+40];

int main()
{
    cin.rdbuf()->pubsetbuf(buf, sz);
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(0);

    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: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44