oj.uz

Submission #636222

# Submission time Handle Problem Language Result Execution time Memory
636222 2022-08-28T14:42:24 Z amirhoseinfar1385 Subtree (INOI20_subtree) C++17
12 / 100
 120 ms 25112 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;
		}
		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 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 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 108 ms 12680 KB Output is correct
4 Correct 99 ms 12576 KB Output is correct
5 Correct 94 ms 12676 KB Output is correct
6 Correct 93 ms 12668 KB Output is correct
7 Correct 114 ms 22384 KB Output is correct
8 Correct 120 ms 18956 KB Output is correct
9 Correct 111 ms 19304 KB Output is correct
10 Correct 79 ms 14036 KB Output is correct
11 Correct 88 ms 14124 KB Output is correct
12 Correct 97 ms 12348 KB Output is correct
13 Correct 108 ms 12024 KB Output is correct
14 Correct 87 ms 17272 KB Output is correct
15 Correct 108 ms 23960 KB Output is correct
16 Correct 113 ms 25112 KB Output is correct
17 Correct 99 ms 12108 KB Output is correct
18 Correct 107 ms 12188 KB Output is correct
19 Correct 102 ms 12076 KB Output is correct
20 Correct 68 ms 14652 KB Output is correct
21 Correct 72 ms 13340 KB Output is correct
22 Correct 74 ms 13100 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 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 -