# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
551369 | 2022-04-20T14:04:16 Z | razvan | Dreaming (IOI13_dreaming) | C++14 | 50 ms | 12364 KB |
#include "dreaming.h" #include <iostream> #include <cstdio> #include <fstream> #include <vector> #include <algorithm> #define pb push_back using namespace std; const int maxn = 100005; struct xy { int x, y; }; vector<xy> v[maxn]; int done[maxn]; int bgst[maxn], ibgst[maxn]; //int ibgst2[maxn]; int now = -1, inow; //int lft, rgh; int ansnow, iansnow; void dfs(int x, int p) { done[x] = true; int big1 = 0, big2 = 0, ibig1 = -1, ibig2 = -1; for(auto u : v[x]) { if(u.x != p) { dfs(u.x, x); if(bgst[u.x] + u.y > big1) { big2 = big1; ibig2 = ibig1; big1 = bgst[u.x] + u.y; ibig1 = u.x; } else if(bgst[u.x] + u.y > big2) { big2 = bgst[u.x] + u.y; ibig2 = u.x; } } } bgst[x] = big1; ibgst[x] = ibig1; //ibgst2[x] = ibig2; if(big1 + big2 > now) { now = big1 + big2; inow = x; } } void dfs2(int x) { if(max(bgst[x], now - bgst[x]) < ansnow) { ansnow = max(bgst[x], now - bgst[x]); iansnow = x; } if(ibgst[x] != -1) dfs2(ibgst[x]); } vector<int> points; int best = -1, ibest; int travelTime(int n, int m, int l, int a[], int b[], int t[]) { int i, j; for(i = 0; i < m; i ++) { v[a[i]].pb({b[i], t[i]}); v[b[i]].pb({a[i], t[i]}); } for(i = 0; i < n; i ++) { if(done[i] == false) { done[i] = true; now = -1; dfs(i, -1); //lft = bgst[inow]; //rgh = now - lft; ansnow = bgst[inow]; iansnow = i; //cout << "now: " << now << ' ' << inow << " " << ansnow << ' ' << iansnow << '\n'; dfs2(ibgst[inow]); //cout << "ansnow: " << ansnow << ' ' << iansnow << '\n'; points.pb(iansnow); if(ansnow > best) { best = ansnow; ibest = iansnow; } } } //cout << "best, ibest: " << best << ' ' << ibest << '\n'; for(auto w : points) { //cout << "point " << w << '\n'; if(w != ibest) { v[ibest].pb({w, l}); v[w].pb({ibest, l}); } } for(i = 0; i < n; i ++) { bgst[i] = ibgst[i] = 0; //ibgst2[i] = 0; } now = -1; dfs(0, -1); return now; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 12364 KB | Output is correct |
2 | Correct | 45 ms | 11944 KB | Output is correct |
3 | Correct | 29 ms | 10688 KB | Output is correct |
4 | Correct | 7 ms | 4020 KB | Output is correct |
5 | Correct | 5 ms | 3412 KB | Output is correct |
6 | Correct | 10 ms | 4692 KB | Output is correct |
7 | Correct | 2 ms | 2644 KB | Output is correct |
8 | Correct | 19 ms | 6608 KB | Output is correct |
9 | Correct | 27 ms | 8960 KB | Output is correct |
10 | Correct | 2 ms | 2644 KB | Output is correct |
11 | Correct | 50 ms | 9492 KB | Output is correct |
12 | Correct | 50 ms | 10944 KB | Output is correct |
13 | Correct | 2 ms | 2644 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2644 KB | Output is correct |
2 | Correct | 2 ms | 2644 KB | Output is correct |
3 | Correct | 1 ms | 2644 KB | Output is correct |
4 | Correct | 2 ms | 2644 KB | Output is correct |
5 | Correct | 2 ms | 2644 KB | Output is correct |
6 | Incorrect | 1 ms | 2644 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 12364 KB | Output is correct |
2 | Correct | 45 ms | 11944 KB | Output is correct |
3 | Correct | 29 ms | 10688 KB | Output is correct |
4 | Correct | 7 ms | 4020 KB | Output is correct |
5 | Correct | 5 ms | 3412 KB | Output is correct |
6 | Correct | 10 ms | 4692 KB | Output is correct |
7 | Correct | 2 ms | 2644 KB | Output is correct |
8 | Correct | 19 ms | 6608 KB | Output is correct |
9 | Correct | 27 ms | 8960 KB | Output is correct |
10 | Correct | 2 ms | 2644 KB | Output is correct |
11 | Correct | 50 ms | 9492 KB | Output is correct |
12 | Correct | 50 ms | 10944 KB | Output is correct |
13 | Correct | 2 ms | 2644 KB | Output is correct |
14 | Correct | 2 ms | 2644 KB | Output is correct |
15 | Correct | 2 ms | 2644 KB | Output is correct |
16 | Correct | 1 ms | 2644 KB | Output is correct |
17 | Correct | 2 ms | 2644 KB | Output is correct |
18 | Correct | 2 ms | 2644 KB | Output is correct |
19 | Incorrect | 1 ms | 2644 KB | Output isn't correct |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 7800 KB | Output is correct |
2 | Correct | 25 ms | 7844 KB | Output is correct |
3 | Correct | 21 ms | 7760 KB | Output is correct |
4 | Correct | 22 ms | 7748 KB | Output is correct |
5 | Correct | 22 ms | 7756 KB | Output is correct |
6 | Correct | 34 ms | 8576 KB | Output is correct |
7 | Correct | 23 ms | 8028 KB | Output is correct |
8 | Correct | 21 ms | 7696 KB | Output is correct |
9 | Correct | 21 ms | 7608 KB | Output is correct |
10 | Correct | 23 ms | 7952 KB | Output is correct |
11 | Correct | 1 ms | 2644 KB | Output is correct |
12 | Correct | 15 ms | 8116 KB | Output is correct |
13 | Correct | 9 ms | 8136 KB | Output is correct |
14 | Correct | 9 ms | 8136 KB | Output is correct |
15 | Correct | 9 ms | 8136 KB | Output is correct |
16 | Correct | 10 ms | 8140 KB | Output is correct |
17 | Correct | 9 ms | 8136 KB | Output is correct |
18 | Correct | 9 ms | 8136 KB | Output is correct |
19 | Correct | 12 ms | 8120 KB | Output is correct |
20 | Correct | 1 ms | 2644 KB | Output is correct |
21 | Correct | 2 ms | 2644 KB | Output is correct |
22 | Correct | 2 ms | 2796 KB | Output is correct |
23 | Correct | 10 ms | 8136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2644 KB | Output is correct |
2 | Correct | 2 ms | 2644 KB | Output is correct |
3 | Correct | 1 ms | 2644 KB | Output is correct |
4 | Correct | 2 ms | 2644 KB | Output is correct |
5 | Correct | 2 ms | 2644 KB | Output is correct |
6 | Incorrect | 1 ms | 2644 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 12364 KB | Output is correct |
2 | Correct | 45 ms | 11944 KB | Output is correct |
3 | Correct | 29 ms | 10688 KB | Output is correct |
4 | Correct | 7 ms | 4020 KB | Output is correct |
5 | Correct | 5 ms | 3412 KB | Output is correct |
6 | Correct | 10 ms | 4692 KB | Output is correct |
7 | Correct | 2 ms | 2644 KB | Output is correct |
8 | Correct | 19 ms | 6608 KB | Output is correct |
9 | Correct | 27 ms | 8960 KB | Output is correct |
10 | Correct | 2 ms | 2644 KB | Output is correct |
11 | Correct | 50 ms | 9492 KB | Output is correct |
12 | Correct | 50 ms | 10944 KB | Output is correct |
13 | Correct | 2 ms | 2644 KB | Output is correct |
14 | Correct | 2 ms | 2644 KB | Output is correct |
15 | Correct | 2 ms | 2644 KB | Output is correct |
16 | Correct | 1 ms | 2644 KB | Output is correct |
17 | Correct | 2 ms | 2644 KB | Output is correct |
18 | Correct | 2 ms | 2644 KB | Output is correct |
19 | Incorrect | 1 ms | 2644 KB | Output isn't correct |
20 | Halted | 0 ms | 0 KB | - |