Submission #400846

#	Time	Username	Problem	Language	Result	Execution time	Memory
400846		radaiosm7	Dreaming (IOI13_dreaming)	C++98	100 / 100	105 ms	17528 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
vector<pair<int, int> > adj[100005];
vector<int> dists;
bool visited[100005];
int dpd[100005];
int maxd[100005][2];
int ans, i;

int dfs1(int x) {
  int ans = 0;
  visited[x] = true;
  int max1 = 0;
  int max2 = 0;
  dpd[x] = 0;

  for (auto y : adj[x]) {
    if (!visited[y.X]) {
      ans = max(ans, dfs1(y.X));
      dpd[x] = max(dpd[x], dpd[y.X]+y.Y);

      if (dpd[y.X]+y.Y >= max1) {
        max2 = max1;
        max1 = dpd[y.X]+y.Y;
      }

      else if (dpd[y.X]+y.Y >= max2) {
        max2 = dpd[y.X]+y.Y;
      }
    }
  }

  maxd[x][0] = max1;
  maxd[x][1] = max2;
  return max(ans, max1+max2);
}

void swaping(int x, int y, int z, bool ok) {
  if (maxd[x][0] == dpd[y]+z) {
    dpd[x]=maxd[x][1];
  }

  else {
    dpd[x] = maxd[x][0];
  }

  if (ok) {
    if (dpd[x]+z >= maxd[y][0]) {
      maxd[y][1] = maxd[y][0];
      maxd[y][0] = dpd[x]+z;
    }

    else if (dpd[x]+z>maxd[y][1]) {
      maxd[y][1] = dpd[x]+z;
    }
  }

  dpd[y] = maxd[y][0];
  return;
}

int dfs2(int x, int p=-1) {
  int ans = dpd[x];

  for (auto y : adj[x]) {
    if (y.X != p) {
      swaping(x, y.X, y.Y, true);
      ans = min(ans, dfs2(y.X, x));
      swaping(y.X, x, y.Y, false);
    }
  }

  return ans;
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
  fill(visited, visited+n+2, false);
  fill(dpd, dpd+n+2, 0);

  for (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]));
  }
  ans = 0;

  for (i=0; i < n; ++i) {
    if (!visited[i]) {
      ans = max(ans, dfs1(i));
      dists.push_back(dfs2(i));
    }
  }

  sort(dists.begin(), dists.end(), greater<int>());

  if (dists.size() == 1) {
    return max(ans, dists[0]);
  }

  else if (dists.size() == 2) {
    return max(ans, dists[0]+dists[1]+l);
  }

  else {
    return max({ans, dists[0]+dists[1]+l, dists[1]+dists[2]+2*l});
  }
}

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