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();
}
}