QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#585499 | #7738. Equivalent Rewriting | mhw | WA | 1ms | 3564kb | C++23 | 1.9kb | 2024-09-23 21:00:48 | 2024-09-23 21:00:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define db double
#define il inline
#define x first
#define y second
#define endl '\n'
const int N = 2e5 + 5;
const int mod = 998244353;
vector<int>g[N];
int s[N], in[N];
int cmp(int a, int b)
{
return a > b;
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
g[i].clear();
in[i] = 0;
}
for (int i = 1; i <= m; i++) s[i] = 0;
for (int i = 1; i <= n; i++)
{
int p; cin >> p;
for (int j = 1; j <= p; j++)
{
int b; cin >> b;
if (s[b]) g[s[b]].push_back(i);
s[b] = i;
}
}
for (int i = 1; i <= n; i++)
{
sort(g[i].begin(), g[i].end());
g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
for (auto j: g[i]) in[j]++;
sort(g[i].begin(), g[i].end(), cmp);
}
queue<int> q;
vector<int> ret;
for (int i = 1; i <= n; i++)
{
if (in[i] == 0)
{
q.push(i);
ret.push_back(i);
}
}
int f = 0;
while(q.size())
{
if (q.size() != 1) f = 1;
int t = q.front();
q.pop();
for (auto i: g[t])
{
in[i]--;
if(in[i] == 0)
{
q.push(i);
ret.push_back(i);
}
}
}
if (f)
{
cout << "Yes\n";
for (auto i: ret) cout << i << ' ';
cout << '\n';
}
else cout << "No\n";
}
signed main()
{
// freopen("D:\\3022244240\\vscode\\txt\\in.txt", "r", stdin);
// freopen("D:\\3022244240\\vscode\\txt\\out.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1; cin >> T;
while (T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
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 1 3 2 No No
result:
ok OK. (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3560kb
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:
No
result:
wrong answer jury found an answer but participant did not (test case 1)