Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
if you have wa 9 | Михаил | 2030. Защитная Бэкап-Система | 28 июн 2019 16:41 | 1 |
Don't forget about long long int! |
What is test case 21 about? | Schwinn | 2030. Защитная Бэкап-Система | 1 сен 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. Защитная Бэкап-Система | 1 дек 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. Защитная Бэкап-Система | 30 ноя 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. Защитная Бэкап-Система | 13 апр 2015 23:51 | 1 |
If you get WA on test #8, don't forget about mod = 1000000007 :) |
Time limit | Snowball_TverSU | 2030. Защитная Бэкап-Система | 15 янв 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. Защитная Бэкап-Система | 12 ноя 2014 20:05 | 5 |
збс Birne Ageev 25 окт 2014 13:27 Re: збс Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 26 окт 2014 00:48 Re: збс Birne Ageev 26 окт 2014 10:11 В пршлм гд бл прфсср "Е.Бен", в этм "ЗБС". Нцнзрн брнь. Re: збс Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 26 окт 2014 14:08 нжн длг крть, чтб т рскрть - вбщ н дгдлс... Edited by author 26.10.2014 14:08 Re: збс Oxxxymiron 12 ноя 2014 20:05 збс же придумал автор?! ЗБС!) |