oj.uz

Submission #44264

# Submission time Handle Problem Language Result Execution time Memory
44264 2018-03-31T05:08:24 Z RayaBurong25_1 Construction of Highway (JOI18_construction) C++17
0 / 100
 2 ms 432 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Incorrect 2 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Incorrect 2 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Incorrect 2 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -