|
|
Show all threads Hide all threads Show all messages Hide all messages | if you have wa 9 | Михаил | 2030. Awesome Backup System | 28 Jun 2019 16:41 | 1 | Don't forget about long long int! | What is test case 21 about? | Schwinn | 2030. Awesome Backup System | 1 Sep 2016 20:02 | 1 | #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 | Runtime Error (access violation) #17 | Majin Boo | 2030. Awesome Backup System | 1 Dec 2015 02:10 | 1 | 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); } } | Is the output to this testcase correct? | Pinku Deb Nath | 2030. Awesome Backup System | 30 Nov 2015 00:11 | 2 | 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. | Little hint for test #8 | ImgJ | 2030. Awesome Backup System | 13 Apr 2015 23:51 | 1 | If you get WA on test #8, don't forget about mod = 1000000007 :) | Time limit | Snowball_TverSU | 2030. Awesome Backup System | 15 Jan 2015 16:33 | 6 | 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 | збс | Birne Ageev | 2030. Awesome Backup System | 12 Nov 2014 20:05 | 5 | збс Birne Ageev 25 Oct 2014 13:27 Re: збс Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 26 Oct 2014 00:48 Re: збс Birne Ageev 26 Oct 2014 10:11 В пршлм гд бл прфсср "Е.Бен", в этм "ЗБС". Нцнзрн брнь. Re: збс Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 26 Oct 2014 14:08 нжн длг крть, чтб т рскрть - вбщ н дгдлс... Edited by author 26.10.2014 14:08 Re: збс Oxxxymiron 12 Nov 2014 20:05 збс же придумал автор?! ЗБС!) |
|
|
|