무결성 등급 관리

시간 제한1초메모리 제한128 MB

요약
A -> B 규칙으로 주어진 부분순서에서 임의의 두 레벨에 대해 최대하한이 보장될 때, 읽기와 쓰기 동작이 사용자나 문서의 레벨을 두 현재 레벨의 최대하한으로 낮추는 과정을 시뮬레이션하고 각 결과를 출력한다.
난이도

보통10점 중 7점

유형
그래프, 위상 정렬, 구현, 시뮬레이션
정답자
아직 제출이 없습니다

문제

동적 비바(Dynamic Biba) 무결성 모델에서는 모든 사용자와 모든 문서에 무결성 등급이 부여됩니다. 무결성 등급은 그 정보가 얼마나 신뢰할 수 있는지를 나타내며, 다음 두 규칙에 따라 변합니다.

  • 사용자가 자신보다 무결성 등급이 높은 문서에 쓰기를 하면, 문서의 무결성 등급이 낮아집니다. 어느 경우든 문서의 새 무결성 등급은 사용자의 등급과 문서의 이전 등급의 최대 하한(greatest lower bound)이 됩니다.
  • 사용자가 자신보다 무결성 등급이 낮은 문서를 읽기를 하면, 사용자의 무결성 등급이 낮아집니다. 어느 경우든 사용자의 새 무결성 등급은 사용자의 이전 등급과 문서의 등급의 최대 하한이 됩니다.

무결성 등급은 단순한 숫자가 아닙니다. 하나의 문서가 어떤 주제에 대해서는 매우 신뢰할 수 있는 정보를, 다른 주제에 대해서는 덜 신뢰할 수 있는 정보를 동시에 담을 수 있기 때문입니다. 각 등급은 임의의 라벨이며, 등급 사이의 순서는 A -> B 형태의 규칙으로 주어집니다. 이는 "등급 A는 최대한 등급 B만큼만 신뢰할 수 있다"는 뜻입니다. 이 순서는 다음 조건을 만족합니다.

  • 모든 라벨 A에 대해 A -> A가 항상 성립하며, 입력에 명시할 필요는 없습니다(명시해도 무방합니다).
  • 서로 다른 두 라벨 A, B에 대해 A -> B와 B -> A가 동시에 성립하는 경우는 없습니다. 다만 둘 다 성립하지 않을 수는 있습니다.
  • A -> B이고 B -> C이면 A -> C입니다(명시되지 않아도 성립).
  • 임의의 두 라벨 A, B에 대해 최대 하한인 라벨 G = glb(A, B)가 존재하여 G -> A와 G -> B가 성립합니다. 또한 L -> A이고 L -> B인 모든 라벨 L은 L -> G도 만족합니다.

주어진 행동들을 수행하면서 사용자와 문서의 무결성 등급을 추적하세요.

입력

  • 첫째 줄에 다섯 정수 l, r, u, d, a가 주어집니다. 각각 무결성 등급의 수, 규칙의 수, 사용자의 수, 문서의 수, 행동의 수이며 모두 10000 이하입니다. 등급은 1부터 l까지, 사용자는 1부터 u까지, 문서는 1부터 d까지 번호가 매겨집니다.
  • 다음 r개의 줄에는 각각 두 정수 x y (1 <= x, y <= l)가 주어지며 x -> y를 뜻합니다.
  • 다음 u개의 줄에는 각각 한 정수(1부터 l)가 주어지며, 사용자 1, 2, ..., u의 초기 등급입니다.
  • 다음 d개의 줄에는 각각 한 정수(1부터 l)가 주어지며, 문서 1, 2, ..., d의 초기 등급입니다.
  • 다음 a개의 줄에는 각각 하나의 행동이 아래 두 형식 중 하나로 주어집니다(user는 1부터 u, document는 1부터 d).
    • user reads document — 사용자의 등급을 glb(사용자의 현재 등급, 문서의 등급)으로 바꿉니다.
    • user writes document — 문서의 등급을 glb(사용자의 등급, 문서의 현재 등급)으로 바꿉니다.

출력

각 행동에 대해 순서대로, 바뀐 새 무결성 등급을 한 줄에 하나씩 출력합니다. reads 행동이면 사용자의 새 등급을, writes 행동이면 문서의 새 등급을 출력합니다.

예제1

  1. 예제 1

    입력
    9 11 2 3 5
6 9
2 6
9 4
7 5
3 8
7 2
5 3
8 4
5 1
6 1
1 8
4
2
5
9
8
1 reads 3
1 writes 2
2 reads 2
1 reads 1
2 writes 1
    예상 출력
    8
6
2
5
7