oj.uz

Submission #398531

# Submission time Handle Problem Language Result Execution time Memory
398531 2021-05-04T13:24:51 Z model_code Arboras (RMI20_arboras) C++17
100 / 100
 342 ms 24964 KB 
/**
* user:  loginov-0a5
* fname: Igor
* lname: Loginov
* task:  Arboras
* score: 100.0
* date:  2020-12-04 12:01:41.831192
*/
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int MOD = 1e9 + 7;
const int N = 101000;

int n;

int et[N], T;

vector<vector<pair<int, long long> > > g;

void dfs0(int v)
{
    et[v] = T++;
    for (auto u : g[v]) dfs0(u.first);
}

int p[N];
long long len[N];
int id[N];

long long d2[N];

int children[N]; // next vertex in the path
int path_id[N]; // where vertex V is located (probably, HLD is needed)
vector<int> path_root; // root of each path
int depth[N]; // distance from root to V in edges
//long long h[N]; // distance from root to V in metres (segment tree)
long long cur1, cur2; // current answers
long long go[N]; // longest path from V in metres, path_root[path_id[V]] == V must holds

long long tree1[4 * N];
long long push1[4 * N];

void Push1(int V)
{
	push1[2 * V + 1] += push1[V];
	push1[2 * V + 2] += push1[V];
	tree1[2 * V + 1] += push1[V];
	tree1[2 * V + 2] += push1[V];
	push1[V] = 0;
}

long long geth(int pos, int L = 0, int R = N, int V = 0)
{
	if (L + 1 == R)
	{
        return tree1[V];
	}
	Push1(V);
	int M = (L + R) / 2;
	if (pos < M) return geth(pos, L, M, 2 * V + 1);
	else return geth(pos, M, R, 2 * V + 2);
}

void addh(int l, int r, long long x, int L = 0, int R = N, int V = 0)
{
	if (R <= l || r <= L) return;
	if (l <= L && R <= r)
	{
		push1[V] += x;
		tree1[V] += x;
		return;
	}
	int M = (L + R) / 2;
	Push1(V);
	addh(l, r, x, L, M, 2 * V + 1);
	addh(l, r, x, M, R, 2 * V + 2);
}

int lst[N];

void dfs(int v, int D, long long H)
{
	depth[v] = D;
	addh(v, v + 1, H);
	long long fnd = 0, fnd2 = 0;
	int mxid = -1;
	lst[v] = v;
	for (auto id : g[v])
	{
		int u = id.first;
		long long w = id.second;
		dfs(u, D + 1, H + w);
		lst[v] = lst[u];
		if (mxid == -1 || go[u] + w > fnd)
        {
            mxid = u;
            fnd2 = fnd;
            fnd = go[u] + w;
        }
        else if (go[u] + w > fnd2)
        {
            fnd2 = go[u] + w;
        }
	}
	d2[v] = fnd2;
	cur2 = (cur2 + fnd2) % MOD;
	//cout << v << " " << mxid << endl;
	if (mxid == -1)
	{
		path_id[v] = path_root.size();
		path_root.push_back(v);
	}
	else
	{
		children[v] = mxid;
		go[v] = go[mxid] + len[mxid];
		path_id[v] = path_id[mxid];
		path_root[path_id[mxid]] = v;
	}
	cur1 = (cur1 + go[v]) % MOD;
}

int get_root(int v)
{
	return path_root[path_id[v]];
}

long long get_actual(int v) // returns correct value of go[v]
{
	int P = get_root(v);
	long long dist = geth(v) - geth(P);
	return go[P] - dist;
}

void update(int v, long long length, int direction)
{
    //cout << v << " " << length << " " << direction << endl;
	if (path_id[direction] == path_id[v])
	{
		long long delta = length - get_actual(v);
		long long P = get_root(v);
		cur1 = (cur1 + (depth[v] - depth[P] + 1) * delta) % MOD;
		go[P] += delta;
		if (P != 0)
		{
			update(p[P], get_actual(P) + len[P], P);
		}
	}
	else
	{
		long long we = get_actual(v);
		if (we >= length)
		{
		    if (length >= d2[v])
		    {
		        cur2 = (cur2 - d2[v] + length) % MOD;
                d2[v] = length;
		    }
		    return;
		}
		int P = get_root(v);
		cur2 = (cur2 - d2[v] + we) % MOD;
		d2[v] = we;
		int nid = path_id[direction];
		go[children[v]] = get_actual(children[v]);
		path_root[path_id[children[v]]] = children[v];
		children[v] = direction;
		//cout << children[v] << " " << direction << " " << get_root(v) << " " << P << endl;
		{
			int kek = v;
			while (1)
            {
                path_id[kek] = nid;
                if (kek == P) break;
                kek = p[kek];
            }
            path_root[path_id[kek]] = kek;
		}
		long long delta = length - we;
		cur1 = (cur1 + (depth[v] - depth[P] + 1) * delta) % MOD;
		go[P] += delta;
		if (P != 0)
		{
			update(p[P], get_actual(P) + len[P], P);
		}
	}
}

