oj.uz

Submission #106089

# Submission time Handle Problem Language Result Execution time Memory
106089 2019-04-16T13:47:31 Z Alexa2001 Designated Cities (JOI19_designated_cities) C++17
23 / 100
 28 ms 17664 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9060 KB Output is correct
2 Correct 10 ms 9088 KB Output is correct
3 Correct 9 ms 9088 KB Output is correct
4 Correct 9 ms 9088 KB Output is correct
5 Correct 10 ms 9088 KB Output is correct
6 Correct 9 ms 9060 KB Output is correct
7 Correct 11 ms 9088 KB Output is correct
8 Correct 9 ms 9088 KB Output is correct
9 Correct 11 ms 9088 KB Output is correct
10 Correct 10 ms 9088 KB Output is correct
11 Correct 10 ms 9088 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9088 KB Output is correct
2 Runtime error 28 ms 17664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9088 KB Output is correct
2 Runtime error 27 ms 17664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9060 KB Output is correct
2 Correct 10 ms 9088 KB Output is correct
3 Correct 9 ms 9088 KB Output is correct
4 Correct 9 ms 9088 KB Output is correct
5 Correct 10 ms 9088 KB Output is correct
6 Correct 9 ms 9060 KB Output is correct
7 Correct 11 ms 9088 KB Output is correct
8 Correct 9 ms 9088 KB Output is correct
9 Correct 11 ms 9088 KB Output is correct
10 Correct 10 ms 9088 KB Output is correct
11 Correct 10 ms 9088 KB Output is correct
12 Correct 9 ms 9156 KB Output is correct
13 Correct 18 ms 9344 KB Output is correct
14 Correct 19 ms 9600 KB Output is correct
15 Correct 16 ms 9344 KB Output is correct
16 Correct 16 ms 9344 KB Output is correct
17 Correct 20 ms 9440 KB Output is correct
18 Correct 21 ms 9472 KB Output is correct
19 Correct 17 ms 9444 KB Output is correct
20 Correct 16 ms 9344 KB Output is correct
21 Correct 15 ms 9472 KB Output is correct
22 Correct 21 ms 9336 KB Output is correct
23 Correct 16 ms 9344 KB Output is correct
24 Correct 18 ms 9472 KB Output is correct
25 Correct 17 ms 9600 KB Output is correct
26 Correct 16 ms 9472 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9088 KB Output is correct
2 Runtime error 28 ms 17664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9060 KB Output is correct
2 Correct 10 ms 9088 KB Output is correct
3 Correct 9 ms 9088 KB Output is correct
4 Correct 9 ms 9088 KB Output is correct
5 Correct 10 ms 9088 KB Output is correct
6 Correct 9 ms 9060 KB Output is correct
7 Correct 11 ms 9088 KB Output is correct
8 Correct 9 ms 9088 KB Output is correct
9 Correct 11 ms 9088 KB Output is correct
10 Correct 10 ms 9088 KB Output is correct
11 Correct 10 ms 9088 KB Output is correct
12 Correct 10 ms 9088 KB Output is correct
13 Runtime error 28 ms 17664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -