oj.uz

Submission #953042

# Submission time Handle Problem Language Result Execution time Memory
953042 2024-03-25T10:57:25 Z LucaIlie Designated Cities (JOI19_designated_cities) C++17
6 / 100
 1880 ms 1556 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 c;
        return d;
    }
};

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

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 ) {
        lazy[v] = 0;
        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, long long 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 );

        for ( int i = 0; i <= n; i++ )
            sz[i] = parent[i] = depth[i] = heavy[i] = head[i] = leftPos[i] = rightPos[i] = 0;
        ord.clear();
        ord.push_back( 0 );

        dfs( r, 0 );

        curPos = 0;
        decomp( r, 0, r );
    }

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

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

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

ARB arb;

void dfs( 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;

        sumCost += d;
        parentEdgeCost[v] = c;
        arb.updateSubTree( v, c );

        dfs( v, u );
    }
}

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;
    }

    vector<int> perm;
    for ( int r = 1; r <= n; r++ )
        perm.push_back( r );
    random_shuffle( perm.begin(), perm.end() );
    for ( int pas = 0; pas < n && pas < 1500; pas++ ) {
        int r = perm[pas];
        for ( int v = 1; v <= n; v++ )
            isCity[v] = vis[v] = false;

        arb.init( r, n );
        sumCost = 0;
        dfs( r, 0 );
        ans[1] = max( ans[1], sumCost );
        isCity[r] = vis[r] = true;

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

            int v = arb.ord[p.p];
            isCity[v] = true;
            arb.updateVertex( v, -INF );
            while ( !vis[v] ) {
                vis[v] = true;
                arb.updateSubTree( v, -parentEdgeCost[v] );
                v = arb.parent[v];
            }
        }
    }

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

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1857 ms 792 KB Output is correct
14 Correct 1790 ms 1556 KB Output is correct
15 Correct 1768 ms 856 KB Output is correct
16 Correct 1860 ms 860 KB Output is correct
17 Correct 1876 ms 1104 KB Output is correct
18 Correct 1880 ms 860 KB Output is correct
19 Incorrect 1870 ms 860 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Runtime error 1 ms 604 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -