WA on #5 求助
查看原帖
WA on #5 求助
542128
liyixin0514楼主2024/11/4 21:45

rt,做法参考第一篇题解。

CF 返回错误:wrong answer 392nd numbers differ - expected: '0', found: '2'

求帮忙看看是哪里写错了,拜谢/bx

#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
constexpr int N=2e5+7;
int t,n,m;
int la[N];
int k;
int x;
vector<int> vec[N];
void clear() {
	rep(i,1,n) {
		for(int x:vec[i]) la[x]=-1;
		vec[i].clear();
	}
}
bool f[N];
int g[N];
bool vi[N];
bool canadd(int it) {
	for(int x:vec[it]) if(vi[x]) return 0;
	return 1;
}
void add(int it) {
	for(int x:vec[it]) vi[x]=1;
}
void del(int it) {
	for(int x:vec[it]) vi[x]=0;
}
int ls[N];
void init() {
	int l=n+1,r=n;
	for(;r>=1;--r) {
		while(l>1&&canadd(l-1)) add(l-1),--l;
		ls[r]=l;
		del(r);
	}
}
bool check(int l,int r) { return ls[r] <= l; }
int mxx;
void get_f() {
	mxx=-1;
	rep(i,1,n) {
		f[i]=0;
		g[i]=g[i-1];
		if(vec[i].empty()) { f[i]=1,g[i]=i,mxx=i; continue; }
		int mx=mxx;
		for(int x:vec[i]) mx=max(mx,la[x]),la[x]=i;
		if(mx!=-1&&check(g[mx]+1,i-1)) f[i]=1,g[i]=i;
	}
}
int main() {
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("my.out","w",stdout);
	#endif
	sf("%d",&t);
	rep(i,1,N-1) la[i]=-1;
	f[0]=1;
	while(t--) {
		sf("%d%d",&n,&m);
		rep(i,1,n) {
			sf("%d",&k);
			rep(j,1,k) {
				sf("%d",&x);
				vec[i].push_back(x);
			}
		}
		init();
		// rep(i,1,n) pf("%d ",ls[i]); pf("\n");
		get_f();
		// rep(i,1,n) pf("%d ",f[i]); pf("\n");
		int pos=ls[n];
		while(!f[pos-1]) ++pos;
		int sum=0;
		rep(i,pos,n) {
			if(vec[i].empty()) { sum=m; break; }
			sum+=vec[i].size();
		}
		pf("%d\n",sum);
		clear();
	}
}
2024/11/4 21:45
加载中...