제출 #200002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
200002		davitmarg	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5067 ms	470792 KiB

diameter

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

void fastscan(int& number)
{
	//variable to indicate sign of input number
	bool negative = false;
	register int c;

	number = 0;

	// extract current character from buffer
	c = getchar();
	while (c == 10)
		c = getchar();
	if (c == '-')
	{
		// number is negative
		negative = true;

		// extract the next character from the buffer
		c = getchar();
	}

	// Keep on extracting characters if they are integers
	// i.e ASCII Value lies from '0'(48) to '9' (57)
	for (; (c > 47 && c < 58); c = getchar())
		number = number * 10 + c - 48;

	// if scanned input has a negative sign, negate the
	// value of the input number
	if (negative)
		number *= -1;
}

struct segtree
{
	vector<LL> d;
	vector<pair<LL, int>> t;

	void build(int v, int l, int r, vector<int>& a, vector<LL>& D, unordered_map<int, int>& b)
	{
		if (l == r)
		{
			t[v].first = D[a[l]];
			t[v].second = b[a[l]];
			d[v] = 0;
			return;
		}
		int m = (l + r) / 2;
		build(v * 2, l, m, a, D, b);
		build(v * 2 + 1, m + 1, r, a, D, b);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}

	segtree(int n = 0)
	{
		t.resize(n * 4 + 5);
		d.resize(n * 4 + 5);
	}

	segtree(vector<int>& a, vector<LL>& D, unordered_map<int, int>& b)
	{
		t.resize(a.size() * 4 + 5);
		d.resize(a.size() * 4 + 5);
		build(1, 0, a.size() - 1, a, D, b);
	}

	void push(int v, int l, int r, int f = 1)
	{
		if (d[v] == 0)
			return;
		if (l != r)
		{
			int m = (l + r) / 2;
			d[v * 2] += d[v];
			d[v * 2 + 1] += d[v];
			if (f)
			{
				push(v * 2, l, m, 0);
				push(v * 2 + 1, m + 1, r, 0);
			}
		}
		t[v].first += d[v];
		d[v] = 0;
	}

	pair<LL, int> get(int v, int l, int r, int i, int j)
	{
		push(v, l, r);
		if (i > j)
			return MP(0, 0);
		if (l == i && r == j)
			return t[v];
		int m = (l + r) / 2;
		return max(
			get(v * 2, l, m, i, min(j, m)),
			get(v * 2 + 1, m + 1, r, max(i, m + 1), j)
		);
	}

	void add(int v, int l, int r, int i, int j, LL val)
	{
		push(v, l, r);
		if (i > j)
			return;
		if (l == i && r == j)
		{
			d[v] += val;
			push(v, l, r);
			return;
		}
		int m = (l + r) / 2;
		add(v * 2, l, m, i, min(j, m), val);
		add(v * 2 + 1, m + 1, r, max(i, m + 1), j, val);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}

};

LL n, q;
LL W, w[100005], sz[100005], used[100005], color[100005], col, ans;
vector<LL> d(100005);
vector<pair<int, int>> g[100005];
vector<int> ord[100005];
segtree seg[100005];
unordered_map<int, int> subtree[100005], tin[100005], tout[100005], pos[100005], centr[100005];
multiset<LL> best;
void dfsSize(int v, int p)
{
	color[v] = col;
	sz[v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		if (used[to] || to == p)
			continue;
		dfsSize(to, v);
		sz[v] += sz[to];
	}
}

int centroid(int v)
{
	col++;
	dfsSize(v, 0);
	col++;
	queue<int> q;
	q.push(v);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		color[x] = col;
		bool is = (sz[v] >= (sz[v] - sz[x]) * 2);
		for (int i = 0; i < g[x].size(); i++)
		{
			int to = g[x][i].first;
			if (color[to] == col || used[to])
				continue;
			q.push(to);
			is &= (sz[v] >= sz[to] * 2);
		}

		if (is)
			return x;
	}
}

