codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; vector <int> level, vert, tr, ind, a; vector <vector <int> > g; int Min(int x, int y) { return (level[x] < level[y]? x: y); } void init(vector <int>& t, vector <int> ver) { t.resize(ver.size() * 2 + 2); for(int i = ver.size(); i < 2 * ver.size(); i++) t[i] = ver[i - ver.size()]; for(int i = ver.size() - 1; i > 0; i--) t[i] = Min(t[2 * i], t[2 * i + 1]); } int fndMin(int l, int r) { if (l > r) swap(l, r); l += vert.size(); r += vert.size(); int mini = l - vert.size(); while (l <= r) { if (l & 1) { mini = Min(mini, tr[l]); l++; } if (!(r&1)) { mini = Min(mini, tr[r]); r--; } l >>= 1; r >>= 1; } return mini; } void dfs(int v, int pr, int lev) { level[v] = lev; vert.push_back(v); ind[v] = vert.size() - 1; for(int i = 0; i < g[v].size(); i++) if (pr != g[v][i]) { dfs(g[v][i], v, lev + 1); vert.push_back(v); } } int main() { int n, m, v; cin >> n >> m; g.resize(n + 1); level.resize(n + 1); ind.resize(n + 1); a.resize(2 * m + 2); for(int i = 1; i < n; i++) { scanf("%d", &v); g[i].push_back(v); g[v].push_back(i); } dfs(0, -1, 0); init(tr, vert); cin >> a[1] >> a[2]; long long x, y, z, ans = 0; v = 0; cin >> x >> y >> z; for(int i = 3; i <= 2 * m; i++) a[i] = (x * a[i - 2] + y * a[i - 1] + z) % n; for(int i = 1; i <= m; i++) { v = fndMin(ind[(a[2 * i - 1] + v) % n], ind[a[2 * i]]); ans += v; } cout << ans << endl; return 0; }
Private
[
?
]
Run code
Submit