QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811098#9840. Tree PartitionliuhengxiWA 52ms653608kbC++142.9kb2024-12-12 15:26:282024-12-12 15:26:29

Judging History

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

  • [2024-12-12 15:26:29]
  • 评测
  • 测评结果:WA
  • 用时:52ms
  • 内存:653608kb
  • [2024-12-12 15:26:28]
  • 提交

answer

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<vector>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
constexpr int N=2e5+5,K=405,MOD=998244353,INF=0x3fffffff;
void reduce(int &x){if(x>=MOD)x-=MOD;}
void reduce_(int &x){if(x<0)x+=MOD;}
struct dsu
{
	typedef unsigned long long ull;
	static constexpr int N=3130;
	int n,f[N],l[N];
	ull a[N];
	void init(int n_)
	{
		n=(n_+63)>>6;
		F(i,0,n)f[i]=-1,l[i]=i,a[i]=-1;
	}
	int find(int x){return f[x]<0?x:f[x]=find(f[x]);}
	void erase(int x)
	{
		++x;
		if(a[x>>6]^=1ull<<(x&63))return;
		x>>=6;
		int u=find(x),v=find(x-1);
		if(f[u]>f[v])swap(u,v);
		f[u]+=f[v];f[v]=u;
		l[u]=min(l[u],l[v]);
	}
	int query(int x)
	{
		++x;
		ull s=a[x>>6]<<(63-(x&63));
		if(s)return x-__builtin_clzll(s);
		x=l[find(x>>6)];
		return x<<6|(63^__builtin_clzll(x));
	}
}q;
int n,k,f[N],e[N],d[N],l[N],r[N],s[N],t,c[N],w[N][K],p[N][K];
vector<int> adj[N];
void merge(int x,int y,int z)
{
	while(f[x]>=0)x=f[x];
	while(f[y]>=0)y=f[y];
	if(f[x]>f[y])swap(x,y);
	f[x]+=f[y];e[y]=z;f[y]=x;
}
int dep(int x){return ~d[x]?d[x]:d[x]=f[x]<0?0:dep(f[x])+1;}
int pathmin(int x,int y)
{
	int h=dep(x)-dep(y),ans=INF;
	while(h>0)--h,ans=min(ans,e[x]),x=f[x];
	while(h<0)++h,ans=min(ans,e[y]),y=f[y];
	while(x!=y)ans=min(ans,e[x]),ans=min(ans,e[y]),x=f[x],y=f[y];
	return ans;
}
int pathmax(int x,int y)
{
	int h=dep(x)-dep(y),ans=-INF;
	while(h>0)--h,ans=max(ans,e[x]),x=f[x];
	while(h<0)++h,ans=max(ans,e[y]),y=f[y];
	while(x!=y)ans=max(ans,e[x]),ans=max(ans,e[y]),x=f[x],y=f[y];
	return ans;
}
int main()
{
	read(n,k);
	F(i,0,n-1)
	{
		int u,v;read(u,v);--u,--v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	F(i,0,n)f[i]=-1,d[i]=-1;
	for(int u=n;~--u;)for(int v:adj[u])if(v>u)merge(u,v,u);
	F(i,0,n-1)l[i]=pathmin(i,i+1);
	F(i,0,n)f[i]=-1,d[i]=-1;
	F(u,0,n)for(int v:adj[u])if(v<u)merge(u,v,u);
	F(i,0,n-1)r[i]=pathmax(i,i+1)-1;
	t=0;
	for(int i=n-1;~--i;)
	{
		c[i]=-1;
		s[t++]=i;
		while(t&&s[t-1]<r[i])c[s[--t]]=i;
	}
	t=0;
	w[0][0]=1;
	w[1][1]=1;
	q.init(n);
	F(i,0,n-1)
	{
		if(t)F(j,0,k+1)p[i][j]=p[s[t-1]][j];
		F(j,0,k+1)reduce(p[i][j]+=w[i][j]);
		s[t++]=i;
		while(t&&s[t-1]>l[i])q.erase(s[--t]);
		int v=q.query(c[i]);
		F(j,0,k)reduce(w[i+2][j+1]+=p[s[t-1]][j]);
		if(v)F(j,0,k)reduce_(w[i+2][j+1]-=p[v-1][j]);
		F(j,0,k)reduce(w[i+2][j+1]+=w[i+1][j]);
	}
	F(i,1,k+1)printf("%d\n",w[n][i]);
	return 0;
}

详细

Test #1:

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

input:

4 3
1 2
2 3
2 4

output:

1
2
2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 17732kb

input:

7 7
2 5
3 6
4 5
5 1
1 6
6 7

output:

1
1
0
0
1
2
1

result:

ok 7 lines

Test #3:

score: -100
Wrong Answer
time: 52ms
memory: 653608kb

input:

200000 20
1 2
1 3
1 4
6 5
6 7
6 8
12 9
12 10
12 11
13 14
13 15
13 16
20 17
20 18
20 19
21 22
21 23
21 24
21 25
1 13
6 13
12 13
20 13
21 13
27 26
27 28
27 29
32 30
32 31
32 33
34 35
34 36
34 37
38 39
38 40
38 41
43 42
43 44
43 45
46 47
46 48
46 49
46 50
27 38
32 38
34 38
43 38
46 38
51 52
51 53
51 54...

output:

1
430
92576
13298301
435439434
990863507
32986938
193070052
329254771
461116361
34138820
64600374
661520845
995113096
516059564
621179033
731579379
527074084
181615723
892209012

result:

wrong answer 2nd lines differ - expected: '13', found: '430'