oj.uz

답안 #636197

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
636197 2022-08-28T13:38:40 Z amirhoseinfar1385 Subtree (INOI20_subtree) C++17
12 / 100
 127 ms 23964 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,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[u]=res[u];
		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[u]*=resa[adj[u][i]];
				resa[u]%=mod;
				continue;
			}
			resa[u]*=res[adj[u][i]]+1;
			resa[u]%=mod;
		}
		return ;
	}
	if(vaz[u]==2){
		for(int i=0;i<adj[u].size();i++){
			if(i==0){
				resa[u]*=resa[adj[u][i]];
				resa[u]%=mod;
				continue;
			}
			resa[u]*=res[adj[u][i]]+1;
			resa[u]%=mod;
		}
		res[u]=resa[u];
		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);
	resa.resize(n+1,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[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:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
Main.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
Main.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 1352 KB Output is correct
3 Correct 96 ms 11436 KB Output is correct
4 Correct 93 ms 11548 KB Output is correct
5 Correct 105 ms 11428 KB Output is correct
6 Correct 112 ms 11368 KB Output is correct
7 Correct 109 ms 21124 KB Output is correct
8 Correct 111 ms 17748 KB Output is correct
9 Correct 106 ms 18092 KB Output is correct
10 Correct 74 ms 12848 KB Output is correct
11 Correct 110 ms 12884 KB Output is correct
12 Correct 92 ms 11040 KB Output is correct
13 Correct 95 ms 10828 KB Output is correct
14 Correct 94 ms 16072 KB Output is correct
15 Correct 127 ms 22768 KB Output is correct
16 Correct 113 ms 23964 KB Output is correct
17 Correct 92 ms 10952 KB Output is correct
18 Correct 95 ms 10992 KB Output is correct
19 Correct 91 ms 10968 KB Output is correct
20 Correct 71 ms 13356 KB Output is correct
21 Correct 71 ms 12108 KB Output is correct
22 Correct 76 ms 11848 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -