Submission #920271

#	Time	Username	Problem	Language	Result	Execution time	Memory
920271		Arp	Dreaming (IOI13_dreaming)	C++17	18 / 100	47 ms	17496 KiB

dreaming

#include<bits/stdc++.h>
using namespace std;
#include"dreaming.h"

using i64 = int;
const int N = 1e5;
vector<pair<int,int>> adj[N];
i64 down[N],up[N];
bool vis[N];
i64 mini = 1e9;
void dfs(int u){
  vis[u] = true;
  vector<i64> all;
  i64 maxi = -1e9;
  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 = -1e9;
  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 = 1e9;
      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 = 1e9;
  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);
  }
  return ans;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23