oj.uz

Submission #339044

# Submission time Handle Problem Language Result Execution time Memory
339044 2020-12-24T13:14:02 Z radaiosm7 Dreaming (IOI13_dreaming) C++
0 / 100
 1000 ms 13164 KB 
#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;
int r[100005];

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

      r[i] = curr;
    }

    sort(r, r+comps);

    if (comps > 2) {
      return max(r[0]+r[1]+L, r[1]+r[2]+2*L);
    }

    else {
      return r[0]+r[1]+L;
    }
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 13164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 13164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 13164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 6288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 13164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 13164 KB Output isn't correct
2 Halted 0 ms 0 KB -