oj.uz

Submission #636226

# Submission time Handle Problem Language Result Execution time Memory
636226 2022-08-28T14:56:05 Z amirhoseinfar1385 Subtree (INOI20_subtree) C++17
12 / 100
 116 ms 25164 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,m;
vector<vector<long long>>adj;
vector<long long>par;
vector<long long>vaz;
vector<long long>res,resa[2][2],we;
vector<bool>vis;
long long mod=1e9+7;
void solvef(long long u){
	if(we[u]!=0){
		vaz[u]=1;
	}
	vis[u]=1;
	vector<long long>adja;
	for(int i=0;i<adj[u].size();i++){
		if(vis[adj[u][i]]==0){
			adja.push_back(adj[u][i]);
		}
	}
	adj[u]=adja;
	long long counta=0;
	adja.clear();
	for(int i=0;i<adj[u].size();i++){
		counta++;
		we[adj[u][i]]++;
	}
	for(int i=0;i<adj[u].size();i++){
		if(vis[adj[u][i]]==0){
			we[adj[u][i]]--;
			counta--;
			solvef(adj[u][i]);
			adja.push_back(adj[u][i]);
			if(we[adj[u][i]]>0){
				swap(adja[0],adja.back());
			}
		}
	}
	if(counta!=0){
		vaz[u]=2;
	}
	we[u]-=counta;
	adj[u]=adja;
}

void solves(long long u){
	vis[u]=1;
	for(int i=0;i<adj[u].size();i++){
		solves(adj[u][i]);
	}
	if(vaz[u]==1){
		for(int i=0;i<adj[u].size();i++){
			res[u]*=res[adj[u][i]]+1;
			res[u]%=mod;
		}
		resa[1][0][u]=res[u];
		resa[0][1][u]=1;
		return ;
	}
	if(vaz[u]==0){
		for(int i=0;i<adj[u].size();i++){
			res[u]*=res[adj[u][i]]+1;
			res[u]%=mod;
		}
		for(int i=0;i<adj[u].size();i++){
			if(i==0){
				resa[1][0][u]+=resa[1][0][adj[u][i]];
				resa[1][1][u]+=resa[1][1][adj[u][i]]+resa[0][1][adj[u][i]];
				resa[0][1][u]+=resa[1][0][adj[u][i]]+resa[0][1][adj[u][i]];
				resa[1][0][u]%=mod;
				resa[1][1][u]%=mod;
				resa[0][1][u]%=mod;
				continue;
			}
			resa[1][1][u]*=res[adj[u][i]]+1;
			resa[1][1][u]%=mod;
			resa[1][0][u]*=res[adj[u][i]]+1;
			resa[1][0][u]%=mod;
			resa[0][1][u]*=res[adj[u][i]]+1;
			resa[0][1][u]%=mod;
		}
		return ;
	}
	if(vaz[u]==2){
		res[u]--;
		for(int i=0;i<adj[u].size();i++){
			if(i==0){
				res[u]+=resa[1][1][adj[u][i]]+resa[0][1][adj[u][i]];
				res[u]%=mod;
				continue;
			}
			res[u]*=res[adj[u][i]]+1;
			res[u]%=mod;
		}
		res[u]++;
		res[u]%=mod;
		return ;
	}
}

int main(){
	cin>>n>>m;
	adj.resize(n+1);
	par.resize(n+1);
	vis.resize(n+1);
	vaz.resize(n+1);
	res.resize(n+1,1);
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			resa[i][j].resize(n+1);
		}
	}
	we.resize(n+1);
	for(int i=0;i<m;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	solvef(1);
	solves(1);
	long long mainres=0;
	for(int i=1;i<=n;i++){
	//	cout<<i<<" "<<res[i]<<" "<<resa[1][0][i]<<" "<<resa[1][1][i]<<" "<<resa[0][1][i]<<" "<<vaz[i]<<endl;
		mainres+=res[i];
		mainres%=mod;
	}
	cout<<mainres<<endl;
}

Compilation message

Main.cpp: In function 'void solvef(long long int)':
Main.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~
Main.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~
Main.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~
Main.cpp: In function 'void solves(long long int)':
Main.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~
Main.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
Main.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
Main.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
Main.cpp:86:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 1516 KB Output is correct
3 Correct 104 ms 12680 KB Output is correct
4 Correct 99 ms 12644 KB Output is correct
5 Correct 104 ms 12620 KB Output is correct
6 Correct 95 ms 12624 KB Output is correct
7 Correct 112 ms 22332 KB Output is correct
8 Correct 116 ms 18948 KB Output is correct
9 Correct 113 ms 19248 KB Output is correct
10 Correct 79 ms 13952 KB Output is correct
11 Correct 83 ms 14096 KB Output is correct
12 Correct 95 ms 12256 KB Output is correct
13 Correct 99 ms 12128 KB Output is correct
14 Correct 91 ms 17336 KB Output is correct
15 Correct 111 ms 23984 KB Output is correct
16 Correct 113 ms 25164 KB Output is correct
17 Correct 100 ms 12108 KB Output is correct
18 Correct 105 ms 12276 KB Output is correct
19 Correct 99 ms 12192 KB Output is correct
20 Correct 70 ms 14656 KB Output is correct
21 Correct 74 ms 13332 KB Output is correct
22 Correct 74 ms 13036 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -