Submission #339040

#	Time	Username	Problem	Language	Result	Execution time	Memory
339040		radaiosm7	Dreaming (IOI13_dreaming)	C++98	0 / 100	96 ms	14412 KiB

dreaming

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

vector<pair<int, int>> adj[100005];
int teams[100005];
int i, j, max1, max2, comps, curr, furt1, furt2, dist;
bool visited[100005];
int p[100005];
int d[100005];
pair<int, int> temp;

void bfs(int x) {
  queue<int> q;
  int v;

  q.push(x);
  p[x] = -1;
  d[x] = 0;
  visited[x] = true;

  while (!q.empty()) {
    v = q.front();
    q.pop();

    for (auto y : adj[v]) {
        if (!visited[y.first]) {
          visited[y.first] = true;
          q.push(y.first);
          d[y.first] = d[v] + y.second;
          p[y.first] = v;
        }
    }
  }
}

void dfs1(int x, int p) {
  visited[x] = true;
  teams[comps] = x;

  for (auto y : adj[x]) {
    if (y.first != p) {
      dfs1(y.first, x);
    }
  }
}

pair<int, int> dfs2(int x, int p) {
  pair<int, int> tmp;
  pair<int, int> cc = make_pair(0,x);

  for (auto y : adj[x]) {
      if (y.first != p) {
        tmp = dfs2(y.first, x);
        cc = max(cc, make_pair(y.second+tmp.first,tmp.second));
      }
  }

  return cc;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (i=0; i < N; i++) {
      visited[i] = false;
    }
    comps = 0;
    max1 = -1;
    max2 = -1;

    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]));
    }

    for (i=0; i < N; i++) {
      if (!visited[i]) {
          dfs1(i, -1);
          comps++;
      }
    }

    for (i=0; i < comps; i++) {
      curr = INT_MAX-1;
      furt1 = dfs2(teams[i], -1).second;
      temp = dfs2(furt1, -1);
      furt2 = temp.second;
      dist = temp.first;

      for (j=0; j < N; j++) {
        visited[j] = false;
      }

      bfs(furt1);

      j = furt2;

      while (j != -1) {
        curr = min(curr, max(dist-d[j], d[j]));
        j = p[j];
      }

      if (max1 == -1) {
        max1 = curr;
      } else if (max2 == -1) {
        max2 = curr;
      } else if (curr > max1) {
        max2 = max1;
        max1 = curr;
      } else if (curr > max2) {
        max2 = curr;
      }
    }

    return max1+max2+L;
}

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