oj.uz

답안 #276126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
276126 2020-08-20T10:57:47 Z egekabas Dynamic Diameter (CEOI19_diameter) C++14
24 / 100
 5000 ms 27512 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll n, q, w;
pii edge[100009];
vector<ll> g[100009];
map<ll, ll> val[100009];

pii far = {-1e9, -1e9};
void dfs(ll v, ll prt, ll dis){
    far = max(far, {dis, v});
    for(auto u : g[v])
        if(u != prt)
            dfs(u, v, dis+val[v][u]);
}
ll finddia(){
    far = {-1e9, -1e9};
    dfs(1, 0, 0);
    ll cur = far.ss;
    far = {-1e9, -1e9};
    dfs(cur, 0, 0);
    return far.ff;
}
ll last;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> q >> w;
    for(ll i = 0; i < n-1; ++i){
        cin >> edge[i].ff >> edge[i].ss >> val[edge[i].ff][edge[i].ss];
        val[edge[i].ss][edge[i].ff] = val[edge[i].ff][edge[i].ss];
        g[edge[i].ff].pb(edge[i].ss);
        g[edge[i].ss].pb(edge[i].ff);
    }
    while(q--){
        ll d, e;
        cin >> d >> e;
        d = (d+last)%(n-1);
        e = (e+last)%w;
        val[edge[d].ss][edge[d].ff] = val[edge[d].ff][edge[d].ss] = e;
        last = finddia();
        cout << last << '\n';
    }
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 5 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 7 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 6 ms 7424 KB Output is correct
12 Correct 5 ms 7424 KB Output is correct
13 Correct 6 ms 7424 KB Output is correct
14 Correct 6 ms 7424 KB Output is correct
15 Correct 6 ms 7424 KB Output is correct
16 Correct 6 ms 7424 KB Output is correct
17 Correct 6 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 5 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 7 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 6 ms 7424 KB Output is correct
12 Correct 5 ms 7424 KB Output is correct
13 Correct 6 ms 7424 KB Output is correct
14 Correct 6 ms 7424 KB Output is correct
15 Correct 6 ms 7424 KB Output is correct
16 Correct 6 ms 7424 KB Output is correct
17 Correct 6 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct
19 Correct 271 ms 7664 KB Output is correct
20 Correct 275 ms 7704 KB Output is correct
21 Correct 278 ms 7708 KB Output is correct
22 Correct 286 ms 7800 KB Output is correct
23 Correct 2280 ms 8704 KB Output is correct
24 Correct 2310 ms 8600 KB Output is correct
25 Correct 2461 ms 8676 KB Output is correct
26 Correct 2242 ms 9336 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 24 ms 7672 KB Output is correct
5 Correct 86 ms 8568 KB Output is correct
6 Correct 6 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 12 ms 7456 KB Output is correct
9 Correct 66 ms 7552 KB Output is correct
10 Correct 726 ms 7800 KB Output is correct
11 Correct 3089 ms 8844 KB Output is correct
12 Correct 22 ms 8320 KB Output is correct
13 Correct 130 ms 8320 KB Output is correct
14 Correct 1265 ms 8316 KB Output is correct
15 Execution timed out 5041 ms 8720 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 7552 KB Output is correct
2 Correct 283 ms 7680 KB Output is correct
3 Correct 1401 ms 8264 KB Output is correct
4 Correct 2903 ms 9152 KB Output is correct
5 Correct 314 ms 9440 KB Output is correct
6 Correct 3053 ms 9696 KB Output is correct
7 Execution timed out 5094 ms 9748 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5075 ms 27512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 5 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 7 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 6 ms 7424 KB Output is correct
12 Correct 5 ms 7424 KB Output is correct
13 Correct 6 ms 7424 KB Output is correct
14 Correct 6 ms 7424 KB Output is correct
15 Correct 6 ms 7424 KB Output is correct
16 Correct 6 ms 7424 KB Output is correct
17 Correct 6 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct
19 Correct 271 ms 7664 KB Output is correct
20 Correct 275 ms 7704 KB Output is correct
21 Correct 278 ms 7708 KB Output is correct
22 Correct 286 ms 7800 KB Output is correct
23 Correct 2280 ms 8704 KB Output is correct
24 Correct 2310 ms 8600 KB Output is correct
25 Correct 2461 ms 8676 KB Output is correct
26 Correct 2242 ms 9336 KB Output is correct
27 Correct 5 ms 7424 KB Output is correct
28 Correct 5 ms 7424 KB Output is correct
29 Correct 7 ms 7424 KB Output is correct
30 Correct 24 ms 7672 KB Output is correct
31 Correct 86 ms 8568 KB Output is correct
32 Correct 6 ms 7424 KB Output is correct
33 Correct 6 ms 7424 KB Output is correct
34 Correct 12 ms 7456 KB Output is correct
35 Correct 66 ms 7552 KB Output is correct
36 Correct 726 ms 7800 KB Output is correct
37 Correct 3089 ms 8844 KB Output is correct
38 Correct 22 ms 8320 KB Output is correct
39 Correct 130 ms 8320 KB Output is correct
40 Correct 1265 ms 8316 KB Output is correct
41 Execution timed out 5041 ms 8720 KB Time limit exceeded
42 Halted 0 ms 0 KB -