oj.uz

Submission #1084203

# Submission time Handle Problem Language Result Execution time Memory
1084203 2024-09-05T15:41:26 Z pera Dreaming (IOI13_dreaming) C++17
0 / 100
 48 ms 21852 KB 
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int travelTime(int N , int M , int L , int A[] , int B[] , int T[]){
   vector<vector<int>> g(N + 1) , w(N + 1);
   auto add_edge = [&](int u , int v , int weight){
      g[u].emplace_back(v);
      w[u].emplace_back(weight);
   };
   for(int i = 0;i < M;i ++){
      ++A[i],++B[i];
      add_edge(A[i] , B[i] , T[i]);
      add_edge(B[i] , A[i] , T[i]);
   }
   vector<int> visited(N + 1) , d(N + 1) , mx(N + 1) , non_sub(N + 1) , max_depths;
   function<void(int , int)> dfs = [&](int u , int p){
      for(int x = 0;x < (int)g[u].size();x ++){
         if(g[u][x] != p){
            d[g[u][x]] = d[u] + w[u][x];
            dfs(g[u][x] , u);
            mx[u] = max(mx[u] , mx[g[u][x]] + w[u][x]);
         }
      }
   };
   function<int(int)> DFS = [&](int u){
      visited[u] = 1;
      int mn = max(mx[u] , non_sub[u]);
      multiset<int> X;
      for(int x = 0;x < (int)g[u].size();x ++){
         if(visited[g[u][x]] == 0){
            X.insert(mx[g[u][x]] + w[u][x]);
         }
      }
      for(int x = 0;x < (int)g[u].size();x ++){
         if(visited[g[u][x]] == 0){
            X.erase(X.find(mx[g[u][x]] + w[u][x]));
            non_sub[g[u][x]] = max(non_sub[u] , (X.empty() ? 0 : *--X.end())) + w[u][x];
            mn = min(mn , DFS(g[u][x]));
            X.insert(mx[g[u][x]] + w[u][x]);
         }
      }
      return mn;
   };
   for(int i = 1;i <= N;i ++){
      if(visited[i] == 0){
         dfs(i , -1);
         max_depths.emplace_back(DFS(i));
      }
   }
   int sz = max_depths.size();
   sort(max_depths.begin() , max_depths.end());
   if(sz == 2){
      return max_depths[0] + max_depths[1] + L;
   }
   return max(max_depths[sz - 1] + max_depths[sz - 2] + L , max_depths[sz - 2] + max_depths[sz - 3] + 2 * L);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 21852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 21852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 11268 KB Output is correct
2 Correct 27 ms 11344 KB Output is correct
3 Correct 28 ms 11356 KB Output is correct
4 Correct 24 ms 11356 KB Output is correct
5 Correct 26 ms 11356 KB Output is correct
6 Correct 26 ms 12240 KB Output is correct
7 Correct 24 ms 11840 KB Output is correct
8 Correct 23 ms 11096 KB Output is correct
9 Correct 23 ms 11100 KB Output is correct
10 Correct 24 ms 11732 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 5 ms 7384 KB Output is correct
13 Correct 6 ms 7212 KB Output is correct
14 Correct 5 ms 7384 KB Output is correct
15 Correct 6 ms 7232 KB Output is correct
16 Correct 6 ms 7384 KB Output is correct
17 Correct 6 ms 7384 KB Output is correct
18 Correct 7 ms 7388 KB Output is correct
19 Correct 6 ms 7384 KB Output is correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 21852 KB Output isn't correct
2 Halted 0 ms 0 KB -