oj.uz

Submission #884210

# Submission time Handle Problem Language Result Execution time Memory
884210 2023-12-06T18:19:02 Z LucaIlie Sprinkler (JOI22_sprinkler) C++17
21 / 100
 2376 ms 70932 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, 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], 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 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 18912 KB Output is correct
4 Incorrect 8 ms 19032 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 1718 ms 42344 KB Output is correct
3 Correct 1516 ms 46264 KB Output is correct
4 Correct 2118 ms 54512 KB Output is correct
5 Correct 1597 ms 43784 KB Output is correct
6 Correct 1265 ms 43708 KB Output is correct
7 Correct 1160 ms 42696 KB Output is correct
8 Correct 657 ms 44248 KB Output is correct
9 Correct 2227 ms 64356 KB Output is correct
10 Correct 1935 ms 70932 KB Output is correct
11 Correct 1668 ms 49692 KB Output is correct
12 Correct 1500 ms 56500 KB Output is correct
13 Correct 591 ms 59572 KB Output is correct
14 Correct 735 ms 56740 KB Output is correct
15 Correct 776 ms 54220 KB Output is correct
16 Correct 861 ms 56300 KB Output is correct
17 Correct 928 ms 55744 KB Output is correct
18 Correct 4 ms 19036 KB Output is correct
19 Correct 4 ms 19036 KB Output is correct
20 Correct 4 ms 19036 KB Output is correct
21 Correct 6 ms 19036 KB Output is correct
22 Correct 5 ms 19124 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 1718 ms 42344 KB Output is correct
3 Correct 1516 ms 46264 KB Output is correct
4 Correct 2118 ms 54512 KB Output is correct
5 Correct 1597 ms 43784 KB Output is correct
6 Correct 1265 ms 43708 KB Output is correct
7 Correct 1160 ms 42696 KB Output is correct
8 Correct 657 ms 44248 KB Output is correct
9 Correct 2227 ms 64356 KB Output is correct
10 Correct 1935 ms 70932 KB Output is correct
11 Correct 1668 ms 49692 KB Output is correct
12 Correct 1500 ms 56500 KB Output is correct
13 Correct 591 ms 59572 KB Output is correct
14 Correct 735 ms 56740 KB Output is correct
15 Correct 776 ms 54220 KB Output is correct
16 Correct 861 ms 56300 KB Output is correct
17 Correct 928 ms 55744 KB Output is correct
18 Correct 4 ms 19036 KB Output is correct
19 Correct 4 ms 19036 KB Output is correct
20 Correct 4 ms 19036 KB Output is correct
21 Correct 6 ms 19036 KB Output is correct
22 Correct 5 ms 19124 KB Output is correct
23 Correct 4 ms 19032 KB Output is correct
24 Incorrect 1740 ms 49572 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19288 KB Output is correct
2 Correct 2263 ms 54052 KB Output is correct
3 Correct 2177 ms 56696 KB Output is correct
4 Correct 2173 ms 53656 KB Output is correct
5 Correct 1759 ms 42288 KB Output is correct
6 Correct 1564 ms 45464 KB Output is correct
7 Correct 1359 ms 55732 KB Output is correct
8 Correct 613 ms 57284 KB Output is correct
9 Correct 2225 ms 57220 KB Output is correct
10 Correct 2114 ms 68276 KB Output is correct
11 Correct 1725 ms 47104 KB Output is correct
12 Correct 1905 ms 55484 KB Output is correct
13 Correct 1646 ms 54680 KB Output is correct
14 Correct 1697 ms 56880 KB Output is correct
15 Correct 4 ms 19288 KB Output is correct
16 Correct 4 ms 19036 KB Output is correct
17 Correct 4 ms 18904 KB Output is correct
18 Correct 4 ms 19036 KB Output is correct
19 Correct 5 ms 18888 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Incorrect 2376 ms 51956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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