oj.uz

Submission #757224

# Submission time Handle Problem Language Result Execution time Memory
757224 2023-06-12T20:09:37 Z amirhoseinfar1385 Star Trek (CEOI20_startrek) C++17
45 / 100
 72 ms 13516 KB 
#include<bits/stdc++.h>
using namespace std;
long long mod=1e9+7;
long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}
long long n,d;
const long long maxn=100000+10;
vector<long long>adj[maxn];
long long cnttagh,cntnafaraval,cntnafardovom,dp[maxn],tagh[maxn];
vector<vector<long long>>mat(2,vector<long long>(2)),mata(2,vector<long long>(1)),res;
 
void zarb(vector<vector<long long>>a,vector<vector<long long>>b){
	long long n1=a.size(),m1=a.back().size(),n2=b.size(),m2=b.back().size();
	res.clear();
	if(m1!=n2){
		return ;
	}
	res.resize(n1,vector<long long>(m2));
	for(long long i=0;i<n1;i++){
		for(long long j=0;j<m2;j++){
			for(long long h=0;h<m1;h++){
				res[i][j]+=a[i][h]*b[h][j];
				res[i][j]%=mod;
			}
		}
	}
}
 
void tav(vector<vector<long long>>&a,long long b){
	vector<vector<long long>>fake=a;
	b--;
	while(b>0){
		if(b&1){
			zarb(fake,a);
			a=res;
		}
		zarb(fake,fake);
		fake=res;
		b>>=1;
	}
}
 
void aval(long long u,long long para=0){
	for(auto x:adj[u]){
		if(x!=para){
			aval(x,u);
			if(dp[x]==0){
				dp[u]++;
			}
		}
	}
}
 
void caltagh(long long u,long long para=0){
	if(para==0){
		tagh[u]=1;
	}
	else if(tagh[para]==1){
		if(dp[para]==0){
			tagh[u]=1;
		}
		else if(dp[para]==1&&dp[u]==0){
			tagh[u]=1;
		}
	}
	if(tagh[u]==1&&dp[u]==0){
		cnttagh++;
	}
	for(auto x:adj[u]){
		if(x==para){
			continue;
		}
		caltagh(x,u);
	}
}
 
void caldp(long long u,long long para=0,long long cn=1){
	if(cn==0){
		dp[u]++;
	}
	if(dp[u]==0){
		if(u<=n)
			cntnafardovom++;
	}
	else{
		if(u<=n)
			cntnafaraval++;
	}
	for(auto x:adj[u]){
		if(x!=para){
			if(dp[x]==0){
				caldp(x,u,dp[u]-1);
			}
			else{
				caldp(x,u,dp[u]);
			}
		}
	}
}
 
void clear(){
	for(long long i=1;i<=n+2;i++){
		dp[i]=0;
	}
}
 
long long newdp[maxn],newtaghbal[maxn],newtaghpaeen[maxn],newvasbal[maxn],newvaspaeen[maxn];
pair<long long,long long>newres[maxn],newresa[maxn];

void dovom(long long u,long long para=0){
	for(auto x:adj[u]){
		if(x!=para){
			dovom(x,u);
			if(newdp[x]==0){
				newdp[u]++;
			}
		}
	}
}

void sevom(long long u,long long para=0,long long cn=1){
	if(para!=0){
		if(newdp[u]==0){
			if(newdp[para]==1){
				newvasbal[u]=1;
				newvaspaeen[u]=1;
			}
		}
		else{
			if(newdp[para]==0){
				newvaspaeen[u]=1;
			}
		}
		if(newdp[u]==0){
			newtaghbal[u]=1;
		}
		if(cn==0){
			newtaghpaeen[u]=1;
		}
	}
	if(cn==0){
		newdp[u]++;
	}
	for(auto x:adj[u]){
		if(x!=para){
			if(newdp[x]==0){
				sevom(x,u,newdp[u]-1);
			}
			else{
				sevom(x,u,newdp[u]);
			}
		}
	}

}


void chaharom(long long u,long long para=0){
	if(newdp[u]==0){
		newres[u].second++;
		newresa[u].second++;
	}
	else{
		newres[u].first++;
	}
	for(auto x:adj[u]){
		if(x!=para){
			chaharom(x,u);
			if(newvasbal[x]==1){
				newres[u].first+=newres[x].first;
				newres[u].second+=newres[x].second;
				if(newtaghpaeen[x]==1){
					newresa[u].first+=newres[x].first;
					newresa[u].second+=newres[x].second;
				}
			}
		}
	}
}



void panjom(long long u,long long para=0,pair<long long,long long>azb=make_pair(0,0)){
	if(newvasbal[u]==1){
		newres[u].first+=azb.first;
		newres[u].second+=azb.second;
		if(newtaghbal[u]==1){
			newresa[u].first+=azb.first;
			newresa[u].second+=azb.second;
		}
	}
	for(auto x:adj[u]){
		if(x!=para){
			pair<long long,long long>ers=azb;
			if(newvaspaeen[x]==1){
				ers.first-=newres[x].first;
				ers.second-=newres[x].second;
			}
			panjom(x,u,ers);
		}
	}
}










int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>d;
	for(long long i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	aval(1);
	caltagh(1);
	caldp(1);
	long long z=dp[1];
	mata[0][0]=cntnafaraval;
	mata[1][0]=cntnafardovom;
	mat[0][0]=cntnafaraval*n;
	mat[1][0]=cntnafardovom*n;
	if(d==1){
		long long res=0;
		if(dp[1]>=1){
			res=1ll*(n-cnttagh)*n%mod;
			res+=1ll*cnttagh*cntnafaraval%mod;
			res%=mod;
			cout<<res<<"\n";
		}
		else{
			res=1ll*cnttagh*cntnafardovom%mod;
			cout<<res<<"\n";
		}
		return 0;
	}
	clear();
	dovom(1);
	sevom(1);
	chaharom(1);
	panjom(1);
	for(long long i=1;i<=n;i++){
		mat[0][1]+=cntnafaraval-newresa[i].first+newresa[i].second;
		mat[1][1]+=cntnafardovom-newresa[i].second+newresa[i].first;
	}
	cntnafaraval=0;
	cntnafardovom=0;
	tav(mat,d-1);
	zarb(mat,mata);
	cntnafaraval=res[0][0];
	cntnafardovom=res[1][0];
	long long sm=cntnafaraval+cntnafardovom;
	long long res=0;
	if(z>=1){
		res=1ll*(n-cnttagh)*(sm)%mod;
		res+=1ll*cnttagh*cntnafaraval%mod;
		res%=mod;
		cout<<res<<"\n";
	}
	else{
		res=1ll*cnttagh*cntnafardovom%mod;
		cout<<res<<"\n";
	}
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 72 ms 10356 KB Output is correct
13 Correct 65 ms 13516 KB Output is correct
14 Correct 53 ms 7652 KB Output is correct
15 Correct 56 ms 7624 KB Output is correct
16 Correct 46 ms 7764 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Incorrect 2 ms 2772 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 72 ms 10356 KB Output is correct
13 Correct 65 ms 13516 KB Output is correct
14 Correct 53 ms 7652 KB Output is correct
15 Correct 56 ms 7624 KB Output is correct
16 Correct 46 ms 7764 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Incorrect 2 ms 2772 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2772 KB Output isn't correct
3 Halted 0 ms 0 KB -