제출 #884210

#제출 시각아이디문제언어결과실행 시간메모리
884210LucaIlieSprinkler (JOI22_sprinkler)C++17
21 / 100
2376 ms70932 KiB
#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 ) {
      |                     ~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...