Submission #97514

#	Time	Username	Problem	Language	Result	Execution time	Memory
97514		bogdan10bos	Construction of Highway (JOI18_construction)	C++14	100 / 100	731 ms	27024 KiB

construction

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef pair<int, int> pii;
typedef long long LL;

const int NMAX = 1e5 + 5;

int N, K;
int v[NMAX], sz[NMAX], chn[NMAX], f[NMAX], pos[NMAX];
vector<int> nodes[NMAX], edg[NMAX];
vector<pii> edges, blk, aux, blocks[NMAX];

class Normalizer
{
public:
    map<int, int> mp;
    vector<int> ord;

    void add(int x)
    {
        if(mp.count(x)) return;
        mp[x]; ord.push_back(x);
    }

    int get(int x) { return mp[x]; }

    void normalize()
    {
        sort(begin(ord), end(ord));
        for(int i = 0; i < ord.size(); i++)
            mp[ ord[i] ] = i + 1;
    }
}nrm;

class BinaryIndexedTree
{
public:
    vector<int> aib;

    void init(int N)
    {
        aib.resize(N + 5);
    }

    void U(int pos, int val)
    {
        for(; pos < aib.size(); pos += (pos & (-pos)))
            aib[pos] += val;
    }

    int Q(int pos)
    {
        int ans = 0;
        for(; pos > 0; pos -= (pos & (-pos)))
            ans += aib[pos];
        return ans;
    }
}aib;

void DFS(int nod, int fth = 0)
{
    sz[nod] = 1;
    f[nod] = fth;
    for(auto &nxt: edg[nod])
    {
        DFS(nxt, nod);
        sz[nod] += sz[nxt];
        if(sz[nxt] > sz[ edg[nod][0] ]) swap(nxt, edg[nod][0]);
    }

    if(edg[nod].empty())
        chn[nod] = ++K;
    else
        chn[nod] = chn[ edg[nod][0] ];

    nodes[ chn[nod] ].push_back(nod);
    pos[nod] = int(nodes[ chn[nod] ].size()) - 1;
}

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++) scanf("%d", &v[i]), nrm.add(v[i]);
    nrm.normalize();
    for(int i = 1; i <= N; i++) v[i] = nrm.get(v[i]);
    for(int i = 1; i < N; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        edg[x].push_back(y);
        edges.push_back({x, y});
    }

    DFS(1);

    aib.init(N);
    blocks[ chn[1] ].push_back({v[1], 1});
    for(auto &e: edges)
    {
        int x = e.first, y = e.second;

        int p = pos[x], c = chn[x];
        blk.clear();
        while(1)
        {
            int rem = int(nodes[c].size()) - p;
            aux.clear();
            while(rem)
            {
                if(blocks[c].back().second > rem)
                {
                    aux.push_back({blocks[c].back().first, rem});
                    blocks[c][ int(blocks[c].size()) - 1 ].second -= rem;
                    break;
                }
                rem -= blocks[c].back().second;
                aux.push_back(blocks[c].back());
                blocks[c].pop_back();
            }
            reverse(aux.begin(), aux.end());
            for(auto &x: aux)   blk.push_back(x);

            int cnt = int(nodes[c].size() - p);
            if(chn[y] == c) cnt++;
            blocks[c].push_back({v[y], cnt});

            if(c == chn[1]) break;
            int nod = f[ nodes[c].back() ];
            c = chn[nod], p = pos[nod];
        }
        if(chn[x] != chn[y])    blocks[ chn[y] ].push_back({v[y], 1});

        LL ans = 0LL;
        for(auto &b: blk)
        {
            ans += 1LL * b.second * aib.Q(b.first - 1);
            aib.U(b.first, b.second);
        }
        printf("%lld\n", ans);
        for(auto &b: blk)
            aib.U(b.first, -b.second);
    }

    return 0;
}

Compilation message (stderr)

construction.cpp: In member function 'void Normalizer::normalize()':
construction.cpp:34:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < ord.size(); i++)
                        ~~^~~~~~~~~~~~
construction.cpp: In member function 'void BinaryIndexedTree::U(int, int)':
construction.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pos < aib.size(); pos += (pos & (-pos)))
               ~~~~^~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
construction.cpp:92:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%d", &v[i]), nrm.add(v[i]);
                                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
construction.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84