Codeforces 875C National Property 문제 해결
10206 단어 2-SAT
Some long and uninteresting story was removed…
The alphabet of Bookland is so large that its letters are denoted by positive integers. Each letter can be small or large, the large version of a letter x is denoted by x’. BSCII encoding, which is used everywhere in Bookland, is made in that way so that large letters are presented in the order of the numbers they are denoted by, and small letters are presented in the order of the numbers they are denoted by, but all large letters are before all small letters. For example, the following conditions hold: 2
A word x1, x2, …, xa is not lexicographically greater than y1, y2, …, yb if one of the two following conditions holds:
a ≤ b and x1 = y1, …, xa = ya, i.e. the first word is the prefix of the second word; there is a position 1 ≤ j ≤ min(a, b), such that x1 = y1, …, xj - 1 = yj - 1 and xj For example, the word “3’ 7 5” is before the word “2 4’ 6” in lexicographical order. It is said that sequence of words is in lexicographical order if each word is not lexicographically greater than the next word in the sequence.
Denis has a sequence of words consisting of small letters only. He wants to change some letters to large (let’s call this process a capitalization) in such a way that the sequence of words is in lexicographical order. However, he soon realized that for some reason he can’t change a single letter in a single word. He only can choose a letter and change all of its occurrences in all words to large letters. He can perform this operation any number of times with arbitrary letters of Bookland’s alphabet.
Help Denis to choose which letters he needs to capitalize (make large) in order to make the sequence of words lexicographically ordered, or determine that it is impossible.
Note that some words can be equal.
Input The first line contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of words and the number of letters in Bookland’s alphabet, respectively. The letters of Bookland’s alphabet are denoted by integers from 1 to m.
Each of the next n lines contains a description of one word in format li, si, 1, si, 2, …, si, li (1 ≤ li ≤ 100 000, 1 ≤ si, j ≤ m), where li is the length of the word, and si, j is the sequence of letters in the word. The words are given in the order Denis has them in the sequence.
It is guaranteed that the total length of all words is not greater than 100 000.
Output In the first line print “Yes” (without quotes), if it is possible to capitalize some set of letters in such a way that the sequence of words becomes lexicographically ordered. Otherwise, print “No” (without quotes).
If the required is possible, in the second line print k — the number of letters Denis has to capitalize (make large), and in the third line print k distinct integers — these letters. Note that you don’t need to minimize the value k.
You can print the letters in any order. If there are multiple answers, print any of them.
Examples input 4 3 1 2 1 1 3 1 3 2 2 1 1 output Yes 2 2 3 input 6 5 2 1 2 2 1 2 3 1 2 3 2 1 5 2 4 4 2 4 4 output Yes 0 input 4 3 4 3 2 2 1 3 1 1 3 3 2 3 3 2 3 1 output No Note In the first example after Denis makes letters 2 and 3 large, the sequence looks like the following:
2’ 1 1 3’ 2’ 1 1 The condition 2’
In the second example the words are in lexicographical order from the beginning, so Denis can do nothing.
In the third example there is no set of letters such that if Denis capitalizes them, the sequence becomes lexicographically ordered.
[1,m]의 숫자로 n 개의 문자열을 표시합니다.그 중에서 숫자는 대소문자로 나뉘는데 처음의 숫자는 모두 소문자이며 대문자는 반드시 소문자보다 작다고 규정한다.소문자 숫자 x의 대문자를 x로 설정하면 2<3,2′<3′, 3′<2가 있다.현재 당신은 일부 소문자를 대문자로 바꿀 수 있습니다. 모든 문자열을 입력 순서에 따라 배열한 후에 사전 순서를 충족시키는 것을 주의해야 합니다.n, m, 단어 길이의 합<=100000
#include
#define clr(x) memset(x, 0, sizeof x)
#define ms(a, x) memset(x, a, sizeof x)
using namespace std;
template <class T> inline void read(T &x) {
int flag = 1; x = 0;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = (x<<1)+(x<<3)+ch-'0'; ch = getchar(); }
x *= flag;
}
const int maxn = 100010;
queue <int> Q;
int n,m,num,tot,cnt,ans[maxn],head[maxn],nxt[maxn],vet[maxn];
int f[2][maxn],r[maxn],dis[maxn];
inline void add(int u, int v) { nxt[++cnt] = head[u]; vet[cnt] = v; head[u] = cnt; }
int main() {
read(n),read(m);
for(int i = 1; i <= n; i++) {
int now = i%2,pre=(i-1)%2;
if(i == 1) {
read(f[now][0]);
for(int j = 1; j <= f[now][0]; j++) read(f[now][j]);
}
else {
read(f[now][0]);
for(int j = 1; j <= f[now][0]; j++) read(f[now][j]);
bool flag = 1;
for(int j = 1, k = 1; j <= f[pre][0] && k <= f[now][0]; j++, k++)
if(f[pre][j] != f[now][k]) { flag = 0; add(f[pre][j], f[now][k]), r[f[now][k]]++; break; }
if(flag && f[pre][0] > f[now][0]) { cout << "No" << endl; return 0; }
}
}
ms(-1, dis);
for(int i = 1; i <= m; i++) if(!r[i]) Q.push(i), num++, dis[i] = 0;
while(!Q.empty()) {
int u = Q.front();
Q.pop();
for(int i = head[u]; i; i = nxt[i]) {
if(r[vet[i]] > 0) {
r[vet[i]]--;
dis[vet[i]] = max(dis[vet[i]], dis[u]+(u>vet[i]));
if(!r[vet[i]]) Q.push(vet[i]), num++;
}
}
}
for(int i = 1; i <= m; i++) {
if(dis[i]>1 || dis[i] == -1) { cout << "No" << endl; return 0; }
if(!dis[i]) ans[++tot] = i;
}
cout << "Yes" << endl;
cout << tot << endl;
for(int i = 1; i <= tot; i++) cout << ans[i] << ' ';
cout << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces 875C National Property 문제 해결Denis has a sequence of words consisting of small letters only. He wants to change some letters to large (let’s call thi...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.