Submission #837039

#	Time	Username	Problem	Language	Result	Execution time	Memory
837039		LucaIlie	Two Currencies (JOI23_currencies)	C++17	100 / 100	2364 ms	73804 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v;

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

struct checkpoint {
    int e, c;
};

struct query {
    int u, v, x;
    long long y;
};

struct answer {
    long long sum;
    int cnt;
};

struct AIB {
    vector<long long> aib;

    void init( int n ) {
        aib.resize( n + 1 );
        for ( int i = 0; i < aib.size(); i++ )
            aib[i] = 0;
    }

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

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

struct updateBS {
    int v, val;
};

struct queryBS {
    int u, v, q;
};

const int MAX_N = 2e5;
const int MAX_M = 2e5;
const int MAX_Q = 2e5;
const int MAX_LOG_N = 17;

int n, m;
int leftBS[MAX_Q], rightBS[MAX_Q], ans[MAX_Q];
int depth[MAX_N + 1], leftPos[MAX_N + 1], rightPos[MAX_N + 1], parent[MAX_LOG_N + 1][MAX_N + 1];
edge edges[MAX_N];
checkpoint checkpoints[MAX_M + 1];
query queries[MAX_Q];
vector<updateBS> updatesBS[MAX_M + 2];
vector<queryBS> queriesBS[MAX_M + 2];
vector<int> adj[MAX_N + 1];
AIB sum, cnt;

int timee = 0;
void dfs( int u, int p ) {
    parent[0][u] = p;
    depth[u] = depth[p] + 1;
    leftPos[u] = ++timee;
    for ( int e: adj[u] ) {
        int v = edges[e].other( u );
        if ( v == p )
            continue;

        dfs( v, u );

        if ( u != edges[e].u )
            swap( edges[e].u, edges[e].v );
    }
    rightPos[u] = timee;
}

int lca( int u, int v ) {
    if ( depth[u] < depth[v] )
        swap( u, v );

    for ( int l = MAX_LOG_N; l >= 0; l-- ) {
        if ( depth[parent[l][u]] >= depth[v] )
            u = parent[l][u];
    }

    if ( u == v )
        return u;

    for ( int l = MAX_LOG_N; l >= 0; l-- ) {
        if ( parent[l][u] != parent[l][v] ) {
            u = parent[l][u];
            v = parent[l][v];
        }
    }

    return parent[0][u];
}

void initArb() {
    sum.init( n );
    cnt.init( n );
    for ( int i = 1; i <= m; i++ ) {
        int u = edges[checkpoints[i].e].v;
        cnt.update( leftPos[u], 1 );
        cnt.update( rightPos[u] + 1, -1 );
    }
}

void updateArb( int u, int val ) {
    sum.update( leftPos[u], val );
    sum.update( rightPos[u] + 1, -val );
    cnt.update( leftPos[u], -1 );
    cnt.update( rightPos[u] + 1, 1 );
}

answer queryArb( int u, int v ) {
    int l = lca( u, v );
    return { sum.query( leftPos[u] ) + sum.query( leftPos[v] ) - 2 * sum.query( leftPos[l] ),
             cnt.query( leftPos[u] ) + cnt.query( leftPos[v] ) - 2 * cnt.query( leftPos[l] )
    };
}

int main() {
    cin.tie( NULL );
    cout.tie( NULL );
    ios_base::sync_with_stdio( false );

    int q;

    cin >> n >> m >> q;
    for ( int i = 1; i < n; i++ )
        cin >> edges[i].u >> edges[i].v;
    for ( int i = 1; i <= m; i++ )
        cin >> checkpoints[i].e >> checkpoints[i].c;
    sort( checkpoints + 1, checkpoints + 1 + m, []( checkpoint a, checkpoint b ) {
        return a.c < b.c;
    } );
    for ( int i = 0; i < q; i++ ) {
        cin >> queries[i].u >> queries[i].v >> queries[i].x >> queries[i].y;
        leftBS[i] = 0;
        rightBS[i] = m + 2;
    }


    for ( int i = 1; i < n; i++ ) {
        adj[edges[i].u].push_back( i );
        adj[edges[i].v].push_back( i );
    }
    dfs( 1, 0 );
    for ( int l = 1; l <= MAX_LOG_N; l++ ) {
        for ( int u = 1; u <= n; u++ )
            parent[l][u] = parent[l - 1][parent[l - 1][u]];
    }

    for ( int pas = 0; pas < MAX_LOG_N + 1; pas++ ) {
        for ( int i = 0; i <= m + 1; i++ ) {
            updatesBS[i].clear();
            queriesBS[i].clear();
        }
        for ( int i = 1; i <= m; i++ )
            updatesBS[i].push_back( { edges[checkpoints[i].e].v, checkpoints[i].c } );
        for ( int i = 0; i < q; i++ )
            queriesBS[(leftBS[i] + rightBS[i]) / 2].push_back( { queries[i].u, queries[i].v, i } );

        initArb();
        for ( int i = 0; i <= m + 1; i++ ) {
            for ( updateBS u: updatesBS[i] )
                updateArb( u.v, u.val );
            for ( queryBS qq: queriesBS[i] ) {
                answer x = queryArb( qq.u, qq.v );
                if ( x.sum > queries[qq.q].y )
                    rightBS[qq.q] = i;
                else
                    leftBS[qq.q] = i;
                ans[qq.q] = x.cnt;
            }
        }
    }

    for ( int i = 0; i < q; i++ )
        cout << (ans[i] <= queries[i].x ? queries[i].x - ans[i] : -1) << "\n";

    return 0;
}

Compilation message (stderr)

currencies.cpp: In member function 'void AIB::init(int)':
currencies.cpp:32:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for ( int i = 0; i < aib.size(); i++ )
      |                          ~~^~~~~~~~~~~~
currencies.cpp: In member function 'void AIB::update(int, int)':
currencies.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while ( i < aib.size() ) {
      |                 ~~^~~~~~~~~~~~
currencies.cpp: In function 'answer queryArb(int, int)':
currencies.cpp:137:64: warning: narrowing conversion of '((cnt.AIB::query(leftPos[u]) + cnt.AIB::query(leftPos[v])) - (2 * cnt.AIB::query(leftPos[l])))' from 'long long int' to 'int' [-Wnarrowing]
  137 |              cnt.query( leftPos[u] ) + cnt.query( leftPos[v] ) - 2 * cnt.query( leftPos[l] )
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32