oj.uz

Submission #282185

# Submission time Handle Problem Language Result Execution time Memory
282185 2020-08-24T06:03:29 Z kevlee Dreaming (IOI13_dreaming) C++17
14 / 100
 109 ms 16964 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a));
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
int dist[100005], dpup[100005], dpdown[100005], n, m, l, diameter, furthest, ans, maxchild[100005], secondmax[100005];
vp edges[100005];
vi v, comp;
bool vis[100005];
void dfs(int x, int p) {
 if (dist[x] > diameter) {
   diameter = dist[x];
   furthest = x;
 }
  vis[x] = true;
  v.pb(x);
  for (auto edge: edges[x]) {
    if (edge.fi != p) {
      dist[edge.fi] = dist[x] + edge.se;
      dfs(edge.fi, x);
    }
  }
}
int find_diameter(int root) {
  dist[root] = 0;
  diameter = 0;
  v.clear();
  dfs(root, -1);
  dist[furthest] = 0;
  diameter = 0;
  v.clear();
  dfs(furthest, -1);
  return diameter;
}
//compute initial dp and dpdown
int dfs2(int x, int p) {
  for (auto edge: edges[x]) {
    if (edge.fi == p) continue;
    int child = dfs2(edge.fi, x) + edge.se;
    if (child > dpdown[x]) {
      dpdown[x] = child;
      maxchild[x] = edge.fi;
    } else {
      secondmax[x] = max(secondmax[x], child);
    }
  }
  return dpdown[x];
}
//update dp and dpup
void dfs3(int x, int p) {
  for (auto edge: edges[x]) {
    if (edge.fi == p) continue;
    dpup[edge.fi] = dpup[x] + edge.se; 
    if (edge.fi == maxchild[x]) {
      dpup[edge.fi] = max(dpup[edge.fi], secondmax[x] + edge.se);
    } else {
      dpup[edge.fi] = max(dpup[edge.fi], dpdown[x] + edge.se);
    }
    dfs3(edge.fi, x);
  }
}
void find_shortest_path() {
  int useless = dfs2(v[0], -1);
  dfs3(v[0], -1);
  int tmp = inf * 2;
  for (int node: v) {
    tmp = min(tmp, max(dpup[node], dpdown[node]));
    //cout << node << ' ' << dpup[node] << ' ' << dpdown[node] << endl;
  }
  comp.pb(tmp);
  //cout << "tmp " << tmp << endl;
}
int travelTime(int N, int M, int L, int u[], int v[], int t[]) {
  n = N;
  m = M;
  l = L;
  FOR(i, 0, m-1) {
    edges[u[i] + 1].emplace_back(v[i] + 1, t[i]);
    edges[v[i] + 1].emplace_back(u[i] + 1, t[i]);
  }
  FOR(i, 1, n) {
    if (!vis[i]) {
      ans = max(ans, find_diameter(i));
      find_shortest_path();
    }
  }
  int sz = comp.size();
  sort(all(comp));
  reverse(all(comp));
  if (sz == 1) {}
  else if (sz == 2) {
    ans = max(ans, L + comp[0] + comp[1]);
  } else {
    ans = max(ans, L + comp[0] + comp[1]);
    ans = max(ans, L + L + comp[1] + comp[2]);
  }
  return ans;
}

Compilation message

dreaming.cpp: In function 'void find_shortest_path()':
dreaming.cpp:82:7: warning: unused variable 'useless' [-Wunused-variable]
   82 |   int useless = dfs2(v[0], -1);
      |       ^~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16376 KB Output is correct
2 Correct 72 ms 16964 KB Output is correct
3 Correct 51 ms 12276 KB Output is correct
4 Correct 11 ms 4864 KB Output is correct
5 Correct 9 ms 3968 KB Output is correct
6 Correct 18 ms 6016 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 42 ms 7676 KB Output is correct
9 Correct 51 ms 9848 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct
11 Correct 80 ms 12152 KB Output is correct
12 Correct 109 ms 14320 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16376 KB Output is correct
2 Correct 72 ms 16964 KB Output is correct
3 Correct 51 ms 12276 KB Output is correct
4 Correct 11 ms 4864 KB Output is correct
5 Correct 9 ms 3968 KB Output is correct
6 Correct 18 ms 6016 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 42 ms 7676 KB Output is correct
9 Correct 51 ms 9848 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct
11 Correct 80 ms 12152 KB Output is correct
12 Correct 109 ms 14320 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct
14 Incorrect 2 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16376 KB Output is correct
2 Correct 72 ms 16964 KB Output is correct
3 Correct 51 ms 12276 KB Output is correct
4 Correct 11 ms 4864 KB Output is correct
5 Correct 9 ms 3968 KB Output is correct
6 Correct 18 ms 6016 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 42 ms 7676 KB Output is correct
9 Correct 51 ms 9848 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct
11 Correct 80 ms 12152 KB Output is correct
12 Correct 109 ms 14320 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct
14 Incorrect 2 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7416 KB Output is correct
2 Correct 38 ms 7408 KB Output is correct
3 Incorrect 45 ms 7416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16376 KB Output is correct
2 Correct 72 ms 16964 KB Output is correct
3 Correct 51 ms 12276 KB Output is correct
4 Correct 11 ms 4864 KB Output is correct
5 Correct 9 ms 3968 KB Output is correct
6 Correct 18 ms 6016 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 42 ms 7676 KB Output is correct
9 Correct 51 ms 9848 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct
11 Correct 80 ms 12152 KB Output is correct
12 Correct 109 ms 14320 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct
14 Correct 2 ms 2816 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct
16 Correct 3 ms 2944 KB Output is correct
17 Correct 2 ms 2816 KB Output is correct
18 Correct 3 ms 2816 KB Output is correct
19 Correct 4 ms 2944 KB Output is correct
20 Correct 2 ms 2816 KB Output is correct
21 Correct 3 ms 2816 KB Output is correct
22 Correct 4 ms 2944 KB Output is correct
23 Incorrect 2 ms 2688 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16376 KB Output is correct
2 Correct 72 ms 16964 KB Output is correct
3 Correct 51 ms 12276 KB Output is correct
4 Correct 11 ms 4864 KB Output is correct
5 Correct 9 ms 3968 KB Output is correct
6 Correct 18 ms 6016 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 42 ms 7676 KB Output is correct
9 Correct 51 ms 9848 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct
11 Correct 80 ms 12152 KB Output is correct
12 Correct 109 ms 14320 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct
14 Incorrect 2 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -