Submission #1209782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209782		LIA	Dreaming (IOI13_dreaming)	C++17	0 / 100	38 ms	12864 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
vvpll g;
ll sum1 = 0 , sum2 = 0;
ll max_to_node_1 = inf, max_to_node_2 =  inf;
vb vis;
void dfs_1(ll node , ll d) {
  vis[node] = 1;
  for (auto [it, dis] : g[node]) {
    if (!vis[it]) {
      sum1+=it;
      dfs_1(it, d+dis);
    }
  }
}
void dfs_2(ll node , ll d) {
  vis[node] = 1;
  for (auto [it, dis] : g[node]) {
    if (!vis[it]) {
      sum2+=it;
      dfs_2(it, d+dis);
    }
  }
}

void calc1(ll node, ll d ) {
  vis[node] = 1;
  ll mx_for_me =  max(d, sum1-d);
  max_to_node_1 = min( max_to_node_1, mx_for_me);
  for (auto [it, dis] : g[node]) {
    if (!vis[it]) {
      calc1(it, dis+d);
    }
  }
}

void calc2(ll node, ll d ) {
  vis[node] = 1;
  ll mx_for_me =  max(d, sum1-d);
  max_to_node_2 = min( max_to_node_2, mx_for_me);
  for (auto [it, dis] : g[node]) {
    if (!vis[it]) {
      calc2(it, dis+d);
    }
  }
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
  g.resize(n);
  vll dar(n);
  loop(i,0,m) {
    g[A[i]].push_back({B[i], T[i]});
    g[B[i]].push_back({A[i], T[i]});
    dar[A[i]]++;
    dar[B[i]]++;
  }
  vis.resize(n, false);
  loop(i,0,n) {
    if (!vis[i]) {
      dfs_1(i,0);
      break;
    }
  }
  vis.assign(n, false);
  loop(i,0,n) {
    if (!vis[i]) {
      dfs_2(i,0);
      break;
    }
  }
  vis.assign(n, false);
  loop(i,0,n) {
    if (dar[i] == 1 && !vis[i]) {
      calc1(i,0);
    }
  }
  vis.assign(n, false);
  loop(i,0,n) {
    if (dar[i] == 1 && !vis[i]) {
      calc2(i,0);
    }
  }
  
  
  ll ans = max({sum1, sum2, max_to_node_1+max_to_node_2});
  
  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