Submission #1255941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255941		comgaTramAnh	Dreaming (IOI13_dreaming)	C++20	0 / 100	1096 ms	21312 KiB

dreaming

#include <bits/stdc++.h> 
#include "dreaming.h"
using namespace std;
vector <vector <pair <int, int>>> adj;
vector <bool> visited;
vector <int> f_out, f_in;
vector <vector <int>> prefix, suffix; 
void dfs_out(int u, int father) {
  visited[u] = true; 
  for (int i = 0; i < (int) adj[u].size(); i++) {
    pair <int, int> neighbor = adj[u][i]; 
    if (neighbor.first != father) {
      dfs_out(neighbor.first, u);
      f_out[u] = max(f_out[u], f_out[neighbor.first] + neighbor.second);  
    }
  }
  prefix[u].clear(); 
  prefix[u].resize((int) adj[u].size() + 3); 
  prefix[u][0] = 0; 
  for (int i = 1; i <= (int) adj[u].size(); i++) {
    prefix[u][i] = max(prefix[u][i - 1], f_out[adj[u][i - 1].first] + adj[u][i - 1].second);
  }
  suffix[u].clear(); 
  suffix[u].resize((int) adj[u].size() + 3); 
  suffix[u][(int) adj[u].size() + 1] = 0; 
  for (int i = (int) adj[u].size(); i >= 1; i--) {
    suffix[u][i] = max(suffix[u][i + 1], f_out[adj[u][i - 1].first] + adj[u][i - 1].second);
  }
}
void dfs_in(int u, int father) {
  for (int i = 0; i < (int) adj[u].size(); i++) {
    pair <int, int> neighbor = adj[u][i]; 
    if (neighbor.first == father) {
      continue; 
    }
    f_in[neighbor.first] = max(f_in[neighbor.first], f_in[u] + neighbor.second); 
    f_in[neighbor.first] = max(f_in[neighbor.first], max(prefix[u][i], suffix[u][i + 2]) + neighbor.second); 
    dfs_in(neighbor.first, u); 
  }
}
int solve(int u) {                        
  int n = (int) adj.size();
  visited.clear(); 
  visited.resize(n, false); 
  f_out.clear();  
  f_out.resize(n, 0);
  f_in.clear(); 
  f_in.resize(n, 0);
  prefix.resize(n);
  suffix.resize(n);  
  dfs_out(u, -1);
  dfs_in(u, -1);
  int ans = 1000000007; 
  for (int i = 0; i < n; i++) {
    if (visited[i] == true) {
      ans = min(ans, max(f_in[u], f_out[u]));   
    }
  }  
  return ans; 
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
  adj.resize(n);
  visited.resize(n, false);
  for (int i = 0; i < m; i++) {
    adj[a[i]].push_back(make_pair(b[i], t[i]));
    adj[b[i]].push_back(make_pair(a[i], t[i]));
  }
  int ans = 0; 
  for (int i = 0; i < n; i++) {
    if (visited[i] == false) {
      ans += solve(i);  
    }
  } 
  ans += l; 
  return ans; 
}

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