NOI '15 P2 - Software Package Manager - DMOJ: Modern Online Judge

NOI '15 P2 - Software Package Manager

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

You'd like to design a package manager on your own, and thus you'd like to resolve the dependency problem among packages. If package $A$ $A$ depends on package $B$ $B$ , then we must install package $B$ $B$ before package $A$ $A$ . Likewise, if we'd like to remove package $B$ $B$ , we also need to remove package $A$ $A$ . You know the dependency relations among the packages, and you may assume all packages other than package $0$ $0$ will rely on exactly one package (package $0$ $0$ does not rely on any other packages). There are no cycles in the dependency relation (like $A_1$ $A_{1}$ depends on $A_2$ $A_{2}$ , $A_2$ $A_{2}$ depends on $A_3$ $A_{3}$ , …, $A_{m_1}$ $A_{m_{1}}$ depends on $A_m$ $A_{m}$ but $A_m$ $A_{m}$ depends on $A_1$ $A_{1}$ ), and of course no package depends on itself.

Now you'd like to know how many packages have their status changed upon installing or uninstalling a given package. Notice installing an installed package or uninstalling an uninstalled package will not change the status of any package.

Input Specification

The first line of the input is an integer $n$ $n$ representing the number of packages. The packages are numbered beginning with $0$ $0$ .

The next line has $n-1$ $n - 1$ integers separated by a single space, representing the package that package $1, 2, \dots, n-2, n-1$ $1, 2, \dots, n - 2, n - 1$ depends on.

The next line contains an integer $q$ $q$ representing the number of queries. In the following $q$ $q$ lines, each line contains a query of form install x or uninstall x representing installing or uninstalling package $x$ $x$ . You need to maintain the status of each package. Initially, all packages are uninstalled. You need to output how many packages will change the status after the step, and then apply the (un)installation.

Output Specification

The output consists of $q$ $q$ lines. The $i$ $i$ -th line is an integer representing the number of packages whose status change at step $i$ $i$ .

Sample Input 1

Copy

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

Sample Output 1

Copy

Sample Input 2

Copy

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

Sample Output 2

Copy

Constraints

Test Case	$n$ $n$	$q$ $q$	Additional Constraints
1	$n = 5\,000$ $n = 5 000$	$q = 5\,000$ $q = 5 000$
2	$n = 5\,000$ $n = 5 000$	$q = 5\,000$ $q = 5 000$
3	$n = 100\,000$ $n = 100 000$	$q = 100\,000$ $q = 100 000$	We never uninstall a package.
4	$n = 100\,000$ $n = 100 000$	$q = 100\,000$ $q = 100 000$	We never uninstall a package.
5	$n = 100\,000$ $n = 100 000$	$q = 100\,000$ $q = 100 000$	The package that package $i$ $i$ depends on is uniformly at random in $[0,i-1]$ $[0, i - 1]$ . The package installed or uninstalled at each query is uniformly at random in $[0,n-1]$ $[0, n - 1]$ .
6
7
8
9	$n = 100\,000$ $n = 100 000$	$q = 100\,000$ $q = 100 000$
10
11
12
13
14
15
16
17
18
19
20

Comments

There are no comments at the moment.