Submission #104069

#	Time	Username	Problem	Language	Result	Execution time	Memory
104069		bogdan10bos	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	921 ms	55412 KiB

designated_cities

/// <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 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];
            add[nod * 2] += add[nod];
            aint[nod * 2 + 1] += add[nod];
            add[nod * 2 + 1] += add[nod];
            add[nod] = 0;
        }

        void U(int nod, int st, int dr)
        {
            if(sti <= st && dr <= dri)
            {
                aint[nod] += val;
                add[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;

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

        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 (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:256:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
designated_cities.cpp:260: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:272:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
designated_cities.cpp:276:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &id);
         ~~~~~^~~~~~~~~~~

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