oj.uz

Submission #821675

# Submission time Handle Problem Language Result Execution time Memory
821675 2023-08-11T12:55:33 Z LucaIlie Construction of Highway (JOI18_construction) C++17
0 / 100
 11 ms 14036 KB 
#include <bits/stdc++.h>

using namespace std;

const int UNDEF = 0;
const int MAX_N = 1e5;
int c[MAX_N], parent[MAX_N], ord[MAX_N];
vector<int> edges[MAX_N];

struct vr {
    int val, rep;
};

struct info {
    vector<vr> v;

    info operator + ( info &a ) {
        vector<vr> ans = v;
        for ( vr x: a.v ) {
            if ( !ans.empty() && ans.back().val == x.val )
                ans[ans.size() - 1].rep += x.rep;
            else
                ans.push_back( x );
        }

        return { ans };
    }
};


struct SegTree {

    info segTree[4 * MAX_N];
    int lazy[4 * MAX_N];

    void init() {
        for ( int v = 0; v < 4 * MAX_N; v++ )
            lazy[v] = UNDEF;
    }

    void propag( int v, int l, int r ) {
        if ( lazy[v] == UNDEF )
            return;

        segTree[v].v.clear();
        segTree[v].v.push_back( { lazy[v], r - l + 1 } );
        if ( l != r )
            lazy[v * 2 + 1] = lazy[v * 2 + 2] = lazy[v];
        lazy[v] = UNDEF;
    }

    void update( int v, int l, int r, int lu, int ru, int x ) {
        //if ( v == 0 )
            //printf( "%d %d %d\n", lu, ru, x );
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            lazy[v] = x;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
        segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
    }

    info query( int v, int l, int r, int lq, int rq ) {
        propag( v, l, r );

        if ( l > rq || r < lq )
            return {};

        if ( lq <= l && r <= rq )
            return segTree[v];

        int mid = (l + r) / 2;
        info a = query( v * 2 + 1, l, mid, lq, rq );
        info b = query( v * 2 + 2, mid + 1, r, lq, rq );
        return a + b;
    }
};

struct HPD {
    int n, curPos;
    int sz[MAX_N], depth[MAX_N], heavy[MAX_N], head[MAX_N], leftPos[MAX_N], rightPos[MAX_N];
    SegTree aint;

    void dfs( int u, int p ) {
        int maxSz = -1;

        parent[u] = p;
        depth[u] = depth[p] + 1;
        sz[u] = 1;
        heavy[u] = UNDEF;
        for ( int v: edges[u] ) {
            if ( v == p )
                continue;
            dfs( v, u );
            sz[u] += sz[v];
            if ( sz[v] > maxSz ) {
                maxSz = sz[v];
                heavy[u] = v;
            }
        }
    }

    void decomp( int u, int p, int h ) {
        head[u] = h;
        leftPos[u] = ++curPos;
        if ( heavy[u] != UNDEF )
            decomp( heavy[u], u, h );
        for ( int v: edges[u] ) {
            if ( v == p || v == heavy[u] )
                continue;
            decomp( v, u, v );
        }
        rightPos[u] = curPos;
    }

    void init( int _n ) {
        n = _n;
        aint.init();
        parent[1] = UNDEF;
        dfs( 1, UNDEF );
        decomp( 1, UNDEF, 1 );
    }


    void updatePath( int u, int x ) {
        while ( u != 0 ) {
            aint.update( 0, 1, n, leftPos[head[u]], leftPos[u], x );
            u = parent[head[u]];
        }
    }

    info queryPath( int u ) {
        info ans;

        while ( u != 0 ) {
            info a = aint.query( 0, 1, n, leftPos[head[u]], leftPos[u] );
            ans = a + ans;
            u = parent[head[u]];
        }

        return ans;
    }
};

struct AIB {
    int aib[MAX_N + 1];

    void update( int i, int x ) {
        while ( i <= MAX_N ) {
            aib[i] += x;
            i += (i & -i);
        }
    }

    int query( int i ) {
        int sum = 0;
        while ( i > 0 ) {
            sum += aib[i];
            i -= (i & -i);
        }
        return sum;
    }
};

AIB aib;
HPD arb;
map<int, int> normal;

