QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#673941#7738. Equivalent RewritingciyekuaWA 1ms3528kbC++232.1kb2024-10-25 12:00:312024-10-25 12:00:31

Judging History

你现在查看的是最新测评结果

  • [2024-10-25 12:00:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3528kb
  • [2024-10-25 12:00:31]
  • 提交

answer

#include<iostream>
#include<queue>
#include<map>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
#define int long long
#define endl '\n'
const int N = 2e5 + 10;
int f[N];
int find(int x)
{
    if (x == f[x])
        return f[x];
    f[x] = find(f[x]); return f[x];
}
void merge(int a, int b)
{
    find(a);
    f[f[a]] = find(b);
    find(a);
}
void solve()
{
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    vector<vector<int>> index(m + 10, vector<int>());
    for (int i = 1; i <= n; i++)
    {
        int p; cin >> p;
        for (int i = 1; i <= p; i++)
        {
            int x; cin >> x;
            index[x].push_back(i);
        }
    }
    for (int i = 1; i <= m; i++)
    {
        if (index[i].size() == 2)
            for (int j = 1; j < index[m].size(); j++)
            {
                merge(index[i][j], index[i][j - 1]);
            }
    }

    int ff = find(1); int cnt = 1;
    map<int, int> rr; rr[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (find(i) == ff)
        {
            rr[i] = 1; cnt++;
        }

    }
    if (cnt == n)
    {
        cout << "No" << endl; return;
    }
    else
    {
    	int fl1=0,fl2=0;
        cout << "Yes" << endl;
        for (int i = 1; i <= n; i++)
        {
            if (!rr[i]&&fl1==0) {
            	fl1=1;
            	cout << i ;
            	continue;
            }
            if (!rr[i]&&fl1==1) {
            	cout <<" "<< i ;
            }
            
        }
        if(!rr[n]) cout<<" ";
        for (int i = 1; i <= n; i++)
        {
            if (rr[i]&&fl2==0) {
            	fl2=1;
            	cout << i;
            	continue;
            }
            if (rr[i]&&fl2==1) {
            	cout <<" "<< i;
            }
        }
    }
    cout << endl;
}
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    int t; cin >> t;
    while (t--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3528kb

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
2 3 1
No
No

result:

wrong answer two transactions are not equivalent. (test case 1)