oj.uz

Submission #104067

# Submission time Handle Problem Language Result Execution time Memory
104067 2019-04-03T21:25:54 Z bogdan10bos Designated Cities (JOI19_designated_cities) C++14
16 / 100
 804 ms 86212 KB 
/// <3 azilE
#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> p3i;

const int NMAX = 2e5;
const int LGMAX = 18;
const ll oo = 1LL << 60;

int N;
ll sol[NMAX + 5], dwn[NMAX + 5];
vector<p3i> edg[NMAX + 5];

void swapNodes(int x, int y)
{
    if(x == y)  return;
    swap(edg[x], edg[y]);
    for(int i = 1; i <= N; i++)
        for(auto &edge: edg[i])
        {
            if(edge.first == x) edge.first = y;
            else if(edge.first == y)    edge.first = x;
        }
}

void DFS(int nod, int fth = 0)
{
    dwn[nod] = 0;
    for(auto &edge: edg[nod])
        if(edge.first != fth)
        {
            DFS(edge.first, nod);
            dwn[nod] += dwn[edge.first] + edge.second.first;
        }
}

void DFS2(int nod, int fth = 0, ll cost = 0)
{
    ll mycost = cost;
    ll sumdwn = dwn[nod];
    sol[1] = min(sol[1], mycost + sumdwn);
    for(auto &edge: edg[nod])
        if(edge.first != fth)
            DFS2(edge.first, nod, mycost + sumdwn - dwn[edge.first] - edge.second.first + edge.second.second);
}

namespace Ezial
{
    ll dp[NMAX + 5];
    int who[NMAX + 5];
    ll sol2;
    int newroot;
    pii gods;

    ll value[NMAX + 5];
    int f[NMAX + 5], done[NMAX + 5];
    int E, eul[NMAX + 5], h[NMAX + 5], lg2[2 * NMAX + 5];
    int rmq[LGMAX + 1][2 * NMAX + 5];

    int I, ord[NMAX + 5], itv[NMAX + 5][2];

    class SegmentTree
    {
    public:
        int N, sti, dri, idd;
        ll val, ans;
        int id[4 * NMAX + 5];
        ll aint[4 * NMAX + 5], add[4 * NMAX + 5];

        void B(int nod, int st, int dr)
        {
            aint[nod] = add[nod] = 0;
            if(st == dr)
            {
                id[nod] = ord[st];
                return;
            }

            int mij = st + (dr - st) / 2;
            B(nod * 2, st, mij);
            B(nod * 2 + 1, mij + 1, dr);

            id[nod] = id[nod * 2];
        }

        void build(int _N) { N = _N; B(1, 1, N); }

        void lazy(int nod)
        {
            aint[nod * 2] += add[nod];
            aint[nod * 2 + 1] += add[nod];
            add[nod] = 0;
        }

        void U(int nod, int st, int dr)
        {
            if(sti <= st && dr <= dri)
            {
                aint[nod] += val;
                return;
            }

            int mij = st + (dr - st) / 2;
            lazy(nod);

            if(sti <= mij)  U(nod * 2, st, mij);
            if(mij < dri)   U(nod * 2 + 1, mij + 1, dr);

            if(aint[nod * 2] > aint[nod * 2 + 1])
            {
                aint[nod] = aint[nod * 2];
                id[nod] = id[nod * 2];
            }
            else
            {
                aint[nod] = aint[nod * 2 + 1];
                id[nod] = id[nod * 2 + 1];
            }
        }

        void update(int st, int dr, ll _val)
        {
            sti = st, dri = dr, val = _val;
            U(1, 1, N);
        }

        int query()
        {
            return id[1];
        }
    }aint;

    int minh(int a, int b)
    {
        if(h[a] < h[b]) return a;
        return b;
    }

    int LCA(int a, int b)
    {
        int pa = eul[a], pb = eul[b];
        if(pa > pb) swap(pa, pb);
        int lg = lg2[pb - pa + 1];
        return minh(rmq[lg][pa], rmq[lg][pb - (1 << lg) + 1]);
    }

    void DFS2(int nod, int fth = 0, ll cost = 0)
    {
        if((int)edg[nod].size() == 1)
        {
            who[nod] = nod;
            dp[nod] = 0;
            return;
        }

        ll min1 = oo, min2 = oo;
        int who1 = -1, who2 = -1;
        for(auto &edge: edg[nod])
            if(edge.first != fth)
            {
                DFS2(edge.first, nod, cost + dwn[nod] - dwn[edge.first] - edge.second.first + edge.second.second);

                ll nowcost = -dwn[edge.first] - edge.second.first + dp[edge.first];
                if(nowcost < min1)
                {
                    min2 = min1, who2 = who1;
                    min1 = nowcost, who1 = who[edge.first];
                }
                else if(nowcost < min2)
                    min2 = nowcost, who2 = who[edge.first];
            }

        dp[nod] = dwn[nod] + min1, who[nod] = who1;

        if(who2 != -1)
        {
            ll nowcost = cost + dwn[nod] + min1 + min2;
            if(nowcost < sol2)
            {
                sol2 = nowcost;
                newroot = nod;
                gods = {who1, who2};
            }
        }
    }

