oj.uz

Submission #757223

# Submission time Handle Problem Language Result Execution time Memory
757223 2023-06-12T20:05:31 Z amirhoseinfar1385 Star Trek (CEOI20_startrek) C++17
45 / 100
 87 ms 14864 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;
	}
}
 
int newdp[maxn],newtaghbal[maxn],newtaghpaeen[maxn],newvasbal[maxn],newvaspaeen[maxn];
pair<int,int>newres[maxn],newresa[maxn];

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

void sevom(int u,int 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(int u,int 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(int u,int para=0,pair<int,int>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<int,int>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(int 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 3 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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2684 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 2680 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2684 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 2680 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2684 KB Output is correct
7 Correct 2 ms 2684 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 2 ms 2688 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 2680 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2684 KB Output is correct
7 Correct 2 ms 2684 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 72 ms 11468 KB Output is correct
13 Correct 87 ms 14864 KB Output is correct
14 Correct 44 ms 8648 KB Output is correct
15 Correct 64 ms 8780 KB Output is correct
16 Correct 50 ms 8944 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 2680 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2684 KB Output is correct
7 Correct 2 ms 2684 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Incorrect 2 ms 2816 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 2680 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2684 KB Output is correct
7 Correct 2 ms 2684 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 72 ms 11468 KB Output is correct
13 Correct 87 ms 14864 KB Output is correct
14 Correct 44 ms 8648 KB Output is correct
15 Correct 64 ms 8780 KB Output is correct
16 Correct 50 ms 8944 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Incorrect 2 ms 2816 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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