|
|
Don't forget about long long int! #include <bits/stdc++.h> using namespace std; const int MOD = 1e9+7, BLOCK = 320; int n, m, a[100001], p[100001], idx[100001], order[100001], lb[100001], rb[100001]; // lb and rb are indexed by bfs order, not vertex bool mark[100001]; vector<int> g[100001]; struct coolsqrt { // sqrt decomposition int f[100001], t[100001]; void init() { for(int i = 1; i <= n; i++) f[i] = a[order[i]]; } void update(int l, int r, int v) { for(int i = l; i % BLOCK; i++) { f[i] = (f[i]+v)%MOD; if(i == r) return; } int block = l/BLOCK + 1; while(block < r/BLOCK) t[block++] += v, t[block] %= MOD; for(int i = BLOCK*(r/BLOCK); i <= r; i++) f[i] = (f[i]+v)%MOD; } int query(int i) { return (f[i] + t[i/BLOCK])%MOD; } void putin() { for(int i = 1; i <= n; i++) cout << query(i) << ' '; cout << endl; } } coolsqrt; int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1,u,v; i < n; i++) { cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } queue<int> q; q.push(1); for(int i = 1, u = q.front(); i <= n; i++, q.pop(), u = q.front()) { mark[u] = true; idx[u] = i; order[i] = u; for(int v: g[u]) if(!mark[v]) q.push(v), p[v] = u; } assert(q.empty()); for(int i = 1; i <= n; i++) if(p[order[i]]) { if(!lb[p[order[i]]]) lb[p[order[i]]] = i; rb[p[order[i]]] = i; } coolsqrt.init(); cin >> m; int inst,v; while(m--) { cin >> inst >> v; if(inst == 1) { coolsqrt.update(idx[p[v]], idx[p[v]], coolsqrt.query(idx[v])); coolsqrt.update(lb[v], rb[v], coolsqrt.query(idx[v])); // coolsqrt.putin(); } else { cout << coolsqrt.query(idx[v]) << endl; } } // for(int i = 1; i <= n; i++) cout << order[i] << ' '; // cout << endl; // for(int i = 1; i <= n; i++) cout << lb[i] << ' ' << rb[i] << endl; } Edited by author 01.09.2016 20:03 Edited by author 01.09.2016 20:03 Why Runtime Error? #include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { unsigned short n, m; scanf("%hu", &n); vector <unsigned long long> bytes(n); vector <vector<unsigned short> > red(n); for(unsigned short i=0;i<n;i++) scanf("%llu", &bytes[i]); for(unsigned short i=1;i<n;i++) { unsigned short x, y; scanf("%hu %hu", &x, &y); red[x-1].push_back(y); red[y-1].push_back(x); } if(n>1) { for(unsigned short i=0;i<red.size();i++) sort(red[i].begin(), red[i].end()); for(unsigned short i=0;i<red.size();i++) { for(unsigned short j=0;j<red[i].size()-1;j++) { if(red[i][j]==red[i][j+1]) { for(unsigned short pos=j+1;pos<red[i].size()-1;pos++) red[i][pos] = red[i][pos+1]; red[i].pop_back(); } } } } scanf("%hu", &m); for(int i=0;i<m;i++) { unsigned short v, t; scanf("%hu %hu", &t, &v); if(t==1) { for(unsigned j=0;j<red[v-1].size();j++) bytes[red[v-1][j]-1] += bytes[v-1]; } if(t==2) printf("%llu\n", bytes[v-1]%1000000007); } } Input: 7 1 1 1 1 1 1 1 1 2 1 3 1 4 1 5 2 6 2 7 9 1 1 1 1 1 1 1 1 1 1 1 6 2 2 1 2 2 7 output: 7 8 I used segment tree, but got wa on testcase 6 Yes, the output is correct. If you get WA on test #8, don't forget about mod = 1000000007 :) Hello everyone. I always receive time limit on Test №21. Could you give any hints? Maybe this task requires special data structure (I try to represent tree as list of edges or adjacency list) or there is interesting algorythm? Thanks for reading. Not update connected vertexes for vertexes with amount of connections more than Sqrt(N). In this case sum for vertex will be current sum + delta for connected vertexes with size more than Sqrt(N). I have the same problem with TLE #21 and I can't understand your hint: what's that 'delta', how can I track/calculate it? I realize that the bottleneck is in vertices with high amount of linked edges but I can't understand how to avoid them - I still need update all vertices, otherwise I loose data for next steps. yes, you're right about data structure. I used binary indexed tree to solve the problem. Overall complexity is O(n + m * logn). So, you actually preprocess data in O(n) time and for each query you spent O(logn) time, which perfectly fits time constraints of the problem Кт-т упрлс тк услв псть в чм прблм В пршлм гд бл прфсср "Е.Бен", в этм "ЗБС". Нцнзрн брнь. нжн длг крть, чтб т рскрть - вбщ н дгдлс... Edited by author 26.10.2014 14:08 збс же придумал автор?! ЗБС!) |
|
|