    void DFS3(int nod, int fth = 0)
    {
        f[nod] = fth;
        h[nod] = 1 + h[fth];
        rmq[0][++E] = nod;
        eul[nod] = E;
        itv[nod][0] = ++I;
        ord[I] = nod;
        for(auto &edge: edg[nod])
            if(edge.first != fth)
            {
                DFS3(edge.first, nod);
                value[edge.first] = edge.second.first;
                rmq[0][++E] = nod;
            }
        itv[nod][1] = I;
    }

    void goup(int nod)
    {
        done[nod] = 1;
        if(nod == 1)     return;
        goup(f[nod]);
    }

    void solve()
    {
        int root = 1;
        for(int i = 1; i <= N; i++)
            if((int)edg[i].size() > 1)
            {
                root = i;
                break;
            }
        swapNodes(1, root);

        DFS(1);
        sol2 = oo;
        DFS2(1);

        swapNodes(1, newroot);
        sol[2] = sol2;

        DFS3(1);
        for(int i = 2; i <= E; i++) lg2[i] = lg2[i >> 1] + 1;
        for(int i = 1; (1 << i) <= E; i++)
            for(int j = 1; j + (1 << i) - 1 <= E; j++)
                rmq[i][j] = minh(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);

        goup(gods.first);
        goup(gods.second);

        aint.build(N);
        for(int i = 1; i <= N; i++)
            if(!done[i])    aint.update(itv[i][0], itv[i][1], value[i]);

        int cnt = 2;
        ll ans = sol2;
        while(1)
        {
            int nod = aint.query();
            if(done[nod])   return;

            while(!done[nod])
            {
                ans -= value[nod];
                aint.update(itv[nod][0], itv[nod][1], -value[nod]);
                done[nod] = 1;
                nod = f[nod];
            }

            cnt++;
            sol[cnt] = ans;
        }
    }
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d", &N);
    for(int i = 1; i < N; i++)
    {
        int x, y, a, b;
        scanf("%d%d%d%d", &x, &y, &a, &b);
        edg[x].push_back({y, {a, b}});
        edg[y].push_back({x, {b, a}});
    }

    DFS(1);
    sol[1] = oo;
    DFS2(1);

    if(N > 2)   Ezial::solve();

    int Q;
    scanf("%d", &Q);
    for(int q = 1; q <= Q; q++)
    {
        int id;
        scanf("%d", &id);
        printf("%lld\n", sol[id]);
    }

    return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:277:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
designated_cities.cpp:281:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &x, &y, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:293:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
designated_cities.cpp:297:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &id);
         ~~~~~^~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Incorrect 6 ms 5120 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 688 ms 70456 KB Output is correct
3 Correct 633 ms 83800 KB Output is correct
4 Correct 712 ms 69752 KB Output is correct
5 Correct 701 ms 70820 KB Output is correct
6 Correct 746 ms 72952 KB Output is correct
7 Correct 682 ms 71180 KB Output is correct
8 Correct 719 ms 84432 KB Output is correct
9 Correct 571 ms 72244 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 804 ms 70556 KB Output is correct
3 Correct 644 ms 86212 KB Output is correct
4 Correct 791 ms 69612 KB Output is correct
5 Correct 767 ms 70792 KB Output is correct
6 Correct 735 ms 73080 KB Output is correct
7 Correct 660 ms 71712 KB Output is correct
8 Correct 685 ms 79864 KB Output is correct
9 Correct 605 ms 71972 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Incorrect 6 ms 5120 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 688 ms 70456 KB Output is correct
3 Correct 633 ms 83800 KB Output is correct
4 Correct 712 ms 69752 KB Output is correct
5 Correct 701 ms 70820 KB Output is correct
6 Correct 746 ms 72952 KB Output is correct
7 Correct 682 ms 71180 KB Output is correct
8 Correct 719 ms 84432 KB Output is correct
9 Correct 571 ms 72244 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 804 ms 70556 KB Output is correct
12 Correct 644 ms 86212 KB Output is correct
13 Correct 791 ms 69612 KB Output is correct
14 Correct 767 ms 70792 KB Output is correct
15 Correct 735 ms 73080 KB Output is correct
16 Correct 660 ms 71712 KB Output is correct
17 Correct 685 ms 79864 KB Output is correct
18 Correct 605 ms 71972 KB Output is correct
19 Correct 6 ms 5120 KB Output is correct
20 Incorrect 703 ms 70396 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Incorrect 6 ms 5120 KB Output isn't correct
9 Halted 0 ms 0 KB -