I want the ask aquestion. "You have a DAG(directed acyclic graph) which is the contain n(1<=n<=300.000) nod. How many nodes can you go if you will start nod i(1<=i<=n). You must find answer for all nod."
Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 07.11.2026 15:15:17 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Problem statement is not clear. Do you have a link to the original problem?
It seems to be "for each i, count vertices that can be reached from vertex i", which is at least O(N2). Whoops.
we can use dfs like idea i think. For every node there will be a mask which will indicate which nodes are reachable from this node. To calculate the mask of a node 'U' we can recursively calculate the info (mask) for the child nodes of 'U'. And to find the mask of U we can use bitwise OR operation.
The problem is as total node is 300000 we have to use an array of integers to define the mask. if we use int then the mask array will be of size 300000/32 = 9375. if we use long long then the mask array will be of size 300000/64 = 4688. is this a Online judge problem? may be the limit is not that big. can you provide the link if it is an online judge problem.
Then I guess ML for this problem is 10Gb.
Ooow. it's very cool question and solution. But this solution isn't fast.
Your question is exactly the same with http://www.spoj.com/problems/DAGCNT2/.
And does this problem actually have a better solution than O(N * M)? Or is it just about constant optimizations?
Someone told me they had proved the lower bound is OmegaO(|V||E|). But I didn't read the paper.
Actually, the problem setter said that his solution was based on std::bitset.
Thank you for answering, I was pondering on that question for a while. It does seem intuitive that you can't do better than that, a proof does seem complicated indeed though. Could you please link to the paper if you come across it? :)
The "someone" just told me. :) I didn't have the exact paper. Sorry about that.
In the problem on SPOJ, n=20000, very smaller than n in this problem. Time limit DAGCNT2 is 26s, and memory limit is 256MB. If we use the same implementation to submit on above problem. TL should be 390s (6.5 minutes) and ML should be 3840MB (3.8GB).
I think you can use a DP approach for this problem. I should be O( |V| + |E| ).
For each node that hasn't been calculate you run a dfs( u ). Where dfs(u) will return how many nodes you can reach from there and for each of its children you will run a dfs( ) that will save the number of nodes that each of its children can reach.
Well, this is my idea. Sorry if i have some grammar or spelling mistakes. I am trying to fix it.
This algorithm will not run correctly. for example we have four nodes. first node have two children which are second and third node. Second and third node have a child which is fourth node. fourth node haven't got a child. we called dfs( 1 ).
dfs(1) = dfs(2)+dfs(3)+1.
dfs(2) = dfs(4)+1 = 2.
dfs(3) = dfs(4)+1 = 2.
dfs(1) = 5.
for first node we count the fourth node twice. normally dfs(1)=4 but we find dfs(1)=5
So, I think that a solution could be that if you actually reach that node you don't have to count it.
In this example you will have:
Well, I think that should work.
And now answer for 3 is incorrect.
Someone told me a randomized algorithm can run really fast, and for at least 90% of
n, its answers' relative error is at most 10%. However, I could not remember the algorithm......Process vertices in inverse topological order.
For each vertex the result is 1 + sum of results for children
O(N + M) or I missed something?
for 4 node
roads
1 -> 2
1 -> 3
2 -> 4
3 -> 4
u counting two times node 4 for calculate node 1