Submission #2969048
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 | 0 |
Code Size | 1302 Byte |
Status | WA |
Exec Time | 94 ms |
Memory | 8192 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 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 | WA | 63 ms | 6528 KB |
003.txt | WA | 79 ms | 8192 KB |
004.txt | WA | 54 ms | 5504 KB |
005.txt | WA | 81 ms | 8192 KB |
006.txt | WA | 76 ms | 7552 KB |
007.txt | WA | 82 ms | 8192 KB |
008.txt | WA | 57 ms | 5888 KB |
009.txt | WA | 82 ms | 8192 KB |
010.txt | WA | 58 ms | 6016 KB |
011.txt | WA | 83 ms | 8192 KB |
012.txt | WA | 48 ms | 4992 KB |
013.txt | WA | 94 ms | 8192 KB |
014.txt | WA | 37 ms | 3968 KB |
015.txt | WA | 81 ms | 8192 KB |
016.txt | WA | 49 ms | 5120 KB |
017.txt | WA | 82 ms | 8192 KB |
018.txt | WA | 14 ms | 1664 KB |
019.txt | WA | 82 ms | 8192 KB |
020.txt | WA | 8 ms | 1024 KB |
021.txt | WA | 81 ms | 8192 KB |