QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#671473#7738. Equivalent RewritingnageingWA 0ms3832kbC++201.8kb2024-10-24 12:43:532024-10-24 12:43:54

Judging History

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

  • [2024-10-24 12:43:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3832kb
  • [2024-10-24 12:43:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

void solve() {
	int n, m;
	cin >> n >> m;
	DSU dsu(m);
	vector<int> rt(n);
	vector<int> vis(m);
	for (int i = 0; i < n; i ++) {
		int k;
		cin >> k;
		vector<int> a(k);
		for (int j = 0; j < k; j ++) {
			cin >> a[j];
			a[j] --;
			vis[a[j]] = 1;
			if (j > 0) {
				dsu.merge(a[0], a[j]);
			}
		}
		rt[i] = a[0];
	}
	
	int ans = 0;
	for (int i = 0; i < m; i ++) {
		int p = dsu.find(i);
		if (vis[p]) {
			vis[p] = 0;
			ans ++;
		}
	}
	if (ans > 1) {
		cout << "Yes\n";
		vector<int> res(n);
		for (int i = 0; i < n; i ++) {
			res[i] = i + 1;
		}
		int root = dsu.find(rt[0]);
		for (int i = 1; i < n; i ++) {
			int p = dsu.find(rt[i]);
			if (p != root) {
				cout << res[i] << ' ';
				for (int j = 0; j < n; j ++) {
					if (j != i) cout << res[j] << ' ';
				}
				break;
			}
		}
		cout << '\n';

	} else {
		cout << "No\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int t = 1;
	cin >> t;
	while (t --) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3544kb

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: 0ms
memory: 3832kb

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)