oj.uz

Submission #953001

# Submission time Handle Problem Language Result Execution time Memory
953001 2024-03-25T10:00:27 Z LucaIlie Designated Cities (JOI19_designated_cities) C++17
16 / 100
 668 ms 96036 KB 
#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v, c, d;

    int other( int p ) {
        return u ^ v ^ p;
    }

    int cost( int p ) {
        if ( p == u )
            return d;
        return c;
    }
};

const int MAX_N = 2e5;
const long long INF = 1e15;
bool isCity[MAX_N + 1], vis[MAX_N + 1];
long long cost[MAX_N + 1], ans[MAX_N + 1];
long long sumCost;
edge edges[MAX_N];
vector<int> adj[MAX_N + 1];

void dfs1( int u, int p ) {
    for ( int e: adj[u] ) {
        int v = edges[e].other( u ), c = edges[e].cost( u ), d = (edges[e].c ^ edges[e].d ^ c);
        if ( v == p )
            continue;

        cost[v] = cost[u] - c + d;
        sumCost += c;

        dfs1( v, u );
    }
}

void dfs2( int u, int p ) {
    for ( int e: adj[u] ) {
        int v = edges[e].other( u ), c = edges[e].cost( u ), d = (edges[e].c ^ edges[e].d ^ c);
        if ( v == p )
            continue;

        cost[v] = cost[u] + d;
        sumCost += c;

        dfs2( v, u );
    }
}

struct info {
    int p;
    long long x;

    bool operator < ( const info &y ) const {
        return x < y.x;
    }
};

struct SegTree {
    info segTree[4 * MAX_N];
    long long lazy[4 * MAX_N];

    void init( int v, int l, int r ) {
        if ( l == r ) {
            segTree[v] = { l, 0 };
            return;
        }

        int mid = (l + r) / 2;
        init( v * 2 + 1, l, mid );
        init( v * 2 + 2, mid + 1, r );
        segTree[v] = max( segTree[v * 2 + 1], segTree[v * 2 + 2] );
    }

    void propag( int v, int l, int r ) {
        segTree[v].x += lazy[v];
        if ( l != r ) {
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
        }
        lazy[v] = 0;
    }

    void update( int v, int l, int r, int lu, int ru, int 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] = max( 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 { 0, -INF };

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

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

struct ARB {
    const int undef = 0;
    int n, curPos;
    int sz[MAX_N + 1], parent[MAX_N + 1], depth[MAX_N + 1], heavy[MAX_N + 1], head[MAX_N + 1], leftPos[MAX_N + 1], rightPos[MAX_N + 1];
    vector<int> ord;
    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 e: adj[u] ) {
            int v = edges[e].other( 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;
        ord.push_back( u );
        if ( heavy[u] != undef )
            decomp( heavy[u], u, h );
        for ( int e: adj[u] ) {
            int v = edges[e].other( u );
            if ( v == p || v == heavy[u] )
                continue;
            decomp( v, u, v );
        }
        rightPos[u] = curPos;
    }

    void init( int r, int _n ) {
        n = _n;
        aint.init( 0, 1, n );
        dfs( r, 0 );
        ord.clear();
        ord.push_back( 0 );
        decomp( r, 0, r );
    }

    void updateSubTree( int u, int x ) {
        aint.update( 0, 1, n, leftPos[u], rightPos[u], x );
    }

    info querySubTree( int u ) {
        return aint.query( 0, 1, n, leftPos[u], rightPos[u] );
    }
};

ARB arb;

int main() {
    int n;
    long long sumTotal = 0;

    cin >> n;
    for ( int e = 0; e < n - 1; e++ ) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        edges[e] = { u, v, c, d };
        adj[u].push_back( e );
        adj[v].push_back( e );
        sumTotal += c + d;
    }

    sumCost = 0;
    cost[1] = 0;
    dfs1( 1, 0 );
    int r = 1;
    for ( int v = 2; v <= n; v++ ) {
        if ( cost[v] > cost[r] )
            r = v;
    }
    ans[1] = sumCost + cost[r];

    sumCost = 0;
    cost[1] = 0;
    dfs2( 1, 0 );
    r = 1;
    for ( int v = 2; v <= n; v++ ) {
        if ( cost[v] > cost[r] )
            r = v;
    }
    isCity[r] = true;

    sumCost = 0;
    dfs2( r, 0 );

    arb.init( r, n );
    for ( int e = 0; e < n - 1; e++ ) {
        int u = edges[e].u, v = edges[e].v, c = edges[e].c, d = edges[e].d;
        if ( arb.depth[u] > arb.depth[v] ) {
            swap( u, v );
            swap( c, d );
        }
        arb.updateSubTree( v, c );
    }

    for ( int i = 2; i <= n; i++ ) {
        info p = arb.querySubTree( r );
        sumCost += p.x;
        ans[i] = sumCost;

        int v = arb.ord[p.p];
        isCity[v] = true;
        while ( !vis[v] ) {
            vis[v] = true;
            v = arb.parent[v];
        }
    }

    int q;
    cin >> q;
    while ( q-- ) {
        int x;
        cin >> x;
        cout << sumTotal - ans[x] << "\n";
    }

    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Incorrect 2 ms 6748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 579 ms 42988 KB Output is correct
3 Correct 625 ms 96036 KB Output is correct
4 Correct 466 ms 42488 KB Output is correct
5 Correct 513 ms 42228 KB Output is correct
6 Correct 619 ms 48664 KB Output is correct
7 Correct 436 ms 43244 KB Output is correct
8 Correct 668 ms 92152 KB Output is correct
9 Correct 328 ms 42864 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 603 ms 42292 KB Output is correct
3 Correct 639 ms 95072 KB Output is correct
4 Correct 515 ms 41516 KB Output is correct
5 Correct 542 ms 42200 KB Output is correct
6 Correct 509 ms 51148 KB Output is correct
7 Correct 368 ms 42644 KB Output is correct
8 Correct 588 ms 75100 KB Output is correct
9 Correct 308 ms 43448 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Incorrect 2 ms 6748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 579 ms 42988 KB Output is correct
3 Correct 625 ms 96036 KB Output is correct
4 Correct 466 ms 42488 KB Output is correct
5 Correct 513 ms 42228 KB Output is correct
6 Correct 619 ms 48664 KB Output is correct
7 Correct 436 ms 43244 KB Output is correct
8 Correct 668 ms 92152 KB Output is correct
9 Correct 328 ms 42864 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 603 ms 42292 KB Output is correct
12 Correct 639 ms 95072 KB Output is correct
13 Correct 515 ms 41516 KB Output is correct
14 Correct 542 ms 42200 KB Output is correct
15 Correct 509 ms 51148 KB Output is correct
16 Correct 368 ms 42644 KB Output is correct
17 Correct 588 ms 75100 KB Output is correct
18 Correct 308 ms 43448 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Incorrect 533 ms 46004 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Incorrect 2 ms 6748 KB Output isn't correct
3 Halted 0 ms 0 KB -