oj.uz

Submission #636231

# Submission time Handle Problem Language Result Execution time Memory
636231 2022-08-28T15:03:57 Z amirhoseinfar1385 Subtree (INOI20_subtree) C++17
12 / 100
 138 ms 25204 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]);
			we[u]+=we[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;
		}
		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);
	vis.clear();
	vis.resize(n+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:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~
Main.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
Main.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
Main.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
Main.cpp:87:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 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 1492 KB Output is correct
3 Correct 101 ms 12680 KB Output is correct
4 Correct 97 ms 12672 KB Output is correct
5 Correct 98 ms 12584 KB Output is correct
6 Correct 95 ms 12680 KB Output is correct
7 Correct 120 ms 22320 KB Output is correct
8 Correct 125 ms 18948 KB Output is correct
9 Correct 114 ms 19352 KB Output is correct
10 Correct 81 ms 14136 KB Output is correct
11 Correct 89 ms 14092 KB Output is correct
12 Correct 135 ms 12296 KB Output is correct
13 Correct 96 ms 12072 KB Output is correct
14 Correct 88 ms 17288 KB Output is correct
15 Correct 124 ms 24036 KB Output is correct
16 Correct 138 ms 25204 KB Output is correct
17 Correct 100 ms 12156 KB Output is correct
18 Correct 109 ms 12076 KB Output is correct
19 Correct 137 ms 12184 KB Output is correct
20 Correct 71 ms 14644 KB Output is correct
21 Correct 74 ms 13328 KB Output is correct
22 Correct 74 ms 13144 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -