Submission #2969079
Source Code Expand
#include <iostream> #include <algorithm> #include <vector> #include <cstring> using namespace std; using ll = long long; constexpr int mod = 1e9 + 7; constexpr int lim = 1e5; bool visited[lim+1]; ll f[lim+1], g[lim+1]; int n; class edge{ public: int to; edge(int t){ to = t; } }; class graph{ public: vector<vector<edge>> v; graph(int n){ v.resize(n+1); } }; void visit(const graph& gr, int v, int from){ bool nxt = false; for(int i=0; i<gr.v[v].size(); i++){ int to = gr.v[v][i].to; if(!visited[to]){ visited[to] = true; nxt = true; visit(gr, to, v); } } if(nxt){ f[v] = 1; g[v] = 1; for(int i=0; i<gr.v[v].size(); i++){ int to = gr.v[v][i].to; if(to == from) continue; (g[v] *= f[to]) %= mod; (f[v] *= g[to]) %= mod; } (f[v] += g[v]) %= mod; } else{ f[v] = 2; g[v] = 1; } } ll solve(const graph& g){ visited[1] = true; visit(g, 1, -1); return f[1]; } int main(){ cin >> n; graph gr(n); int a[n], b[n]; for(int i=1; i<n; i++){ cin >> a[i] >> b[i]; gr.v[a[i]].push_back({b[i]}); gr.v[b[i]].push_back({a[i]}); } ll ans = solve(gr); cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 塗り絵 |
User | kobajin |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1308 Byte |
Status | AC |
Exec Time | 82 ms |
Memory | 8192 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 | 1 ms | 256 KB |
001.txt | AC | 1 ms | 256 KB |
002.txt | AC | 63 ms | 6528 KB |
003.txt | AC | 82 ms | 8192 KB |
004.txt | AC | 53 ms | 5504 KB |
005.txt | AC | 82 ms | 8192 KB |
006.txt | AC | 75 ms | 7552 KB |
007.txt | AC | 82 ms | 8192 KB |
008.txt | AC | 57 ms | 5888 KB |
009.txt | AC | 82 ms | 8192 KB |
010.txt | AC | 58 ms | 6016 KB |
011.txt | AC | 82 ms | 8192 KB |
012.txt | AC | 48 ms | 4992 KB |
013.txt | AC | 81 ms | 8192 KB |
014.txt | AC | 37 ms | 3968 KB |
015.txt | AC | 81 ms | 8192 KB |
016.txt | AC | 49 ms | 5120 KB |
017.txt | AC | 82 ms | 8192 KB |
018.txt | AC | 14 ms | 1664 KB |
019.txt | AC | 81 ms | 8192 KB |
020.txt | AC | 8 ms | 1024 KB |
021.txt | AC | 82 ms | 8192 KB |