컴퓨터에 프로그램 꾸러미 n개가 설치되어 있고 1번부터 n번까지 번호가 붙어 있다.
꾸러미마다 종류가 있다. 1은 사용자가 직접 설치한 꾸러미, 0은 다른 꾸러미 때문에 자동으로 설치된 꾸러미다.
i번 꾸러미의 크기는 sᵢ다.
관계 "a b"는 a번 꾸러미가 b번 꾸러미를 필요로 한다는 뜻이다.
두 꾸러미가 서로를 필요로 하거나, 관계를 따라가면 처음 꾸러미로 돌아오는 경우도 있다.
지우기 명령 "x"가 q개 주어지고, 주어진 차례대로 다음과 같이 처리한다.
x번 꾸러미가 이미 지워져 있으면 아무것도 바뀌지 않고 0을 출력한다.
그렇지 않고, 지금 설치되어 있는 꾸러미 가운데 x번 꾸러미를 필요로 하는 것이 하나라도 있으면 명령은 거절된다. 아무것도 바뀌지 않고 -1을 출력한다.
그렇지도 않으면 x번 꾸러미를 지운다. 이때 x번 꾸러미의 종류는 따지지 않는다.
꾸러미 하나가 지워질 때마다, 그 꾸러미가 필요로 하던 꾸러미 하나하나를 살핀다.
살피는 꾸러미가 아직 설치되어 있고, 종류가 0이며, 그것을 필요로 하는 설치된 꾸러미가 이제 하나도 없으면 그 꾸러미도 지운다.
이렇게 따라 지워진 꾸러미에도 같은 규칙을 적용하고, 더 지울 것이 없을 때까지 이어 간다.
위 규칙으로 지워지는 꾸러미 말고는 아무것도 지우지 않는다. 처음부터 아무도 필요로 하지 않던 종류 0 꾸러미도 명령으로 지우기 전에는 남아 있다.
꾸러미를 지운 명령마다, 그 명령으로 지워진 꾸러미의 수(x번 포함)와 그 크기의 합을 빈칸 하나로 띄워 한 줄에 출력하라.
모든 명령을 처리한 다음, 마지막 줄에 남아 있는 꾸러미의 수와 그 크기의 합을 빈칸 하나로 띄워 출력하라. 남은 꾸러미가 없으면 0 0을 출력한다.
입력
첫 줄에 n, m, q, 둘째 줄에 꾸러미 1번부터 n번까지의 종류(0 또는 1), 셋째 줄에 s₁ … sₙ, 다음 m줄에 줄마다 관계 a와 b, 다음 q줄에 줄마다 명령 x가 주어진다. 한 줄의 수들은 빈칸 하나로 나뉜다. 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. 같은 관계 "a b"는 두 번 주어지지 않는다. 모두 정수다
출력
명령마다 한 줄씩: 이미 지워진 꾸러미면 0, 거절되면 -1, 지웠으면 지워진 꾸러미의 수와 크기의 합. 마지막 줄에 남은 꾸러미의 수와 크기의 합. 수는 쉼표 없이 숫자만 쓴다
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
꾸러미마다 '나를 필요로 하는, 설치된 꾸러미의 수'를 세어 두는 것이 핵심이에요. 꾸러미를 지울 때 그것이 필요로 하던 꾸러미의 수를 1씩 줄이고, 0이 된 종류 0 꾸러미를 큐에 넣어 같은 일을 이어 가요. 들어오는 화살표가 0이 된 것부터 꺼내는 위상 정렬과 같은 움직임이고, 꾸러미 하나는 한 번만 지워지니 명령이 많아도 전체 일은 n + m + q에 비례해요. 예제를 따라가 볼게요. 명령 2는 1번이 2번을 필요로 해서 -1이에요. 명령 1은 1번과 2번을 지워요(3번은 5번이 아직 쓰고, 4번은 종류 1). 다음 명령 1은 0이에요. 명령 5는 5번 → 3번 → 9번으로 이어져 3 170이에요. 함정 하나: 종류 1 꾸러미까지 따라 지우면 여기서 4번도 지워져 4 210이 돼요. 함정 둘: 한 단계만 따라가면 9번이 남아 2 80이 돼요. 함정 셋: 7번과 8번은 서로를 필요로 해서 수가 0이 되지 않으니 남아요. '종류 1 꾸러미에서 따라갈 수 있는 것만 남긴다'로 풀면 둘까지 지워서 5 320이 돼요. 함정 넷: 거절은 지금 설치된 꾸러미만 따져요. 4번을 필요로 하던 2번과 9번은 이미 지워졌으니 명령 4는 1 40인데, 처음 입력의 수를 그대로 쓰면 -1이 돼요. 함정 다섯: 6번은 처음부터 아무도 쓰지 않지만 명령이 올 때까지 남아요. 명령마다 '아무도 안 쓰는 종류 0 꾸러미'를 모두 지우면 둘째 줄이 3 90이 돼요. 함정 여섯: 이미 지운 꾸러미인지 먼저 보지 않으면 두 번째 명령 1에서 1번을 또 지우면서 수를 한 번 더 줄여 3 130이 나와요. 함정 일곱: 크기의 합은 9조까지 커져요. Java·C#의 int는 오류 없이 엉뚱한 수가 되고 C·C++은 정의되지 않은 동작이라 long·long long을 써요. Python은 한계가 없고 JS·TS·크레이콘은 2^53까지 정확해요. 큐는 언어마다 달라요. Python은 리스트를 for p in gone:으로 도는 동안 append한 것도 이어서 돌아요. JS·TS는 배열과 head 번호, Java는 ArrayDeque, C#은 Queue<int>, C++은 std::queue, C는 배열과 head·tail을 써요. 크레이콘은 반복 (앞 = 0; 앞 < 지운것.개수; 앞++)으로 목록을 앞에서부터 읽으면서 지운것.넣기(b)로 뒤에 붙여요.
Pythonmain.py · 48 줄
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 줄
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 줄
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 줄
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 줄
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 줄
#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 줄
#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 줄
첫줄 = 콘솔.수들읽기();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); } } } 남은수 -= 지운것.개수; 남은크기 -= 비운크기; 콘솔.쓰기([지운것.개수, 비운크기]); }}콘솔.쓰기([남은수, 남은크기]);