oj.uz

Submission #920269

# Submission time Handle Problem Language Result Execution time Memory
920269 2024-02-02T11:33:22 Z Arp Dreaming (IOI13_dreaming) C++17
0 / 100
 59 ms 19536 KB 
#include<bits/stdc++.h>
#include"dreaming.h"
using namespace std;

using i64 = long long;
const int N = 1e5;
vector<pair<int,int>> adj[N];
i64 down[N],up[N];
bool vis[N];
i64 mini = 1e18;
void dfs(int u){
  vis[u] = true;
  vector<i64> all;
  i64 maxi = -1e18;
  for(auto [v,w] : adj[u]){
    if(vis[v]) continue;
    // cout << u << " " << v << '\n';
    down[v] = down[u] + w;
    dfs(v);  
    up[u] = max(up[u],up[v] + w);
  }
  for(auto [v,w] : adj[u]){
    up[v] = max(up[v],maxi + w);
    maxi = max(maxi,up[v] + w);
  }
  maxi = -1e18;
  reverse(adj[u].begin(),adj[u].end());
  for(auto [v,w] : adj[u]){
    up[v] = max(up[v],maxi + w);
    maxi = max(maxi,up[v] + w);
  }
}

void dfs2(int u,int p){
  for(auto [v,w] : adj[u]){
    if(v == p) continue;
    dfs2(v,u);  
  }
  mini = min(mini,max(down[u],up[u]));
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
  for(int i = 0;i<N;i++){
    up[i] = down[i] = 0;
    vis[i] = false;
  }
  for(int i = 0;i<M;i++){
    adj[A[i]].emplace_back(B[i],T[i]);
    adj[B[i]].emplace_back(A[i],T[i]);
  }
  multiset<i64> ms;
  vector<i64> com;
  int cc = 0;
  for(int i = 0;i<N;i++){
    if(!vis[i] && adj[i].size() <= 1){
      mini = 1e18;
      dfs(i);
      dfs2(i,-1);
      ms.insert(mini);
      com.push_back(mini);
      cc ++;
    }
  }
  assert(cc - 1 == N - M - 1);
  if(cc <= 2){
    i64 sum = 0;
    while(ms.size() > 0){
      sum += *ms.begin();
      ms.erase(ms.begin());
    }
    return sum + (cc - 1) * L;
  }
  i64 ans = 1e18;
  for(i64 c : com){
    ms.erase(ms.find(c));
    i64 maxi1 = *(--ms.end());
    ms.erase(ms.find(maxi1));
    i64 maxi2 = *(--ms.end());
    ans = min(ans,max(maxi1 + maxi2 + 2 * L,maxi1 + c + L));
    ms.insert(c);
    ms.insert(maxi1);
    ms.insert(maxi2);
  }
  return ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 14024 KB Output is correct
2 Incorrect 59 ms 14216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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