A computer has n program packages installed, numbered 1 to n.
Each package has a kind. 1 is a package the user installed by hand, and 0 is a package installed automatically because of another package.
The size of package i is sᵢ.
A relation "a b" means that package a needs package b.
Two packages may need each other, and following relations may lead back to the starting package.
There are q removal commands "x", handled in the given order as follows.
If package x has already been removed, nothing changes and 0 is printed.
Otherwise, if at least one currently installed package needs package x, the command is refused. Nothing changes and -1 is printed.
Otherwise package x is removed. The kind of package x does not matter here.
Every time a package is removed, each package it needed is looked at.
If the package looked at is still installed, has kind 0, and no installed package needs it any more, it is removed as well.
The same rule applies to packages removed this way, and this continues until nothing more can be removed.
Nothing is removed except by the rules above. A kind 0 package that nobody needed from the start also stays until a command removes it.
For each command that removed packages, print on one line the number of packages removed by that command (including x) and the sum of their sizes, separated by one space.
After all commands, print on the last line the number of packages still installed and the sum of their sizes, separated by one space. If none are left, print 0 0.
Input
The first line has n, m and q, the second line the kinds of packages 1 to n (0 or 1), the third line s₁ … sₙ, each of the next m lines a relation a and b, and each of the next q lines a command x. Numbers on a line are separated by one space. 1 ≤ n ≤ 9,000, 0 ≤ m ≤ 9,000, 1 ≤ q ≤ 9,000, 1 ≤ sᵢ ≤ 1,000,000,000, 1 ≤ a, b, x ≤ n, a ≠ b. The same relation "a b" is not given twice. All are integers
Output
One line per command: 0 if the package was already removed, -1 if refused, otherwise the number of packages removed and the sum of their sizes. On the last line, the number of packages left and the sum of their sizes. Write numbers as digits only, without commas
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The key is to keep, for every package, 'the number of installed packages that need me'. When a package is removed, lower that number by 1 for each package it needed, put every kind 0 package that reaches 0 into a queue, and carry on in the same way. This moves like a topological sort, which takes out whatever has no incoming arrows left, and since a package is removed only once the total work is proportional to n + m + q however many commands there are. Follow the example. Command 2 gives -1 because package 1 needs package 2. Command 1 removes packages 1 and 2 (package 3 is still used by 5, and package 4 has kind 1). The next command 1 gives 0. Command 5 goes 5 → 3 → 9 and gives 3 170. Trap one: remove kind 1 packages along the way too and package 4 goes here as well, giving 4 210. Trap two: follow only one step and package 9 stays, giving 2 80. Trap three: packages 7 and 8 need each other, so their numbers never reach 0 and they stay. Solve it as 'keep only what can be reached from kind 1 packages' and both are removed, giving 5 320. Trap four: refusal looks only at packages installed now. Packages 2 and 9, which needed package 4, are already gone, so command 4 gives 1 40; use the numbers from the original input and it gives -1. Trap five: nobody uses package 6 from the start, but it stays until a command comes. Remove every 'unused kind 0 package' on each command and the second line becomes 3 90. Trap six: without first checking whether the package is already removed, the second command 1 removes package 1 again and lowers the numbers once more, giving 3 130. Trap seven: the sum of sizes grows up to 9 trillion. Java and C# int silently give a wrong number and in C and C++ it is undefined behaviour, so use long / long long. Python has no limit, and JS, TS and Craykon are exact up to 2^53. Queues differ by language. In Python, while for p in gone: walks a list it also reaches items you append meanwhile. JS and TS use an array and a head index, Java ArrayDeque, C# Queue<int>, C++ std::queue, and C an array with head and tail. Craykon reads the list from the front with for (head = 0; head < gone.Count; head++) while adding to the back with gone.Add(b).
Pythonmain.py · 48 lines
import sysdef main(): data = sys.stdin.buffer.read().split() n, m, q = int(data[0]), int(data[1]), int(data[2]) manual = [False] + [x == b"1" for x in data[3:3 + n]] size = [0] + [int(x) for x in data[3 + n:3 + 2 * n]] needs = [[] for _ in range(n + 1)] # needs[a] = a가 필요로 하는 꾸러미들 users = [0] * (n + 1) # users[b] = b를 필요로 하는, 설치된 꾸러미의 수 pos = 3 + 2 * n for _ in range(m): a, b = int(data[pos]), int(data[pos + 1]) pos += 2 needs[a].append(b) users[b] += 1 installed = [True] * (n + 1) left_count = n left_size = sum(size) out = [] for i in range(q): x = int(data[pos + i]) if not installed[x]: out.append("0") continue if users[x] > 0: out.append("-1") continue # 위상 정렬처럼: 쓰는 쪽이 0이 된 꾸러미를 차례로 꺼내며 그 아래의 수를 줄인다 installed[x] = False gone = [x] freed = 0 for p in gone: # 도는 동안 뒤에 붙는 것도 이어서 돈다(큐) freed += size[p] for b in needs[p]: users[b] -= 1 if users[b] == 0 and not manual[b]: installed[b] = False gone.append(b) left_count -= len(gone) left_size -= freed out.append(f"{len(gone)} {freed}") out.append(f"{left_count} {left_size}") print("\n".join(out))main()
JavaScriptmain.js · 54 lines
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const [n, m, q] = data;const manual = [false];const size = [0];for (let i = 0; i < n; i++) { manual.push(data[3 + i] === 1); size.push(data[3 + n + i]);}const needs = Array.from({ length: n + 1 }, () => []); // needs[a] = a가 필요로 하는 꾸러미들const users = new Array(n + 1).fill(0); // users[b] = b를 필요로 하는, 설치된 꾸러미의 수let pos = 3 + 2 * n;for (let i = 0; i < m; i++) { const a = data[pos], b = data[pos + 1]; pos += 2; needs[a].push(b); users[b]++;}const installed = new Array(n + 1).fill(true);let leftCount = n;let leftSize = 0;for (let v = 1; v <= n; v++) leftSize += size[v];const out = [];for (let i = 0; i < q; i++) { const x = data[pos + i]; if (!installed[x]) { out.push("0"); continue; } if (users[x] > 0) { out.push("-1"); continue; } // 위상 정렬처럼: 쓰는 쪽이 0이 된 꾸러미를 차례로 꺼내며 그 아래의 수를 줄인다 installed[x] = false; const gone = [x]; let freed = 0; for (let head = 0; head < gone.length; head++) { const p = gone[head]; freed += size[p]; for (const b of needs[p]) { users[b]--; if (users[b] === 0 && !manual[b]) { installed[b] = false; gone.push(b); } } } leftCount -= gone.length; leftSize -= freed; out.push(`${gone.length} ${freed}`);}out.push(`${leftCount} ${leftSize}`);console.log(out.join("\n"));
TypeScriptmain.ts · 54 lines
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const [n, m, q] = data;const manual: boolean[] = [false];const size: number[] = [0];for (let i = 0; i < n; i++) { manual.push(data[3 + i] === 1); size.push(data[3 + n + i]);}const needs: number[][] = Array.from({ length: n + 1 }, () => []); // needs[a] = a가 필요로 하는 꾸러미들const users: number[] = new Array(n + 1).fill(0); // users[b] = b를 필요로 하는, 설치된 꾸러미의 수let pos = 3 + 2 * n;for (let i = 0; i < m; i++) { const a = data[pos], b = data[pos + 1]; pos += 2; needs[a].push(b); users[b]++;}const installed: boolean[] = new Array(n + 1).fill(true);let leftCount = n;let leftSize = 0;for (let v = 1; v <= n; v++) leftSize += size[v];const out: string[] = [];for (let i = 0; i < q; i++) { const x = data[pos + i]; if (!installed[x]) { out.push("0"); continue; } if (users[x] > 0) { out.push("-1"); continue; } // 위상 정렬처럼: 쓰는 쪽이 0이 된 꾸러미를 차례로 꺼내며 그 아래의 수를 줄인다 installed[x] = false; const gone: number[] = [x]; let freed = 0; for (let head = 0; head < gone.length; head++) { const p = gone[head]; freed += size[p]; for (const b of needs[p]) { users[b]--; if (users[b] === 0 && !manual[b]) { installed[b] = false; gone.push(b); } } } leftCount -= gone.length; leftSize -= freed; out.push(`${gone.length} ${freed}`);}out.push(`${leftCount} ${leftSize}`);console.log(out.join("\n"));
JavaMain.java · 59 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; in.nextToken(); int m = (int) in.nval; in.nextToken(); int q = (int) in.nval; boolean[] manual = new boolean[n + 1]; long[] size = new long[n + 1]; for (int v = 1; v <= n; v++) { in.nextToken(); manual[v] = in.nval == 1; } long leftSize = 0; for (int v = 1; v <= n; v++) { in.nextToken(); size[v] = (long) in.nval; leftSize += size[v]; } List<List<Integer>> needs = new ArrayList<>(); // needs.get(a) = a가 필요로 하는 꾸러미들 for (int v = 0; v <= n; v++) needs.add(new ArrayList<>()); int[] users = new int[n + 1]; // users[b] = b를 필요로 하는, 설치된 꾸러미의 수 for (int i = 0; i < m; i++) { in.nextToken(); int a = (int) in.nval; in.nextToken(); int b = (int) in.nval; needs.get(a).add(b); users[b]++; } boolean[] installed = new boolean[n + 1]; Arrays.fill(installed, true); int leftCount = n; StringBuilder out = new StringBuilder(); ArrayDeque<Integer> queue = new ArrayDeque<>(); for (int i = 0; i < q; i++) { in.nextToken(); int x = (int) in.nval; if (!installed[x]) { out.append("0\n"); continue; } if (users[x] > 0) { out.append("-1\n"); continue; } // 위상 정렬처럼: 쓰는 쪽이 0이 된 꾸러미를 차례로 꺼내며 그 아래의 수를 줄인다 installed[x] = false; queue.add(x); int count = 0; long freed = 0; // 9조까지 커지므로 long while (!queue.isEmpty()) { int p = queue.poll(); count++; freed += size[p]; for (int b : needs.get(p)) { users[b]--; if (users[b] == 0 && !manual[b]) { installed[b] = false; queue.add(b); } } } leftCount -= count; leftSize -= freed; out.append(count).append(' ').append(freed).append('\n'); } out.append(leftCount).append(' ').append(leftSize).append('\n'); System.out.print(out); }}
C#Main.cs · 70 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), m = int.Parse(data[1]), q = int.Parse(data[2]); var manual = new bool[n + 1]; var size = new long[n + 1]; long leftSize = 0; for (int v = 1; v <= n; v++) { manual[v] = data[2 + v] == "1"; size[v] = long.Parse(data[2 + n + v]); leftSize += size[v]; } var needs = new List<int>[n + 1]; // needs[a] = a가 필요로 하는 꾸러미들 for (int v = 0; v <= n; v++) needs[v] = new List<int>(); var users = new int[n + 1]; // users[b] = b를 필요로 하는, 설치된 꾸러미의 수 int pos = 3 + 2 * n; for (int i = 0; i < m; i++) { int a = int.Parse(data[pos]), b = int.Parse(data[pos + 1]); pos += 2; needs[a].Add(b); users[b]++; } var installed = new bool[n + 1]; Array.Fill(installed, true); int leftCount = n; var output = new StringBuilder(); var queue = new Queue<int>(); for (int i = 0; i < q; i++) { int x = int.Parse(data[pos + i]); if (!installed[x]) { output.Append("0\n"); continue; } if (users[x] > 0) { output.Append("-1\n"); continue; } // 위상 정렬처럼: 쓰는 쪽이 0이 된 꾸러미를 차례로 꺼내며 그 아래의 수를 줄인다 installed[x] = false; queue.Enqueue(x); int count = 0; long freed = 0; // 9조까지 커지므로 long while (queue.Count > 0) { int p = queue.Dequeue(); count++; freed += size[p]; foreach (int b in needs[p]) { users[b]--; if (users[b] == 0 && !manual[b]) { installed[b] = false; queue.Enqueue(b); } } } leftCount -= count; leftSize -= freed; output.Append(count).Append(' ').Append(freed).Append('\n'); } output.Append(leftCount).Append(' ').Append(leftSize).Append('\n'); Console.Write(output); }}
C++main.cpp · 59 lines
#include <iostream>#include <queue>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; vector<int> manual(n + 1); vector<long long> size(n + 1); long long leftSize = 0; for (int v = 1; v <= n; v++) cin >> manual[v]; for (int v = 1; v <= n; v++) { cin >> size[v]; leftSize += size[v]; } vector<vector<int>> needs(n + 1); // needs[a] = a가 필요로 하는 꾸러미들 vector<int> users(n + 1, 0); // users[b] = b를 필요로 하는, 설치된 꾸러미의 수 for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; needs[a].push_back(b); users[b]++; } vector<bool> installed(n + 1, true); int leftCount = n; for (int i = 0; i < q; i++) { int x; cin >> x; if (!installed[x]) { cout << "0\n"; continue; } if (users[x] > 0) { cout << "-1\n"; continue; } // 위상 정렬처럼: 쓰는 쪽이 0이 된 꾸러미를 차례로 꺼내며 그 아래의 수를 줄인다 installed[x] = false; queue<int> gone; gone.push(x); int count = 0; long long freed = 0; // 9조까지 커지므로 long long while (!gone.empty()) { int p = gone.front(); gone.pop(); count++; freed += size[p]; for (int b : needs[p]) { if (--users[b] == 0 && !manual[b]) { installed[b] = false; gone.push(b); } } } leftCount -= count; leftSize -= freed; cout << count << ' ' << freed << '\n'; } cout << leftCount << ' ' << leftSize << '\n'; return 0;}
Cmain.c · 66 lines
#include <stdio.h>#include <stdlib.h>int main(void) { int n, m, q; if (scanf("%d %d %d", &n, &m, &q) != 3) return 1; int *manual = malloc(sizeof(int) * (n + 1)); long long *size = malloc(sizeof(long long) * (n + 1)); long long left_size = 0; for (int v = 1; v <= n; v++) scanf("%d", &manual[v]); for (int v = 1; v <= n; v++) { scanf("%lld", &size[v]); left_size += size[v]; } /* 관계를 a별로 모아 한 배열에 이어 붙인다: a가 필요로 하는 것은 to[start[a]] ~ to[start[a+1]-1] */ int *ea = malloc(sizeof(int) * (m + 1)), *eb = malloc(sizeof(int) * (m + 1)); int *start = calloc(n + 2, sizeof(int)); int *users = calloc(n + 1, sizeof(int)); /* users[b] = b를 필요로 하는, 설치된 꾸러미의 수 */ for (int i = 0; i < m; i++) { scanf("%d %d", &ea[i], &eb[i]); start[ea[i] + 1]++; users[eb[i]]++; } for (int v = 1; v <= n + 1; v++) start[v] += start[v - 1]; int *fill = malloc(sizeof(int) * (n + 2)); for (int v = 0; v <= n + 1; v++) fill[v] = start[v]; int *to = malloc(sizeof(int) * (m + 1)); for (int i = 0; i < m; i++) to[fill[ea[i]]++] = eb[i]; char *installed = malloc(n + 1); for (int v = 0; v <= n; v++) installed[v] = 1; int *gone = malloc(sizeof(int) * (n + 1)); int left_count = n; for (int i = 0; i < q; i++) { int x; scanf("%d", &x); if (!installed[x]) { printf("0\n"); continue; } if (users[x] > 0) { printf("-1\n"); continue; } /* 위상 정렬처럼: 쓰는 쪽이 0이 된 꾸러미를 차례로 꺼내며 그 아래의 수를 줄인다 */ installed[x] = 0; int head = 0, tail = 0; gone[tail++] = x; long long freed = 0; /* 9조까지 커지므로 long long */ while (head < tail) { int p = gone[head++]; freed += size[p]; for (int k = start[p]; k < start[p + 1]; k++) { int b = to[k]; users[b]--; if (users[b] == 0 && !manual[b]) { installed[b] = 0; gone[tail++] = b; } } } left_count -= tail; left_size -= freed; printf("%d %lld\n", tail, freed); } printf("%d %lld\n", left_count, left_size); free(manual); free(size); free(ea); free(eb); free(start); free(users); free(fill); free(to); free(installed); free(gone); return 0;}
Craykonmain.cray · 65 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];종류 = Console.ReadNumbers();크기 = Console.ReadNumbers();// 필요[a] = a가 필요로 하는 꾸러미들, 쓰는수[b] = b를 필요로 하는, 설치된 꾸러미의 수필요 = [];for (v = 0; v <= n; v++){ 필요.Add([]);}쓰는수 = NewList(n + 1, 0);for (i = 0; i < m; i++){ 줄 = Console.ReadNumbers(); 필요[줄[0]].Add(줄[1]); 쓰는수[줄[1]] += 1;}설치됨 = NewList(n + 1, true);남은수 = n;남은크기 = 0;foreach (s in 크기){ 남은크기 += s;}for (i = 0; i < q; i++){ x = Console.ReadLine().ToNumber(); if (!설치됨[x]) { Console.WriteLine(0); } else if (쓰는수[x] > 0) { Console.WriteLine(-1); } else { // 위상 정렬처럼: 쓰는 쪽이 0이 된 꾸러미를 차례로 꺼내며 그 아래의 수를 줄인다 설치됨[x] = false; 지운것 = [x]; 비운크기 = 0; for (앞 = 0; 앞 < 지운것.Count; 앞++) { p = 지운것[앞]; 비운크기 += 크기[p - 1]; foreach (b in 필요[p]) { 쓰는수[b] -= 1; if (쓰는수[b] == 0 && 종류[b - 1] == 0) { 설치됨[b] = false; 지운것.Add(b); } } } 남은수 -= 지운것.Count; 남은크기 -= 비운크기; Console.WriteLine([지운것.Count, 비운크기]); }}Console.WriteLine([남은수, 남은크기]);