oj.uz

Submission #241903

# Submission time Handle Problem Language Result Execution time Memory
241903 2020-06-26T09:38:04 Z osaaateiasavtnl Construction of Highway (JOI18_construction) C++17
0 / 100
 19 ms 6076 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 1e5+7, LG = 20;
int n, a[N], par[N];
ii d[N];
vector <int> tree[N];

int to[N][LG], h[N];
int l[N], r[N], ptr = -1;
void dfs(int u) {
    to[u][0] = par[u];
    for (int i = 1; i < LG; ++i)
        to[u][i] = to[to[u][i - 1]][i - 1];

    l[u] = ++ptr;    

    for (int v : tree[u]) {
        h[v] = h[u]+1;
        dfs(v);        
    }   

    r[u] = ptr;
}   

int mx[N << 2];
void upd(int v, int tl, int tr, int i, int x) {
    mx[v] = x;
    if (tl == tr) 
        return;
    int tm = (tl + tr) >> 1;
    if (i <= tm)
        upd(v * 2 + 1, tl, tm, i, x);
    else
        upd(v * 2 + 2, tm + 1, tr, i, x);
}
int get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl)
        return -1;
    if (l <= tl && tr <= r)
        return mx[v];
    int tm = (tl + tr) >> 1;
    return max(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm + 1, tr, l, r));
}

int val[N];

int last(int u) {
    return get(0, 0, N, l[u], r[u]);
}

int getval(int u, int ls) {
    if (ls == -1)
        return a[u];
    else
        return val[ls];
}

struct Fen {
int f[N];
void add(int i, int x) {
    for (; i < N; i |= i + 1) 
        f[i] += x;
}   
void clear(int i) {
    for (; i < N; i |= i + 1)
        f[i] = 0;
}   
int get(int i) {
    int ans = 0;
    for (; i >= 0; i &= i + 1, --i) ans += f[i];
    return ans;
}   
int get(int l, int r) {
    return get(r) - get(l - 1);
}   
} f;

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    for (int i = 0; i < (N << 2); ++i)
        mx[i] = -1;

    cin >> n;
    vector <int> c;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        c.app(a[i]);
    }   
    sort(all(c));
    c.resize(unique(all(c)) - c.begin());
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(all(c), a[i]) - c.begin();

    for (int t = 0; t < n - 1; ++t) {
        int u, v;
        cin >> u >> v;
        tree[u].app(v);
        par[v] = u;
        d[t] = mp(u,v);
    }   

    par[1] = 1;
    dfs(1);

    int sum = 0;

    for (int t = 0; t < n - 1; ++t) {
        int u, v;
        tie(u, v) = d[t];

        vector <ii> path;
        while (1) {
            int up = u;
            for (int i = LG - 1; i >= 0; --i)
                if (last(to[up][i]) == last(u))
                    up = to[up][i];
            path.app(mp(getval(u, last(u)), h[u] - h[up] + 1));
            if (up == 1)
                break;
            else
                u = par[up];
        }   

        val[t] = a[v];
        upd(0, 0, N, l[v], t);

        sum += path.size();
        if (sum > 4 * n)
            exit(1);

        int ans = 0;
        for (auto e : path) {
            ans += f.get(e.f - 1) * e.s;
            f.add(e.f, e.s);
        }   
        cout << ans << endl;
        for (auto e : path)
            f.clear(e.f);
    }   
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5888 KB Output is correct
2 Correct 7 ms 5888 KB Output is correct
3 Correct 9 ms 5888 KB Output is correct
4 Correct 12 ms 6016 KB Output is correct
5 Correct 17 ms 6016 KB Output is correct
6 Correct 16 ms 6016 KB Output is correct
7 Correct 17 ms 6076 KB Output is correct
8 Correct 11 ms 6016 KB Output is correct
9 Correct 11 ms 6016 KB Output is correct
10 Correct 11 ms 6016 KB Output is correct
11 Correct 12 ms 6016 KB Output is correct
12 Correct 13 ms 6016 KB Output is correct
13 Correct 12 ms 6016 KB Output is correct
14 Correct 12 ms 6016 KB Output is correct
15 Runtime error 19 ms 6016 KB Execution failed because the return code was nonzero
16 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5888 KB Output is correct
2 Correct 7 ms 5888 KB Output is correct
3 Correct 9 ms 5888 KB Output is correct
4 Correct 12 ms 6016 KB Output is correct
5 Correct 17 ms 6016 KB Output is correct
6 Correct 16 ms 6016 KB Output is correct
7 Correct 17 ms 6076 KB Output is correct
8 Correct 11 ms 6016 KB Output is correct
9 Correct 11 ms 6016 KB Output is correct
10 Correct 11 ms 6016 KB Output is correct
11 Correct 12 ms 6016 KB Output is correct
12 Correct 13 ms 6016 KB Output is correct
13 Correct 12 ms 6016 KB Output is correct
14 Correct 12 ms 6016 KB Output is correct
15 Runtime error 19 ms 6016 KB Execution failed because the return code was nonzero
16 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5888 KB Output is correct
2 Correct 7 ms 5888 KB Output is correct
3 Correct 9 ms 5888 KB Output is correct
4 Correct 12 ms 6016 KB Output is correct
5 Correct 17 ms 6016 KB Output is correct
6 Correct 16 ms 6016 KB Output is correct
7 Correct 17 ms 6076 KB Output is correct
8 Correct 11 ms 6016 KB Output is correct
9 Correct 11 ms 6016 KB Output is correct
10 Correct 11 ms 6016 KB Output is correct
11 Correct 12 ms 6016 KB Output is correct
12 Correct 13 ms 6016 KB Output is correct
13 Correct 12 ms 6016 KB Output is correct
14 Correct 12 ms 6016 KB Output is correct
15 Runtime error 19 ms 6016 KB Execution failed because the return code was nonzero
16 Halted 0 ms 0 KB -