Submission #884363

#	Time	Username	Problem	Language	Result	Execution time	Memory
884363		LucaIlie	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	3316 ms	209832 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

struct update {
    int v, g, d, x, t;
};

struct query {
    int v, g, t;
};

const int MAX_N = 2e5;
const int MAX_AIB = MAX_N + 1;
const int MAX_Q = 4e5;
int n, l;
bool vis[MAX_N + 1];
int h[MAX_N + 1], ans[MAX_Q], sz[MAX_N + 1], depth[MAX_N + 1];
vector<int> edges[MAX_N + 1];
vector<update> updatesV[MAX_N + 1], updates;
vector<query> queriesV[MAX_N + 1], queries;

struct AIB {
    unordered_map<int, int> aib[MAX_AIB + 1];
    vector<int> changes;
    int size1, size2;

    void init( int _size1, int _size2 ) {
        size1 = _size1, size2 = _size2;
        for ( int p: changes )
            aib[p].clear();
        changes.clear();
    }

    void update( int i, int j, int x ) {
        while ( i <= size1 ) {
            int p = j;
            while ( p <= size2 ) {
                if ( aib[i].find( p ) == aib[i].end() )
                    aib[i][p] = 1;
                aib[i][p] = (long long)aib[i][p] * x % l;
                p += (p & -p);
            }
            changes.push_back( i );
            i += (i & -i);
        }
    }

    int query( int i, int j ) {
        int ans = 1;
        while ( i > 0 ) {
            int p = j;
            while ( p > 0 ) {
                if ( aib[i].find( p ) != aib[i].end() )
                    ans = (long long)ans * aib[i][p] % l;
                p -= (p & -p);
            }
            i -= (i & -i);
        }
        return ans;
    }
} aibNI, aibII;

int lgPut( int x, int n ) {
    if ( n == 0 )
        return 1;

    int p = lgPut( x, n / 2 );
    p = (long long)p * p % l;
    if ( n % 2 == 1 )
        p = (long long)p * x % l;

    return p;
}

int invmod( int x ) {
    return lgPut( x, l - 2 );
}

void calcSizes( int u, int p ) {
    sz[u] = 1;
    for ( int v: edges[u] ) {
        if ( v == p || vis[v] )
            continue;
        calcSizes( v, u );
        sz[u] += sz[v];
    }
}

int cen, totSz;
void findCentroid( int u, int p ) {
    int maxSize = 0;
    for ( int v: edges[u] ) {
        if ( v == p || vis[v] )
            continue;
        findCentroid( v, u );
        maxSize = max( maxSize, sz[v] );
    }
    maxSize = max( maxSize, totSz - sz[u] );

    if ( maxSize <= totSz / 2 )
        cen = u;
}

void dfs( int u, int p, int g ) {
    depth[u] = depth[p] + 1;
    for ( update upd: updatesV[u] ) {
        upd.g = g;
        updates.push_back( upd );
    }
    for ( query qry: queriesV[u] ) {
        qry.g = g;
        queries.push_back( qry );
    }
    for ( int v: edges[u] ) {
        if ( v == p || vis[v] )
            continue;
        dfs( v, u, g );
    }
}

void decomp( int r ) {
    calcSizes( r, 0 );
    totSz = sz[r];
    findCentroid( r, 0 );
    int c = cen;

    int g = 1;
    updates.clear();
    queries.clear();
    depth[c] = 0;
    for ( update upd: updatesV[c] ) {
        upd.g = g;
        updates.push_back( upd );
    }
    for ( query qry: queriesV[c] ) {
        qry.g = g;
        queries.push_back( qry );
    }
    for ( int v: edges[c] ) {
        if ( vis[v] )
            continue;
        ++g;
        dfs( v, c, g );
    }
    sort( updates.begin(), updates.end(), []( update x, update y ) {
        return x.t < y.t;
    } );
    sort( queries.begin(), queries.end(), []( query x, query y ) {
        return x.t < y.t;
    } );

    aibNI.init( g, n + 1 );
    aibII.init( g, n + 1 );

    int pu = 0;
    for ( query q: queries ) {
        while ( pu < updates.size() && updates[pu].t < q.t ) {
            if ( updates[pu].d >= depth[updates[pu].v] ) {
                aibNI.update( updates[pu].g, (n + 1) - min( n, (updates[pu].d - depth[updates[pu].v]) ), updates[pu].x );
                aibII.update( (g + 1) - updates[pu].g, (n + 1) - min( n, (updates[pu].d - depth[updates[pu].v]) ), updates[pu].x );
            }
            pu++;
        }
        if ( q.g == 1 )
            ans[q.t] = (long long)ans[q.t] * aibNI.query( g, (n + 1) - depth[q.v] ) % l;
        else
            ans[q.t] = (long long)ans[q.t] * aibNI.query( q.g - 1, (n + 1) - depth[q.v] ) % l * aibII.query( (g + 1) - (q.g + 1), (n + 1) - depth[q.v] ) % l;
    }

    vis[c] = true;
    for ( int v: edges[c] ) {
        if ( !vis[v] )
            decomp( v );
    }
}


int main() {
    cin >> n >> l;
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back( v );
        edges[v].push_back( u );
    }
    for ( int v = 1; v <= n; v++ )
        cin >> h[v];
    int q;
    cin >> q;
    for ( int i = 0; i < q; i++ ) {
        int t;
        cin >> t;
        if ( t == 1 ) {
            int v, d, x;
            cin >> v >> d >> x;
            updatesV[v].push_back( { v, 0, d, x, i } );
            ans[i] = -1;
        } else {
            int v;
            cin >> v;
            queriesV[v].push_back( { v, 0, i } );
            ans[i] = h[v];
        }
    }

    decomp( 1 );

    for ( int i = 0; i < q; i++ ) {
        if ( ans[i] != -1 )
            cout << ans[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

sprinkler.cpp: In function 'void decomp(int)':
sprinkler.cpp:158:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<update>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         while ( pu < updates.size() && updates[pu].t < q.t ) {
      |                 ~~~^~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17