int main() {
    int n;

    cin >> n;
    for ( int u = 1; u <= n; u++ )
        cin >> c[u], normal[c[u]] = 1;
    int val = 0;
    for ( auto x: normal )
        normal[x.first] = ++val;
    for ( int u = 1; u <= n; u++ )
        c[u] = normal[c[u]];

    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        parent[v] = u;
        edges[u].push_back( v );
        ord[i] = v;
    }

    arb.init( n );
    arb.updatePath( 1, c[1] );
    for ( int i = 0; i < n - 1; i++ ) {
        int u = ord[i];
        vector<vr> v = arb.queryPath( parent[u] ).v;

        int sum = 0;
        long long ans = 0;
        for ( vr x: v ) {
            ans += (long long)x.rep * (sum - aib.query( x.val - 1 ));
            aib.update( x.val, x.rep );
            sum += x.rep;
        }
        for ( vr x: v )
            aib.update( x.val, -x.rep );
        cout << ans << "\n";

        arb.updatePath( u, c[u] );
    }

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13600 KB Output is correct
2 Correct 7 ms 13652 KB Output is correct
3 Correct 6 ms 13652 KB Output is correct
4 Correct 8 ms 13768 KB Output is correct
5 Correct 9 ms 13864 KB Output is correct
6 Correct 9 ms 13908 KB Output is correct
7 Correct 9 ms 13864 KB Output is correct
8 Correct 7 ms 13908 KB Output is correct
9 Correct 7 ms 13908 KB Output is correct
10 Correct 8 ms 13908 KB Output is correct
11 Correct 8 ms 14000 KB Output is correct
12 Correct 7 ms 14036 KB Output is correct
13 Correct 8 ms 14036 KB Output is correct
14 Correct 8 ms 13920 KB Output is correct
15 Correct 10 ms 13864 KB Output is correct
16 Correct 10 ms 13868 KB Output is correct
17 Correct 11 ms 13972 KB Output is correct
18 Correct 11 ms 13908 KB Output is correct
19 Correct 8 ms 13908 KB Output is correct
20 Correct 8 ms 13868 KB Output is correct
21 Correct 8 ms 13892 KB Output is correct
22 Incorrect 9 ms 13736 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13600 KB Output is correct
2 Correct 7 ms 13652 KB Output is correct
3 Correct 6 ms 13652 KB Output is correct
4 Correct 8 ms 13768 KB Output is correct
5 Correct 9 ms 13864 KB Output is correct
6 Correct 9 ms 13908 KB Output is correct
7 Correct 9 ms 13864 KB Output is correct
8 Correct 7 ms 13908 KB Output is correct
9 Correct 7 ms 13908 KB Output is correct
10 Correct 8 ms 13908 KB Output is correct
11 Correct 8 ms 14000 KB Output is correct
12 Correct 7 ms 14036 KB Output is correct
13 Correct 8 ms 14036 KB Output is correct
14 Correct 8 ms 13920 KB Output is correct
15 Correct 10 ms 13864 KB Output is correct
16 Correct 10 ms 13868 KB Output is correct
17 Correct 11 ms 13972 KB Output is correct
18 Correct 11 ms 13908 KB Output is correct
19 Correct 8 ms 13908 KB Output is correct
20 Correct 8 ms 13868 KB Output is correct
21 Correct 8 ms 13892 KB Output is correct
22 Incorrect 9 ms 13736 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13600 KB Output is correct
2 Correct 7 ms 13652 KB Output is correct
3 Correct 6 ms 13652 KB Output is correct
4 Correct 8 ms 13768 KB Output is correct
5 Correct 9 ms 13864 KB Output is correct
6 Correct 9 ms 13908 KB Output is correct
7 Correct 9 ms 13864 KB Output is correct
8 Correct 7 ms 13908 KB Output is correct
9 Correct 7 ms 13908 KB Output is correct
10 Correct 8 ms 13908 KB Output is correct
11 Correct 8 ms 14000 KB Output is correct
12 Correct 7 ms 14036 KB Output is correct
13 Correct 8 ms 14036 KB Output is correct
14 Correct 8 ms 13920 KB Output is correct
15 Correct 10 ms 13864 KB Output is correct
16 Correct 10 ms 13868 KB Output is correct
17 Correct 11 ms 13972 KB Output is correct
18 Correct 11 ms 13908 KB Output is correct
19 Correct 8 ms 13908 KB Output is correct
20 Correct 8 ms 13868 KB Output is correct
21 Correct 8 ms 13892 KB Output is correct
22 Incorrect 9 ms 13736 KB Output isn't correct
23 Halted 0 ms 0 KB -