void dfs(int Centr, int Sub, int v, int p, LL dist)
{
	d[v] = dist;
	subtree[Centr][v] = Sub;
	ord[Centr].PB(v);
	tin[Centr][v] = ord[Centr].size() - 1;

	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		int d = g[v][i].second;
		if (to == p || used[to])
			continue;
		pos[Centr][d] = to;
		dfs(Centr, Sub, to, v, dist + w[d]);
	}

	tout[Centr][v] = ord[Centr].size() - 1;

}

LL getMax(int v)
{
	pair<LL, LL> mx1, mx2;
	mx1 = seg[v].get(1, 0, ord[v].size() - 1, 0, ord[v].size() - 1);
	if (mx1.first == 0)
		return 0;
	mx2 = max(
		seg[v].get(1, 0, ord[v].size() - 1, 0, tin[v][mx1.second] - 1),
		seg[v].get(1, 0, ord[v].size() - 1, tout[v][mx1.second] + 1, ord[v].size() - 1)
	);
	return mx1.first + mx2.first;
}


void calc(int v)
{
	used[v] = 1;
	ord[v].PB(v);
	tin[v][v] = ord[v].size() - 1;
	d[v] = 0;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		int d = g[v][i].second;
		if (used[to])
			continue;
		pos[v][d] = to;
		dfs(v, to, to, v, w[d]);
	}
	tout[v][v] = ord[v].size() - 1;
	seg[v] = segtree(ord[v], d, subtree[v]);


	LL mx = getMax(v);
	//cout<<"!!!"<<v<<" > "<<mx<<endl;
	best.insert(mx);

	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		if (used[to])
			continue;
		calc(centr[v][to] = centroid(to));
	}
}

void solve(int v, int P, LL val)
{
	if (pos[v].find(P) == pos[v].end())
		return;
	int p = pos[v][P];


	LL mx;
	mx = getMax(v);
	//cout<<"!!"<<v<<" > "<<mx<<endl;
	best.erase(best.find(mx));
	seg[v].add(1, 0, ord[v].size() - 1, tin[v][p], tout[v][p], val);


	mx = getMax(v);
	//cout<<"!"<<v<<" > "<<mx<<endl;

	best.insert(mx);
	solve(centr[v][subtree[v][p]], P, val);
}
int main()
{
	cin >> n >> q >> W;
	for (int i = 1; i <= n - 1; i++)
	{
		int a, b,ww;
		
		fastscan(a);
		fastscan(b);
		fastscan(ww);
		w[i] = ww;
		g[a].PB(MP(b, i));
		g[b].PB(MP(a, i));
	}
	calc(centr[0][1] = centroid(1));
	while (q--)
	{
		int p;
		int D;
		fastscan(p);
		fastscan(D);
		p = (p + ans) % (n - 1);
		D = (D + ans) % W;
		p++;
		solve(centr[0][1], p, D - w[p]);
		w[p] = D;

		if (!best.empty())
		{
			auto it = best.end();
			--it;
			ans = (*it);
		}
		else
			ans = 0;

		printf("%lld\n", ans);
	}

	return 0;
}

/*

7 1 1000
1 2 10
2 3 1
2 4 1
1 5 1
5 6 1
5 7 1
0 1


*/

컴파일 시 표준 에러 (stderr) 메시지

diameter.cpp: In function 'void fastscan(int&)':
diameter.cpp:30:15: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
  register int c;
               ^
diameter.cpp: In function 'void dfsSize(int, int)':
diameter.cpp:155:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
diameter.cpp: In function 'int centroid(int)':
diameter.cpp:178:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < g[x].size(); i++)
                   ~~^~~~~~~~~~~~~
diameter.cpp: In function 'void dfs(int, int, int, int, long long int)':
diameter.cpp:199:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
diameter.cpp: In function 'void calc(int)':
diameter.cpp:233:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
diameter.cpp:250:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
diameter.cpp: In function 'int centroid(int)':
diameter.cpp:190:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27