QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546785#7738. Equivalent Rewritingpzc2004#WA 4ms34676kbC++141.5kb2024-09-04 13:38:402024-09-04 13:38:40

Judging History

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

  • [2024-09-04 13:38:40]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:34676kb
  • [2024-09-04 13:38:40]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
using namespace std;
template<class T>inline void read(T &x){
	x=0;
	char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))x=x*10+(c&15),c=getchar();
}

const int mN=1e5+9, mS=1.1e6+9;
int n, m, ind[mS];

vector<int> a[mN], ver[mS], ans;
int sta[mS], top;
// bool vis[mS];

bool check() {
	rep(i, 1, n) {
		if(ans[i-1]==i) {
			return 0;
		}
	}
	return 1;
}

int main(){

	int T_T;
	read(T_T);
	while(T_T--) {
		rep(i, 1, m) {
			a[i].clear();
		}
		rep(i, 1, m+n) {
			ver[i].clear();
		}
		rep(i, 1, n+m) {
			ind[i]=0;
			// vis[i]=0;
		}
		ans.clear();
		top=0;

		read(n), read(m);
		rep(i, 1, n) {
			int pi, id;
			scanf("%d", &pi);
			rep(__, 1, pi) {
				read(id);
				a[id].push_back(i);
			}
		}
		rep(i, 1, m) if(a[i].size()>1) {
			rep(__, 0, a[i].size()-2) {
				ver[a[i][__]].push_back(m+i);
				++ind[m+i];
			}
			ver[m+i].push_back(a[i].back());
			++ind[a[i].back()];
		}
		rep(i, 1, m+n) if(!ind[i]) {
			sta[++top]=i;
			// vis[i]=1;
		}
		while(top>0) {
			int tmp=sta[top];
			if(tmp==ans.size()+1 && top>1) {
				swap(sta[top], sta[1]);
			}

			int x=sta[top--];
			if(x<=n) {
				ans.push_back(x);
			}
			for(int y: ver[x]) {
				--ind[y];
				if(!ind[y]) {
					sta[++top]=y;
				}
			}
		}
		if(check()) {
			puts("Yes");
			for(int x: ans) {
				printf("%d ", x);
			}
			puts("");
		} else {
			puts("No");
		}
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 34676kb

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: 32440kb

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)