QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#271261 | #7738. Equivalent Rewriting | iorit# | WA | 4ms | 63260kb | C++14 | 2.9kb | 2023-12-02 08:44:32 | 2023-12-02 08:44:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
namespace IO {
#if ONLINE_JUDGE
#define getc() (IS == IT && (IT = (IS = ibuf) + fread(ibuf, 1, IL, stdin), IS == IT) ? EOF : *IS++)
#else
#define getc() getchar()
#endif
const int IL = 1 << 21, OL = 1 << 21;
int olen = 0;
char ibuf[IL], *IS = ibuf, *IT = ibuf, obuf[OL];
inline int read() {
register char ch = getc(); register int x = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
return x * f;
}
inline double readdb() {
register char ch = getc(); register double x = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
if(ch == '.') {
register double b = 0.1;
ch = getc();
while(isdigit(ch)) x += (ch - 48) * b, b *= 0.1, ch = getc();
}
return x * f;
}
inline int readstr(char *s) {
register char ch = getc(); register int len = 0;
while(!isalpha(ch)) ch = getc();
while(isalpha(ch)) s[++len] = ch, ch = getc();
return len;
}
inline void flush() { fwrite(obuf, 1, olen, stdout); olen = 0; }
inline void putc(register char ch) { obuf[olen++] = ch; }
template<class T>
inline void write(register T x) {
if(x < 0) obuf[olen++] = '-', x = -x;
if(x > 9) write(x / 10);
obuf[olen++] = x % 10 + 48;
}
} using namespace IO;
const int N = 1e6 + 10;
int T, n, m, a[N], pre[N], col[N];
vector<int> vc[N], ans[N];
bool vis[N];
int cnt[N];
void MAIN() {
n = read(), m = read();
for(int i = 1; i <= m; i++)
a[i] = col[i] = 0;
for(int i = 1; i <= n; i++) {
cnt[i] = vis[i] = pre[i] = 0;
int x = read();
vc[i].clear();
ans[i].clear();
for(int j = 1; j <= x; j++) {
int y = read();
a[y] = i;
vc[i].push_back(y);
}
}
for(int i = 1; i <= m; i++)
vis[a[i]] = 1;
for(int i = 1; i <= n; i++)
if(!vis[i]) {
puts("Yes");
printf("%d ", i);
if(i == n) {
for(int j= 1; j < n; j++)
if(j < n - 1)printf("%d ", j);
else printf("%d\n", j);
}
else {
for(int j = 1; j <= n; j++) {
if(j == i) continue;
if(j < n) printf("%d ", j);
else printf("%d\n", j);
}
}
return;
}
for(int i = 1; i <= n; i++) {
for(auto x : vc[i]) {
if(a[x] == i) { pre[i] = max(pre[i], col[x]); }
// if(x==3)cout<<"!:"<<col[x]<<endl;
col[x] = i;
}
cnt[pre[i] + 1]++;
ans[pre[i] + 1].push_back(i);
}
// for(int i = 1; i <= n; i++)
// printf("cnt:%d %d\n", i, cnt[i]);
bool flg = 0;
for(int i = 1; i <= n; i++)
if(cnt[i] != 1) {
flg = 1;
break;
}
if(!flg) {
puts("No");
return;
}
puts("Yes");
int t = 0;
for(int i = 1; i <= n; i++) {
reverse(ans[i].begin(), ans[i].end());
for(auto x : ans[i]) {
printf("%d", x);
t++;
if(t != n) printf(" ");
else printf("\n");
}
}
}
int main() {
T = read();
while(T--) MAIN();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 61184kb
input:
3 3 6 3 3 1 5 2 5 3 2 2 6 2 3 3 1 3 2 2 3 1 1 3 2 2 1
output:
Yes 3 1 2 No No
result:
ok OK. (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 4ms
memory: 63260kb
input:
1 10 5 2 2 4 4 1 3 4 2 1 2 3 2 1 4 4 5 2 4 3 3 2 5 4 3 5 4 2 3 1 3 2 5 1 4 2 3 5 1 4
output:
Yes 1 2 3 4 5 6 7 8 9 10
result:
wrong answer two transactions are same. (test case 1)