QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#801882#9840. Tree Partitionrotcar07WA 127ms343192kbC++232.5kb2024-12-07 10:29:162024-12-07 10:29:16

Judging History

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

  • [2024-12-07 10:29:16]
  • 评测
  • 测评结果:WA
  • 用时:127ms
  • 内存:343192kb
  • [2024-12-07 10:29:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998244353,N=2e5+5,M=405;
inline void red(int&x){x>=mod&&(x-=mod);}
int n,k;
vector<int> e[N];int fa[N];
void dfs(int p,int f){fa[p]=f;for(int x:e[p]) if(x!=f) dfs(x,p);}
vector<int> L[N];
int nxt[N],pre[N],cnt[N];
int dp[N][M];
int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1,u,v;i<n;i++) cin>>u>>v,e[u].push_back(v),e[v].push_back(u);
    dfs(1,0);
    for(int i=1;i<=n;i++) if(fa[i]>i) L[fa[i]].push_back(i);
    vector<pair<int,vector<int>>>A,B;
    for(int i=0;i<=n+1;i++) nxt[i]=i+1,pre[i]=i-1;
	A.emplace_back(-1,vector<int>(k+1,0));B.emplace_back(-1,vector<int>(k+1,0));
	A.emplace_back(0,vector<int>(k+1,0));A.back().second[0]=1;dp[0][0]=1;
    auto upd=[&](auto&A,int p){
		A.emplace_back(p,A.back().second);
		for(int i=0;i<=k;i++)red(A.back().second[i]+=dp[p][i]);
    };set<int> s;
    for(int i=1;i<=n;i++){
        if(fa[i]<i){
            vector<int> w;int T=0;
            for(int p=pre[i];p>=fa[i];p=pre[p]){
                cnt[p]++;
                if(cnt[p]==1) w.push_back(p);
                else{
                    T++;
                    nxt[pre[p]]=nxt[p];
                    pre[nxt[p]]=pre[p];
                }
            }
            while(T--) B.pop_back();
			reverse(w.begin(),w.end());
			for(int x:w) A.pop_back(),upd(B,x);
        }else s.insert(i);
		auto cmp=[&](const auto&x,const auto&y){return x.first<y.first;};
		for(int z:L[i]) s.erase(z);
		int fi=0,se=0;
		if(!s.empty()){
			fi=*s.rbegin();
			if(s.size()>1) se=*prev(prev(s.end()));
		}
		// cout<<fi<<" "<<se<<' '<<B.size()<<' '<<A.size()<<'\n';
		// for(auto w:B){
		// 	cout<<w.first<<' ';
		// 	for(int z:w.second) cout<<z<<' ';cout<<'\n';
		// }
		// cout<<"???\n";
		// for(auto w:A){
		// 	cout<<w.first<<' ';
		// 	for(int z:w.second) cout<<z<<' ';cout<<'\n';
		// }
		auto it=prev(lower_bound(B.begin(),B.end(),make_pair(fi,vector<int>()),cmp));
		// cout<<it-B.begin()<<"??!!!?\n";
		for(int j=1;j<=k;j++) red(dp[i][j]=B.back().second[j-1]+mod-it->second[j-1]);
		it=prev(lower_bound(A.begin(),A.end(),make_pair(se,vector<int>()),cmp));
		auto jt=prev(upper_bound(A.begin(),A.end(),make_pair(fi,vector<int>()),cmp));
		for(int j=1;j<=k;j++) red(dp[i][j]+=jt->second[j-1]-it->second[j-1]+mod);
		upd(A,i);
		// for(int j=0;j<=k;j++) cout<<dp[i][j]<<' ';cout<<'\n';
		// cout<<"____________\n";
    }
	for(int i=1;i<=k;i++) cout<<dp[n][i]<<'\n';
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5596kb

input:

4 3
1 2
2 3
2 4

output:

1
2
2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 7668kb

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: 127ms
memory: 343192kb

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
13
176
2319
30068
384955
4875560
61165940
760811301
405332244
640740004
59235978
467536955
332888870
612722928
918121025
55427569
38402530
247560044
261196503

result:

wrong answer 11th lines differ - expected: '246475419', found: '640740004'