oj.uz

Submission #594575

# Submission time Handle Problem Language Result Execution time Memory
594575 2022-07-12T17:04:23 Z penguinhacker Dynamic Diameter (CEOI19_diameter) C++17
11 / 100
 5000 ms 11896 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, q, eu[mxN], ev[mxN];
ll wlim, ew[mxN];
vector<int> adj[mxN];
vector<ll> st;

void dfs(int u=0, int p=-1, ll d=0) {
	st.push_back(d);
	for (int e : adj[u]) {
		int v=eu[e]^ev[e]^u;
		if (v!=p) {
			dfs(v, u, d+ew[e]);
			st.push_back(d);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> wlim;
	for (int i=0; i<n-1; ++i) {
		cin >> eu[i] >> ev[i] >> ew[i], --eu[i], --ev[i];
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	ll ans=0;
	while(q--) {
		int i;
		ll nxt;
		cin >> i >> nxt;
		i=(i+ans)%(n-1);
		nxt=(nxt+ans)%wlim;
		ew[i]=nxt;

		st.clear();
		dfs();
		assert(st.size()==2*n-1);

		ans=0;
		for (int i=0; i<2*n-1; ++i) {
			ll mn=3e18;
			for (int j=i; j<2*n-1; ++j) {
				mn=min(mn, st[j]);
				ans=max(ans, st[i]+st[j]-2*mn);
			}
			//cout << st[i] << " ";
		}
		//cout << endl;

		cout << ans << "\n";
	}
	return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from diameter.cpp:1:
diameter.cpp: In function 'int main()':
diameter.cpp:44:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |   assert(st.size()==2*n-1);
      |          ~~~~~~~~~^~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 1 ms 2676 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2676 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 4 ms 2644 KB Output is correct
13 Correct 5 ms 2644 KB Output is correct
14 Correct 5 ms 2680 KB Output is correct
15 Correct 6 ms 2680 KB Output is correct
16 Correct 4 ms 2676 KB Output is correct
17 Correct 4 ms 2644 KB Output is correct
18 Correct 7 ms 2644 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 1 ms 2676 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2676 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 4 ms 2644 KB Output is correct
13 Correct 5 ms 2644 KB Output is correct
14 Correct 5 ms 2680 KB Output is correct
15 Correct 6 ms 2680 KB Output is correct
16 Correct 4 ms 2676 KB Output is correct
17 Correct 4 ms 2644 KB Output is correct
18 Correct 7 ms 2644 KB Output is correct
19 Execution timed out 5024 ms 2812 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 6 ms 2672 KB Output is correct
4 Correct 35 ms 2868 KB Output is correct
5 Correct 173 ms 3792 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 16 ms 2644 KB Output is correct
8 Correct 150 ms 2716 KB Output is correct
9 Correct 1463 ms 2732 KB Output is correct
10 Execution timed out 5094 ms 2912 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2826 ms 2772 KB Output is correct
2 Execution timed out 5044 ms 2856 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5092 ms 11896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 1 ms 2676 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2676 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 4 ms 2644 KB Output is correct
13 Correct 5 ms 2644 KB Output is correct
14 Correct 5 ms 2680 KB Output is correct
15 Correct 6 ms 2680 KB Output is correct
16 Correct 4 ms 2676 KB Output is correct
17 Correct 4 ms 2644 KB Output is correct
18 Correct 7 ms 2644 KB Output is correct
19 Execution timed out 5024 ms 2812 KB Time limit exceeded
20 Halted 0 ms 0 KB -