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); } } } 남은수 -= 지운것.個数; 남은크기 -= 비운크기; コンソール.書く([지운것.個数, 비운크기]); }}コンソール.書く([남은수, 남은크기]);