Submission #1686051
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define FOR(i, n) for(int i = 0; i < (n); i++) #define MEM(a, x) memset(a, x, sizeof(a)) #define ALL(a) a.begin(), a.end() #define UNIQUE(a) a.erase(unique(ALL(a)), a.end()) typedef long long ll; int n; vector<int> g[100005]; ll MOD = 1000000007, dp[100005][2]; void dfs(int cur, int pre) { FOR(i, g[cur].size()) { int x = g[cur][i]; if (x != pre) { dfs(x, cur); dp[cur][0] = (dp[cur][0] * (dp[x][0] + dp[x][1])) % MOD; dp[cur][1] = (dp[cur][1] * dp[x][0]) % MOD; } } } int main(int argc, char const *argv[]) { ios_base::sync_with_stdio(false); cin >> n; FOR(i, n-1) { int u, v; cin >> u >> v; g[u-1].push_back(v-1); g[v-1].push_back(u-1); } FOR(i, n) FOR(j, 2) dp[i][j] = 1; dfs(0, -1); cout << (dp[0][0]+dp[0][1])%MOD << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 塗り絵 |
User | moguta |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 858 Byte |
Status | AC |
Exec Time | 49 ms |
Memory | 7424 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000.txt | AC | 2 ms | 2560 KB |
001.txt | AC | 3 ms | 2560 KB |
002.txt | AC | 34 ms | 6272 KB |
003.txt | AC | 43 ms | 7424 KB |
004.txt | AC | 29 ms | 5760 KB |
005.txt | AC | 43 ms | 7424 KB |
006.txt | AC | 40 ms | 7040 KB |
007.txt | AC | 44 ms | 7296 KB |
008.txt | AC | 31 ms | 6016 KB |
009.txt | AC | 49 ms | 7296 KB |
010.txt | AC | 31 ms | 6016 KB |
011.txt | AC | 43 ms | 7296 KB |
012.txt | AC | 26 ms | 5376 KB |
013.txt | AC | 43 ms | 7424 KB |
014.txt | AC | 21 ms | 4864 KB |
015.txt | AC | 44 ms | 7424 KB |
016.txt | AC | 27 ms | 5504 KB |
017.txt | AC | 44 ms | 7296 KB |
018.txt | AC | 9 ms | 3456 KB |
019.txt | AC | 44 ms | 7296 KB |
020.txt | AC | 6 ms | 3072 KB |
021.txt | AC | 43 ms | 7296 KB |