oj.uz

Submission #884198

# Submission time Handle Problem Language Result Execution time Memory
884198 2023-12-06T17:54:30 Z LucaIlie Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 63604 KB 
#include <bits/stdc++.h>

using namespace std;

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

struct query {
    int v, 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 {
    int aib[MAX_AIB + 1];
    vector<int> changes;

    void init() {
        for ( int i = 0; i <= MAX_AIB; i++ )
            aib[i] = 1;
    }

    void clear() {
        for ( int p: changes )
            aib[p] = 1;
        changes.clear();
    }

    void update( int i, int x ) {
        while ( i <= MAX_AIB ) {
            aib[i] = (long long)aib[i] * x % l;
            changes.push_back( i );
            i += (i & -i);
        }
    }
    void updateInv( int i, int x ) {
        update( MAX_AIB - i, x );
    }

    int query( int i ) {
        int ans = 1;
        while ( i > 0 ) {
            ans = (long long)ans * aib[i] % l;
            i -= (i & -i);
        }
        return ans;
    }
    int queryInv( int i ) {
        return query( MAX_AIB - i );
    }
} aib;

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 ) {
    depth[u] = depth[p] + 1;
    for ( update upd: updatesV[u] )
        updates.push_back( upd );
    for ( query qry: queriesV[u] )
        queries.push_back( qry );
    for ( int v: edges[u] ) {
        if ( v == p || vis[v] )
            continue;
        dfs( v, u );
    }
}

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

    updates.clear();
    queries.clear();
    depth[c] = 0;
    for ( update upd: updatesV[c] )
        updates.push_back( upd );
    for ( query qry: queriesV[c] )
        queries.push_back( qry );
    for ( int v: edges[c] ) {
        if ( vis[v] )
            continue;
        dfs( v, c );
    }
    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;
    } );
    aib.clear();
    int pu = 0;
    for ( query q: queries ) {
        while ( pu < updates.size() && updates[pu].t < q.t ) {
            if ( updates[pu].d >= depth[updates[pu].v] )
                aib.updateInv( updates[pu].d - depth[updates[pu].v], updates[pu].x );
            pu++;
        }
        ans[q.t] = ((long long)ans[q.t] * aib.queryInv( depth[q.v] )) % l;
    }

    for ( int v: edges[c] ) {
        if ( vis[v] )
            continue;
        updates.clear();
        queries.clear();
        dfs( v, r );

        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;
        } );
        aib.clear();
        int pu = 0;
        for ( query q: queries ) {
            while ( pu < updates.size() && updates[pu].t < q.t ) {
                if ( updates[pu].d >= depth[updates[pu].v] )
                    aib.updateInv( updates[pu].d - depth[updates[pu].v], invmod( updates[pu].x ) );
                pu++;
            }
            ans[q.t] = ((long long)ans[q.t] * aib.queryInv( 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, d, x, i } );
            ans[i] = -1;
        } else {
            int v;
            cin >> v;
            queriesV[v].push_back( { v, i } );
            ans[i] = h[v];
        }
    }

    aib.init();
    decomp( 1 );

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

    return 0;
}

Compilation message

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 3 ms 19088 KB Output is correct
4 Incorrect 46 ms 19288 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Execution timed out 4082 ms 47408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Execution timed out 4082 ms 47408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Execution timed out 4040 ms 63604 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19444 KB Output is correct
2 Execution timed out 4035 ms 59324 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 3 ms 19088 KB Output is correct
4 Incorrect 46 ms 19288 KB Output isn't correct
5 Halted 0 ms 0 KB -