| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 | 2048 MB | 29 | 2 | 2 | 9.091% |
통신망은 $N$개의 컴퓨터와 회선으로 구성된다. 컴퓨터는 $0$번부터 $N-1$번까지 번호가 붙어 있다. 하나의 회선은 서로 다른 $2$개의 컴퓨터가 양방향으로 통신할 수 있도록 한다. 즉, 통신망은 $N$개의 정점을 가지는 무방향 그래프이며, 각 회선은 서로 다른 두 정점을 잇는 간선의 역할을 한다. 초기 통신망에는 어떠한 회선도 존재하지 않는다.
매 초마다 통신망에는 여러 회선들이 추가되거나 제거된다. 구체적으로, 매 $u = 0, 1, 2, \cdots , T-1$에 대해서, 서로 다른 회선들의 집합 $E_u$가 주어진다. $u+0.5$초에, 통신망에 있는 회선들은 다음과 같은 규칙으로 갱신된다:
어떠한 정수 $t$와 두 컴퓨터 $a$, $b$에 대해서, 컴퓨터 $a$와 $b$가 $t$초에 연결되어 있다는 것은, $t$초에 통신망에 존재하는 회선들만 사용해서 컴퓨터 $a$와 컴퓨터 $b$를 잇는 경로가 존재함을 뜻한다. $a=b$일 경우, 이는 통신망의 회선 구성과 상관없이 항상 참임을 알 수 있다.
더 나아가, 어떠한 정수 $0 \le l \le r \le T$와 두 컴퓨터 $a$, $b$에 대해 컴퓨터 $a$와 $b$가 $l$초부터 $r$초까지 연결되어 있다는 것은, 모든 $t = l, l+1, \cdots , r$에 대해 컴퓨터 $a$와 $b$가 $t$초에 연결되어 있음을 뜻한다.
특정 시간 구간 동안 어떠한 컴퓨터에서 안정적으로 다른 컴퓨터와 통신할 수 있는지를 연구하기 위해, 당신은 다음과 같은 $Q$개의 질문을 하고자 한다:
다음 함수를 구현해야 한다.
vector<int> count_computers(int N, int T, int Q, vector<vector<array<int, 2>>> E, vector<array<int, 3>> F)
제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $N,S,Q ≤ 100$ |
| 2 | 12 | $N,S,Q ≤ 5\, 000$ |
| 3 | 19 | 모든 질문에 대해서, $l = r$ |
| 4 | 23 | $E$에 포함되는 모든 회선 $[a,b]$에 대해서, $| a - b | = 1$ |
| 5 | 41 | 추가적인 제약조건이 없다. |
다음 호출을 생각해보자.
count_computers(4, 5, 7, [[[0, 1], [1, 2]], [[2, 3], [1, 3]], [[0, 1], [0, 3]], [[0, 1], [1, 2], [0, 3], [2, 3]], [[1, 3]]], [[1, 1, 1], [2, 2, 2], [3, 3, 3], [0, 0, 5], [2, 1, 3], [1, 1, 4], [3, 2, 3]])
통신망에는 $4$개의 컴퓨터가 있다.
매 시간, 통신망의 회선 구성은 다음과 같다:
총 $7$개의 질문이 주어진다:
고로 함수는 $[3, 4, 4, 1, 3, 2, 4]$를 반환해야 한다.
샘플 그레이더의 입력 형식은 다음과 같다. $|E_i|$는 집합 $E_i$의 크기를 뜻하며, $S = \sum_{0 \le j \le T - 1}{E_j|}$이다.
샘플 그레이더는 다음 형식으로 답을 출력한다:
Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2026 > 1차 선발고사 2번
C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)