oj.uz

Submission #47396

# Submission time Handle Problem Language Result Execution time Memory
47396 2018-05-02T11:07:26 Z daniel_02 Construction of Highway (JOI18_construction) C++17
0 / 100
 1000 ms 55304 KB 
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front

using namespace std;

const int N = 5e5 + 7;
const int inf = 1e9 + 7;

int a[N], pr[N];

struct con
{
    int l, r;
    ll sm;
    con()
    {

        l = r = sm = 0;
    }
}t[N * 7];
int cnt;

void update(int v, int tl, int tr, int pos, int x)
{
    if (tl == tr)
    {
        t[v].sm += x;
    }
    else
    {
        int mid = (tl + tr) >> 1;

        if (mid >= pos)
        {
            if (!t[v].l)
                t[v].l = ++cnt;

            update(t[v].l, tl, mid, pos, x);
        }
        else
        {
            if (!t[v].r)
                t[v].r = ++cnt;

            update(t[v].r, mid + 1, tr, pos, x);
        }
        if (!t[v].l)t[v].l = ++cnt;
        if (!t[v].r)t[v].r = ++cnt;

        t[v].sm = t[t[v].l].sm + t[t[v].r].sm;
    }
}
ll get(int v, int tl, int tr, int l, int r)
{
    if (tl > r || l > tr)return 0LL;

    if (l <= tl && tr <= r)
    {
        return t[v].sm;
    }
    else
    {
        int mid = (tl + tr) >> 1;

        if (!t[v].l)
            t[v].l = ++cnt;
        if (!t[v].r)
            t[v].r = ++cnt;

        return get(t[v].l, tl, mid, l, r) + get(t[v].r, mid + 1, tr, l, r);
    }
}
deque<int>dq;

void dfs(int v)
{
    if (v == 0)
       return;
    dq.pf(a[v]);
    dfs(pr[v]);
}
void conquer(int v)
{
    ll ans = 0;
    dfs(v);

    cnt = 1;
    for (int i = 0; i < dq.size(); i++)
    {
        ans += get(1, 1, inf, dq[i] + 1, inf);
        update(1, 1, inf, dq[i], 1);
    }
    dq.clear();
    memset(t, 0, sizeof(t));
    printf("%lld\n", ans);
}
void upd(int v, int x)
{
    if (v == 0)return;

    a[v] = x;

    upd(pr[v], x);
}
main()
{
    int n;

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i < n; i++)
    {
        int q, w;
        scanf("%d%d", &q, &w);
        if (i == 1)
        {
            puts("0");
            pr[w] = q;
            a[q] = a[w];
            continue;
        }
        conquer(q);
        upd(q, a[w]);
        pr[w] = q;
    }
}

Compilation message

construction.cpp: In function 'void conquer(int)':
construction.cpp:93:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < dq.size(); i++)
                     ~~^~~~~~~~~~~
construction.cpp: At global scope:
construction.cpp:110:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
construction.cpp: In function 'int main()':
construction.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
construction.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &q, &w);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 55160 KB Output is correct
2 Correct 122 ms 55160 KB Output is correct
3 Execution timed out 1039 ms 55304 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 55160 KB Output is correct
2 Correct 122 ms 55160 KB Output is correct
3 Execution timed out 1039 ms 55304 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 55160 KB Output is correct
2 Correct 122 ms 55160 KB Output is correct
3 Execution timed out 1039 ms 55304 KB Time limit exceeded
4 Halted 0 ms 0 KB -