oj.uz

Submission #106099

# Submission time Handle Problem Language Result Execution time Memory
106099 2019-04-16T14:03:35 Z Alexa2001 Designated Cities (JOI19_designated_cities) C++17
23 / 100
 2000 ms 62712 KB 
#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
{
    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;

    static pair<ll, int> best[Nmax];
    static int w[Nmax], subarb[Nmax];
    static ll c[Nmax];
    static bool used[Nmax];
    static 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;
            }
        }
        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);
    }
}




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
{
    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 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();
            if(!res.first) break;
            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];
            }
        }

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

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

    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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17792 KB Output is correct
2 Correct 20 ms 17792 KB Output is correct
3 Correct 18 ms 17920 KB Output is correct
4 Correct 19 ms 17792 KB Output is correct
5 Correct 17 ms 17920 KB Output is correct
6 Correct 16 ms 17792 KB Output is correct
7 Correct 18 ms 17792 KB Output is correct
8 Correct 20 ms 17892 KB Output is correct
9 Correct 17 ms 17792 KB Output is correct
10 Correct 20 ms 17792 KB Output is correct
11 Correct 18 ms 17920 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17792 KB Output is correct
2 Correct 1490 ms 45216 KB Output is correct
3 Correct 1775 ms 61124 KB Output is correct
4 Correct 1311 ms 45432 KB Output is correct
5 Correct 868 ms 45692 KB Output is correct
6 Correct 1617 ms 47736 KB Output is correct
7 Correct 695 ms 46220 KB Output is correct
8 Execution timed out 2036 ms 60156 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17792 KB Output is correct
2 Correct 1531 ms 45356 KB Output is correct
3 Execution timed out 2048 ms 62712 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17792 KB Output is correct
2 Correct 20 ms 17792 KB Output is correct
3 Correct 18 ms 17920 KB Output is correct
4 Correct 19 ms 17792 KB Output is correct
5 Correct 17 ms 17920 KB Output is correct
6 Correct 16 ms 17792 KB Output is correct
7 Correct 18 ms 17792 KB Output is correct
8 Correct 20 ms 17892 KB Output is correct
9 Correct 17 ms 17792 KB Output is correct
10 Correct 20 ms 17792 KB Output is correct
11 Correct 18 ms 17920 KB Output is correct
12 Correct 19 ms 17920 KB Output is correct
13 Correct 22 ms 18176 KB Output is correct
14 Correct 21 ms 18176 KB Output is correct
15 Correct 25 ms 18168 KB Output is correct
16 Correct 22 ms 18176 KB Output is correct
17 Correct 24 ms 18176 KB Output is correct
18 Correct 27 ms 18176 KB Output is correct
19 Correct 27 ms 18176 KB Output is correct
20 Correct 22 ms 18176 KB Output is correct
21 Correct 22 ms 18168 KB Output is correct
22 Correct 21 ms 18168 KB Output is correct
23 Correct 23 ms 18148 KB Output is correct
24 Correct 24 ms 18176 KB Output is correct
25 Correct 24 ms 18560 KB Output is correct
26 Correct 21 ms 18176 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17792 KB Output is correct
2 Correct 1490 ms 45216 KB Output is correct
3 Correct 1775 ms 61124 KB Output is correct
4 Correct 1311 ms 45432 KB Output is correct
5 Correct 868 ms 45692 KB Output is correct
6 Correct 1617 ms 47736 KB Output is correct
7 Correct 695 ms 46220 KB Output is correct
8 Execution timed out 2036 ms 60156 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17792 KB Output is correct
2 Correct 20 ms 17792 KB Output is correct
3 Correct 18 ms 17920 KB Output is correct
4 Correct 19 ms 17792 KB Output is correct
5 Correct 17 ms 17920 KB Output is correct
6 Correct 16 ms 17792 KB Output is correct
7 Correct 18 ms 17792 KB Output is correct
8 Correct 20 ms 17892 KB Output is correct
9 Correct 17 ms 17792 KB Output is correct
10 Correct 20 ms 17792 KB Output is correct
11 Correct 18 ms 17920 KB Output is correct
12 Correct 17 ms 17792 KB Output is correct
13 Correct 1490 ms 45216 KB Output is correct
14 Correct 1775 ms 61124 KB Output is correct
15 Correct 1311 ms 45432 KB Output is correct
16 Correct 868 ms 45692 KB Output is correct
17 Correct 1617 ms 47736 KB Output is correct
18 Correct 695 ms 46220 KB Output is correct
19 Execution timed out 2036 ms 60156 KB Time limit exceeded
20 Halted 0 ms 0 KB -