QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#811098 | #9840. Tree Partition | liuhengxi | WA | 52ms | 653608kb | C++14 | 2.9kb | 2024-12-12 15:26:28 | 2024-12-12 15:26:29 |
Judging History
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'