oj.uz

Submission #922468

# Submission time Handle Problem Language Result Execution time Memory
922468 2024-02-05T14:29:40 Z SNP011 Dynamic Diameter (CEOI19_diameter) C++17
11 / 100
 5000 ms 22848 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long int
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define u_map unordered_map
#define int ll
const int maxn = 1e5 + 5, mod = 1e9 + 7;

vector<int> adj[maxn];
map<pii, int> we;
int mx, far, lastans;

void dfs(int v, int par = 0, int h = 0) {
	if (h > mx) {
		far = v;
		mx = h;
	}
	for (int u: adj[v]) {
		if (u != par) {
			dfs(u, v, h + we[{u, v}]);
		}
	}
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q, w;
    cin >> n >> q >> w;
    vector<pii> edge;
    for (int i = 1; i < n; i++) {
    	int u, v, w;
    	cin >> u >> v >> w;
    	adj[v].pb(u);
    	adj[u].pb(v);
    	we[{u, v}] = w;
    	we[{v, u}] = w;
    	edge.pb({u, v});
    }
    while (q--) {
    	int d, e;
    	cin >> d >> e;
		d = (d + lastans) % (n - 1);
		e = (e + lastans) % w;
    	we[{edge[d].first, edge[d].second}] = e;
    	we[{edge[d].second, edge[d].first}] = e;
    	mx = 0;
    	dfs(1);
    	int dia = far;
    	mx = 0;
    	dfs(far);
    	cout << mx << '\n';
    	lastans = mx;
    }

    return 0;
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:55:10: warning: unused variable 'dia' [-Wunused-variable]
   55 |      int dia = far;
      |          ^~~

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2812 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 2 ms 2648 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 474 ms 3284 KB Output is correct
20 Correct 503 ms 3056 KB Output is correct
21 Correct 600 ms 3076 KB Output is correct
22 Correct 810 ms 3112 KB Output is correct
23 Execution timed out 5029 ms 4072 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 19 ms 2956 KB Output is correct
5 Correct 67 ms 3924 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 5 ms 2904 KB Output is correct
9 Correct 47 ms 2908 KB Output is correct
10 Correct 373 ms 3016 KB Output is correct
11 Correct 1917 ms 4432 KB Output is correct
12 Correct 14 ms 3676 KB Output is correct
13 Correct 114 ms 3676 KB Output is correct
14 Correct 1119 ms 4032 KB Output is correct
15 Execution timed out 5038 ms 4228 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2904 KB Output is correct
2 Correct 717 ms 3068 KB Output is correct
3 Correct 3558 ms 3860 KB Output is correct
4 Execution timed out 5049 ms 4176 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2812 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 2 ms 2648 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 474 ms 3284 KB Output is correct
20 Correct 503 ms 3056 KB Output is correct
21 Correct 600 ms 3076 KB Output is correct
22 Correct 810 ms 3112 KB Output is correct
23 Execution timed out 5029 ms 4072 KB Time limit exceeded
24 Halted 0 ms 0 KB -