void ans()
{
    long long A = cur1;
    for (int i = 0; i < n; i++)
    {
        long long mx1 = 0, mx2 = 0;
        for (auto id : g[i])
        {
            long long Len = get_actual(id.first) + len[id.first];
            if (Len > mx1)
            {
                mx2 = mx1;
                mx1 = Len;
            }
            else if (Len > mx2)
            {
                mx2 = Len;
            }
        }
        A = (A + mx2) % MOD;
    }
    cout << A << "\n";
}

/*
5
0 0 1 1
0 0 0 0
10
1 2
2 2
3 2
4 2
4 1
3 1
2 1
1 1
4 1000
2 1000

7
0 1 1 3 3 4
100000000 100000000 100000000 100000000 100000000 100000000
10
5 1
4 3
6 5
1 1
3 10000000
5 1000000
3 4
1 100000000
4 1000000000
6 100000

7
0 1 1 3 3 4
10 10 10 10 10 10
6
5 1
4 1
6 1
1 1
3 100
5 100

8
0 0 2 0 2 4 3
0
*/

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	g = vector<vector<pair<int, long long> > >(n);
	for (int i = 1; i < n; i++)
	{
		cin >> p[i];
		g[p[i]].push_back({i, 0});
	}
    dfs0(0);
    vector<int> zz(n);
    for (int i = 1; i < n; i++)
    {
        zz[i] = p[i];
    }
    for (int i = 1; i < n; i++)
    {
        p[et[i]] = et[zz[i]];
    }
    for (int i = 1; i < n; i++)
    {
        cin >> zz[i];
        //zz[i] = 100000000 - i;
    }
    for (int i = 1; i < n; i++)
    {
        len[et[i]] = zz[i];
    }
	g = vector<vector<pair<int, long long> > >(n);
	for (int i = 1; i < n; i++)
	{
		id[i] = g[p[i]].size();
		g[p[i]].push_back({i, len[i]});
	}
	dfs(0, 0, 0);

	/*
	for (int i = 0; i < n; i++)
	{
	    cout << get_actual(i) << " ";
	}

	cout << cur1 << "\n";
	//*/

	cout << (cur1 + cur2) % MOD << "\n";

	int q;
	cin >> q;
	while (q--)
	{
		int v, add;
		cin >> v >> add;
		//v = rand() % n;
		//add = 1;

		v = et[v];
		g[p[v]][id[v]].second += add;

		long long g = get_actual(v);

		len[v] += add;

		//cout << v << " " << lst[v] << "\n";
		addh(v, lst[v] + 1, add);

		update(p[v], g + len[v], v);

		/*
        for (int j = 0; j < n; j++)
        {
            cout << path_id[j] << " ";
        }
        cout << "\n";
        for (int j = 0; j < path_root.size(); j++)
        {
            cout << path_root[j] << " ";
        }
        cout << "\n";
        for (int j = 0; j < n; j++)
        {
            cout << go[j] << " ";
        }
        cout << "\n";
        for (int j = 0; j < n; j++)
        {
            cout << geth(j) << " ";
        }
        cout << "\n";
        //*/
        /*
		for (int j = 0; j < n; j++)
		{
		    cout << get_actual(j) << " ";
		}

		cout << "\n";

		cout << cur1 << "\n";
		//*/
		cout << (cur1 + cur2) % MOD << "\n";
		//ans();
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 3 ms 588 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 19808 KB Output is correct
2 Correct 208 ms 19280 KB Output is correct
3 Correct 229 ms 18400 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 21772 KB Output is correct
2 Correct 227 ms 24860 KB Output is correct
3 Correct 342 ms 20312 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 338 ms 19808 KB Output is correct
5 Correct 208 ms 19280 KB Output is correct
6 Correct 229 ms 18400 KB Output is correct
7 Correct 268 ms 21772 KB Output is correct
8 Correct 227 ms 24860 KB Output is correct
9 Correct 342 ms 20312 KB Output is correct
10 Correct 299 ms 21788 KB Output is correct
11 Correct 246 ms 24948 KB Output is correct
12 Correct 226 ms 20380 KB Output is correct
13 Correct 174 ms 23792 KB Output is correct
14 Correct 166 ms 24964 KB Output is correct