oj.uz

Submission #557293

# Submission time Handle Problem Language Result Execution time Memory
557293 2022-05-05T05:46:02 Z fatemetmhr Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 5000 ms 21972 KB 
//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

ll h[maxn5], c[maxn5];
vector <pair<int, ll>> adj[maxn5];
int a[maxn5], b[maxn5];

inline void dfs(int v, int par){
    for(auto [u, id] : adj[v]) if(u != par){
        h[u] = h[v] + c[id];
        dfs(u, v);
    }
    return;
}

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

 
    ll w;
    int n, q; cin >> n >> q >> w;
 
    for(int i = 0; i < n - 1; i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        adj[a[i]].pb({b[i], i});
        adj[b[i]].pb({a[i], i});
    }

    ll last = 0;

    for(int i = 0; i < q; i++){
        ll d, e; cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;

        c[d] = e;
        h[0] = 0;
        dfs(0, -1);
        int di = 0;
        for(int i = 0; i < n; i++) if(h[i] >= h[di])
            di = i;
        h[di] = 0;
        dfs(di, -1);
        last = 0;
        for(int i = 0; i < n; i++)
            last = max(last, h[i]);
        cout << last << '\n';

    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 9 ms 12100 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12000 KB Output is correct
7 Correct 9 ms 12116 KB Output is correct
8 Correct 8 ms 12084 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 8 ms 11984 KB Output is correct
11 Correct 8 ms 12084 KB Output is correct
12 Correct 7 ms 11996 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Correct 6 ms 11988 KB Output is correct
15 Correct 8 ms 12080 KB Output is correct
16 Correct 7 ms 11988 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Correct 7 ms 11988 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 9 ms 12100 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12000 KB Output is correct
7 Correct 9 ms 12116 KB Output is correct
8 Correct 8 ms 12084 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 8 ms 11984 KB Output is correct
11 Correct 8 ms 12084 KB Output is correct
12 Correct 7 ms 11996 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Correct 6 ms 11988 KB Output is correct
15 Correct 8 ms 12080 KB Output is correct
16 Correct 7 ms 11988 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Correct 7 ms 11988 KB Output is correct
19 Correct 169 ms 12356 KB Output is correct
20 Correct 188 ms 12460 KB Output is correct
21 Correct 171 ms 12244 KB Output is correct
22 Correct 180 ms 12324 KB Output is correct
23 Correct 1289 ms 12716 KB Output is correct
24 Correct 1381 ms 12720 KB Output is correct
25 Correct 1476 ms 12760 KB Output is correct
26 Correct 1412 ms 12932 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 9 ms 12084 KB Output is correct
3 Correct 8 ms 12100 KB Output is correct
4 Correct 18 ms 12288 KB Output is correct
5 Correct 63 ms 13124 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 12088 KB Output is correct
8 Correct 10 ms 12116 KB Output is correct
9 Correct 24 ms 12156 KB Output is correct
10 Correct 187 ms 12324 KB Output is correct
11 Correct 895 ms 13452 KB Output is correct
12 Correct 9 ms 12500 KB Output is correct
13 Correct 29 ms 12500 KB Output is correct
14 Correct 216 ms 12576 KB Output is correct
15 Correct 1735 ms 12908 KB Output is correct
16 Execution timed out 5017 ms 13636 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12116 KB Output is correct
2 Correct 203 ms 12244 KB Output is correct
3 Correct 908 ms 13036 KB Output is correct
4 Correct 1805 ms 13592 KB Output is correct
5 Correct 265 ms 13020 KB Output is correct
6 Correct 2095 ms 13268 KB Output is correct
7 Execution timed out 5048 ms 13552 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 9 ms 12100 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12000 KB Output is correct
7 Correct 9 ms 12116 KB Output is correct
8 Correct 8 ms 12084 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 8 ms 11984 KB Output is correct
11 Correct 8 ms 12084 KB Output is correct
12 Correct 7 ms 11996 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Correct 6 ms 11988 KB Output is correct
15 Correct 8 ms 12080 KB Output is correct
16 Correct 7 ms 11988 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Correct 7 ms 11988 KB Output is correct
19 Correct 169 ms 12356 KB Output is correct
20 Correct 188 ms 12460 KB Output is correct
21 Correct 171 ms 12244 KB Output is correct
22 Correct 180 ms 12324 KB Output is correct
23 Correct 1289 ms 12716 KB Output is correct
24 Correct 1381 ms 12720 KB Output is correct
25 Correct 1476 ms 12760 KB Output is correct
26 Correct 1412 ms 12932 KB Output is correct
27 Correct 7 ms 11988 KB Output is correct
28 Correct 9 ms 12084 KB Output is correct
29 Correct 8 ms 12100 KB Output is correct
30 Correct 18 ms 12288 KB Output is correct
31 Correct 63 ms 13124 KB Output is correct
32 Correct 6 ms 11988 KB Output is correct
33 Correct 7 ms 12088 KB Output is correct
34 Correct 10 ms 12116 KB Output is correct
35 Correct 24 ms 12156 KB Output is correct
36 Correct 187 ms 12324 KB Output is correct
37 Correct 895 ms 13452 KB Output is correct
38 Correct 9 ms 12500 KB Output is correct
39 Correct 29 ms 12500 KB Output is correct
40 Correct 216 ms 12576 KB Output is correct
41 Correct 1735 ms 12908 KB Output is correct
42 Execution timed out 5017 ms 13636 KB Time limit exceeded
43 Halted 0 ms 0 KB -