连带删除不再需要的软件包

import sys  def 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()

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"));

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"));

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);    }}

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);    }}

#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;}

#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;}

첫줄 = 控制台.读数字();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];종류 = 控制台.读数字();크기 = 控制台.读数字(); // 필요[a] = a가 필요로 하는 꾸러미들, 쓰는수[b] = b를 필요로 하는, 설치된 꾸러미의 수필요 = [];循环 (v = 0; v <= n; v++){    필요.添加([]);}쓰는수 = 新列表(n + 1, 0);循环 (i = 0; i < m; i++){    줄 = 控制台.读数字();    필요[줄[0]].添加(줄[1]);    쓰는수[줄[1]] += 1;} 설치됨 = 新列表(n + 1, 真);남은수 = n;남은크기 = 0;遍历 (s 在 크기){    남은크기 += s;}循环 (i = 0; i < q; i++){    x = 控制台.读行().转数字();    如果 (!설치됨[x])    {        控制台.输出(0);    }    否则 如果 (쓰는수[x] > 0)    {        控制台.输出(-1);    }    否则    {        // 위상 정렬처럼: 쓰는 쪽이 0이 된 꾸러미를 차례로 꺼내며 그 아래의 수를 줄인다        설치됨[x] = 假;        지운것 = [x];        비운크기 = 0;        循环 (앞 = 0; 앞 < 지운것.数量; 앞++)        {            p = 지운것[앞];            비운크기 += 크기[p - 1];            遍历 (b 在 필요[p])            {                쓰는수[b] -= 1;                如果 (쓰는수[b] == 0 && 종류[b - 1] == 0)                {                    설치됨[b] = 假;                    지운것.添加(b);                }            }        }        남은수 -= 지운것.数量;        남은크기 -= 비운크기;        控制台.输出([지운것.数量, 비운크기]);    }}控制台.输出([남은수, 남은크기]);