Submission #857075

#	Time	Username	Problem	Language	Result	Execution time	Memory
857075		Tudy006	Traffickers (RMI18_traffickers)	C++14	100 / 100	1801 ms	12816 KiB

traffickers

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 3e4;
const int LMAX = 20;
const int QMAX = 5e4;

vector <int> edges[NMAX + 1];

int aib[LMAX + 1][2 * NMAX + 1];

struct node {
    int start;
    int finish;
    int jump;
    int p;
    int d;
} info[NMAX + 1];

void update( int l, int c, int x ) {
    for ( int i = l; i <= LMAX; i += ( i & -i ) ) {
        for ( int j = c; j <= 2 * NMAX; j += ( j & -j ) ) {
            aib[i][j] += x;
        }
    }
}

int sum( int l, int c ) {
    int s = 0;
    for ( int i = l; i > 0; i -= ( i & -i ) ) {
        for ( int j = c; j > 0; j -= ( j & -j ) ) {
            s += aib[i][j];
        }
    }
    return s;
}

int t = 0;
void dfs( int node, int p = 1 ) {
    info[node].p = p;
    info[node].d = info[p].d + 1;
    info[node].start = ++t;
    for ( auto vec : edges[node] ) {
        if ( vec == p ) continue;
        dfs( vec, node );
        if ( info[p].d - info[info[p].jump].d == info[info[p].jump].d - info[info[info[p].jump].jump].d ) {
            info[vec].jump = info[info[p].jump].jump;
        } else {
            info[vec].jump = p;
        }
    }
    info[node].finish = ++t;
}

bool isAncestor( int u, int v ) {
    return ( info[u].start <= info[v].start && info[v].finish <= info[u].finish );
}
int LCA( int u, int v ) {
    while ( !isAncestor( u, v ) ) {
        if ( !isAncestor( info[u].jump, v ) ) {
             u = info[u].jump;
        } else {
            u = info[u].p;
        }
    }
    return u;
}
int dist( int u, int v, int lca ) {
    return info[u].d + info[v].d - 2 * info[lca].d + 1;
}
struct query {
    int tip;
    int u;
    int v;
    int t1;
    int t2;
    int lca;
};

int sumPath( int u, int v, int l, int lca ) {
    int s = sum( l, info[u].start ) + sum( l, info[v].start ) - sum( l, info[lca].start );
    if ( lca == 1 ) {
        return s;
    }
    return s - sum( l, info[info[lca].p].start );
}
long long queryPath( int u, int v, int l, int lca, int t ) {
    return (long long)(t / l) * sumPath( u, v, l, lca ) + sumPath( u, v, t % l, lca );
}
void updatePath( int u, int v, int add, int lca ) {
    int d = dist( u, v, lca ), tLca = dist( u, lca, lca );
    for ( int t = 1; u != lca; u = info[u].p ) {
        update( t, info[u].start, +add );
        update( t, info[u].finish, -add );
        t ++;
    }
    for ( int t = d; v != lca; v = info[v].p ) {
        update( t, info[v].start, +add );
        update( t, info[v].finish, -add );
        t --;
    }
    update( tLca, info[lca].start, +add );
    update( tLca, info[lca].finish, -add );
}

long long answer[QMAX + 1];

int main() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );
    cout.tie( NULL );
//    ifstream cin( "Traffickers.in");
//    ofstream cout( "traffickers.out" );
    int n, k, q;
    cin >> n;
    for ( int i = 1, a, b; i < n; i ++ ) {
        cin >> a >> b;
        edges[a].push_back( b );
        edges[b].push_back( a );
    }
    info[1].jump = 1;
    dfs( 1 );
    vector <query> v;
    cin >> k;
    for ( int i = 1, a, b; i <= k; i ++ ) {
        cin >> a >> b;
        v.push_back( (query){1, a, b, 0, 0, LCA(a, b)} );
    }
    cin >> q;
    for ( int i = 1, a, b, tip; i <= q; i ++ ) {
        cin >> tip >> a >> b;
        if ( tip == 3 ) {
            int t1, t2;
            cin >> t1 >> t2;
            v.push_back( (query){tip, a, b, t1, t2, LCA(a, b)} );
        } else {
            v.push_back( (query){tip, a, b, 0, 0, LCA(a, b)} );
        }
    }

    int cnt;
    for ( int l = 1; l <= LMAX; l ++ ) {
        for ( int i = 1; i <= LMAX; i ++ ) {
            for ( int j = 1; j <= 2 * NMAX; j ++ ) {
                aib[i][j] = 0;
            }
        }
        cnt = 0;
        for ( auto p : v ) {
            if ( p.tip == 3 ) {
                answer[++cnt] += queryPath( p.u, p.v, l, p.lca, p.t2 + 1 ) - queryPath( p.u, p.v, l, p.lca, p.t1 );
            } else {
                if ( dist( p.u, p.v, p.lca ) == l ) {
                    updatePath( p.u, p.v, (p.tip == 1 ? 1 : -1), p.lca );
                }
            }
        }
    }
    for ( int i = 1; i <= cnt; i ++ ) {
        cout << answer[i] << '\n';
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40