제출 #373749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373749		LucaDantas	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	2177 ms	22496 KiB

diameter

#include<bits/stdc++.h>
using namespace std;

constexpr int maxn = 4e5+10;

vector<pair<int,int>> g[maxn];

pair<int,int> back[maxn];

int n, q;
int dist[maxn], cost[maxn], w;

void dfs(int u, int p) {
	for(auto [v, id] : g[u]) {
		if(v != p) {
			dist[v] = dist[u] + cost[id];
			dfs(v, u);
		}
	}
}

void brute() {
	int last = 0;
	while(q--) {
		int d, e; scanf("%d %d", &d, &e);
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		cost[d] = e;
		dist[1] = 0;
		dfs(1, 0);
		int x = (int)(max_element(dist+1, dist+n+1) - dist);
		dist[x] = 0;
		dfs(x, 0);
		printf("%d\n", *max_element(dist+1, dist+n+1));
		last = *max_element(dist+1, dist+n+1);
	}
	exit(0);
}

void bst() {
	multiset<int, greater<int>> st;
	for(int i = 0; i < n-1; i++)
		st.insert(cost[i]);
	int last = 0;
	while(q--) {
		int d, e; scanf("%d %d", &d, &e);
		d = (int)((d + last) % (n - 1));
		e = (int)((e + last) % w);
		st.erase(st.find(cost[d]));
		cost[d] = e;
		st.insert(e);
		last = (int)(*st.begin() + (n>2?*next(st.begin()):0));
		printf("%d\n", last);
	}
	exit(0);
}

struct SegmentTree
{
	pair<int,int> tree[maxn], G[maxn];
	void build(int node) {		
		sort(g[node].begin(), g[node].end());
		reverse(g[node].begin(), g[node].end());
		if(g[node].size() == 3 || (g[node].size() == 2 && node>1) || g[node].size() == 1)
			g[node].pop_back();
		reverse(g[node].begin(), g[node].end());

		// printf("%d == ", node);
		// for(auto x : g[node])
		// 	printf("%d ", x.first);
		// printf("\n");

		if(g[node].size()) {
			G[node].first = g[node][0].second;
			assert(g[node][0].first == 2*node);
			build(node<<1);
		}
		else G[node].first = maxn-10;

		if(g[node].size() > 1) {
			G[node].second = g[node][1].second;
			assert(g[node][1].first == 2*node+1);
			build(node<<1|1);
		}
		else G[node].second = maxn-10;

		int vl = tree[2*node].first + cost[G[node].first],
		vr = tree[2*node+1].first + cost[G[node].second];
		tree[node] = {max(vl, vr),
			max({vl+vr, tree[2*node].second, tree[2*node+1].second})};

		// printf("%d %d %d\n", node, tree[node].first, tree[node].second);
	}
	void upd(int node) {
		int vl = tree[2*node].first + cost[G[node].first],
		vr = tree[2*node+1].first + cost[G[node].second];
		tree[node] = {max(vl, vr),
			max({vl+vr, tree[2*node].second, tree[2*node+1].second})};
		if(node != 1) upd(node>>1);
	}
	int query() { return tree[1].second; }
} seg;

void solve_seg() {
	seg.build(1);
	// printf("%d\n", seg.query());
	int last = 0;
	while(q--) {
		int d, e; scanf("%d %d", &d, &e);
		d = (int)((d + last) % (n - 1));
		e = (int)((e + last) % w);
		cost[d] = e;
		auto [a, b] = back[d];
		if(a > b) swap(a, b);
		seg.upd(a);
		last = seg.query();
		printf("%d\n", last);
	}
}

int main() {
	scanf("%d %d %d", &n, &q, &w);
	// printf("%d %d %d\n", n, q, w);
	if(w > 10000) assert(0);
	for(int i = 0; i < n-1; i++) {
		int a, b; int c; scanf("%d %d %d", &a, &b, &c);
		// printf("%d %d %d\n", a, b, c);
		g[a].push_back({b, i});
		g[b].push_back({a, i});
		cost[i] = c;
		back[i] = {a, b};
	}
	if((int)g[1].size() == n-1) bst();
	if(n <= 5000) brute();
	solve_seg();
}

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

diameter.cpp: In function 'void brute()':
diameter.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   int d, e; scanf("%d %d", &d, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void bst()':
diameter.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |   int d, e; scanf("%d %d", &d, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void solve_seg()':
diameter.cpp:109:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |   int d, e; scanf("%d %d", &d, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  122 |  scanf("%d %d %d", &n, &q, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:126:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |   int a, b; int c; scanf("%d %d %d", &a, &b, &c);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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