Submission #44264

#	Time	Username	Problem	Language	Result	Execution time	Memory
44264		RayaBurong25_1	Construction of Highway (JOI18_construction)	C++17	0 / 100	2 ms	432 KiB

construction

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
int C[100005];
int Cnew[100005];
int Pa[100005];
int Ch[100005];
int PaC[100005];
long long num;
int findRoot(int u)
{
    num = 1;
    while (Pa[u] != 0)
    {
        u = Pa[u];
        num++;
    }
    return u;
}
void cut(int v, int u)
{
    // printf("cut %d %d\n", v, u);
    PaC[v] = u;
    Pa[v] = 0;
}
void link(int v, int u)
{
    int r = C[v], uu, vv;
    while (u != 0)
    {
        // printf("link %d %d\n", v, u);
        Pa[v] = u;
        cut(Ch[u], u);
        uu = Ch[u];
        Ch[u] = v;
        vv = findRoot(u);
        Cnew[uu] = Cnew[vv];
        v = vv;
        u = PaC[v];
    }
    Cnew[v] = r;
}
long long Inv;
int Fen[100005];
int N;
void update(int pos, int v)
{
    for (; pos > 0; pos -= pos&-pos)
        Fen[pos] += v;
}
int query(int pos)
{
    int r = 0;
    for (; pos <= N; pos += pos&-pos)
        r += Fen[pos];
    return r;
}
std::queue<std::pair<int, int> > V;
void findInv(int u)
{
    // printf("findInv %d\n", u);
    int uu = findRoot(u);
    long long r = num;
    if (PaC[uu] == 0)
    {
        update(Cnew[uu], num);
        V.push({Cnew[uu], num});
        return;
    }
    findInv(PaC[uu]);
    Inv += r*query(Cnew[uu] + 1);
    update(Cnew[uu], num);
    V.push({Cnew[uu], num});
}
std::vector<int> S;
int main()
{
    scanf("%d", &N);
    int i;
    for (i = 1; i <= N; i++)
    {
        scanf("%d", &C[i]);
        S.push_back(C[i]);
    }
    std::sort(S.begin(), S.end());
    for (i = 1; i <= N; i++)
        C[i] = std::lower_bound(S.begin(), S.end(), C[i]) - S.begin() + 1;
    int u, v;
    for (i = 1; i < N; i++)
    {
        scanf("%d %d", &u, &v);
        Inv = 0;
        findInv(u);
        printf("%lld\n", Inv);
        while (!V.empty())
        {
            update(V.front().first, -V.front().second);
            V.pop();
        }
        link(v, u);
    }
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
construction.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &C[i]);
         ~~~~~^~~~~~~~~~~~~
construction.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

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