假算法过题
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<string> #include<map> #include<set> #include<queue> #include<iomanip> #include<stack> using namespace std; #define STDIN freopen("in.in", "r", stdin);freopen("out.out", "w", stdout); const int N = 1e5 + 10; int n; double z, r; double v[N]; double v1[N]; int main() { STDIN cin >> n >> z >> r; v[0] = z; double sum = 0; double sum2 = 0; bool flag = false; for (int i = 0; i < n; i++) { int x; cin >> x; if (x == 0) { double t; cin >> t; sum += v[i]*(t);sum2 += v[i]*(t+1); v[i] = v[i]*(t);v1[i] = v1[i]*(t+1); if (v[i] == 0) flag = true; // cout << i << " " <<v[i] << endl; } else for (int j = 1; j <= x; j++) { int t; cin >> t; v[t] = v[i]*(1-r*0.01); v1[t] = v1[i]*(1-r*0.01); } } if (flag) printf("%lld ", (long long)sum2); else printf("%lld ", (long long)sum); }
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<string> #include<map> #include<set> #include<queue> #include<iomanip> #include<stack> using namespace std; #define STDIN freopen("in.in", "r", stdin);freopen("out.out", "w", stdout); const int N = 1e5 + 10; int n;double z, r; int h[N], e[N<<1], ne[N<<1], idx; double bei[N]; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } double sum = 0; void dfs(int u, double v) { if (bei[u] != 0) sum += bei[u]*v; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; dfs(j, v*(1-r*0.01)); } } int main() { // STDIN memset(h, -1, sizeof h); cin >> n >> z >> r; for (int i = 0; i < n; i++) { int x; cin >> x; if (x == 0) { cin >> bei[i]; } else for (int j = 1; j <= x; j++) { int t; cin >> t; add(i, t); } } dfs(0, z); printf("%lld", (long long) sum); }