oj.uz

Submission #633508

# Submission time Handle Problem Language Result Execution time Memory
633508 2022-08-22T15:36:28 Z MatBad Subtree (INOI20_subtree) C++14
12 / 100
 482 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=a; i<=b; i++)
#define FORR(i, a, b) for(int i=a; i>=b; i--)
#define pb push_back
#define ppb pop_back
#define lc 2*u
#define rc 2*u+1
#define mid ((l+r)/2)
#define F first
#define S second
#define debug(x) cerr<<"$ "<<#x<<" : "<<x<<"$\n"
#define wall() cerr<<"\n----------------------\n"

typedef long long ll;
typedef pair<int, int> pii;

const ll MX=1e5+5, M=1e9+5, LG=19, inf=1e9+5, MOD=1e9+7;

ll n, m, dp[2][MX];
vector<int> adj[MX];

void dfs(int u, int p){
	dp[1][u]=1;
	for(int v:adj[u])if(v!=p){
		dfs(v, u);
		dp[0][u] = (dp[0][u]+dp[0][v]+dp[1][v])%MOD;
		dp[1][u] = dp[1][u]*(dp[1][v]+1)%MOD;
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	FOR(i, 1, m) {
		int u, v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1, 0);
	cout<<(dp[0][1]+dp[1][1])%MOD<<'\n';
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 482 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2672 KB Output is correct
2 Correct 5 ms 3156 KB Output is correct
3 Correct 44 ms 8616 KB Output is correct
4 Correct 41 ms 8608 KB Output is correct
5 Correct 80 ms 8504 KB Output is correct
6 Correct 38 ms 8504 KB Output is correct
7 Correct 56 ms 14128 KB Output is correct
8 Correct 54 ms 11992 KB Output is correct
9 Correct 48 ms 12084 KB Output is correct
10 Correct 31 ms 8556 KB Output is correct
11 Correct 36 ms 8720 KB Output is correct
12 Correct 46 ms 8552 KB Output is correct
13 Correct 43 ms 8544 KB Output is correct
14 Correct 42 ms 11080 KB Output is correct
15 Correct 57 ms 14956 KB Output is correct
16 Correct 46 ms 15708 KB Output is correct
17 Correct 41 ms 8536 KB Output is correct
18 Correct 48 ms 8656 KB Output is correct
19 Correct 65 ms 8520 KB Output is correct
20 Correct 29 ms 8016 KB Output is correct
21 Correct 30 ms 8196 KB Output is correct
22 Correct 30 ms 8168 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 482 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 482 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -