제출 #884210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884210		LucaIlie	Sprinkler (JOI22_sprinkler)	C++17	21 / 100	2376 ms	70932 KiB

sprinkler

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 9 / 9
• Subtask 3: 0 / 29
• Subtask 4: 12 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17