oj.uz

답안 #349802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349802 2021-01-18T12:34:15 Z Pety 꿈 (IOI13_dreaming) C++14
18 / 100
 78 ms 17644 KB 
#include <bits/stdc++.h>
#include "dreaming.h"


using namespace std;

const int N = 1e5 + 2;
int up[N], k, down[N], bestTime[N];
bool viz[N];
vector<pair<int, int> > G[N];
void dfs (int nod, int p) {
  for (auto it : G[nod])
    if (it.first != p) {
      dfs(it.first, nod);
      down[nod] = max(down[nod], down[it.first] + it.second);
    }

}

void dfs2 (int nod, int p) {
  vector<int>pref;
  vector<int>suf;
  viz[nod] = 1;
  for (auto it : G[nod])
    if (it.first != p) {
      up[it.first] = up[nod] + it.second;
      pref.push_back(down[it.first] + it.second);
    }
  suf = pref;
  for (int i = 1; i < pref.size(); i++)
    pref[i] = max(pref[i - 1], pref[i]);
  for (int i = suf.size() - 2; i >= 0; i--)
    suf[i] = max(suf[i + 1], suf[i]);
  int useless = 0;
  for (auto it : G[nod])
    if (it.first != p) {
      int value = 0;
      if (useless > 0)
        value = pref[useless - 1];
      if (useless < suf.size() - 1)
        value = max(value, suf[useless + 1]);
      up[it.first] = max(up[it.first], value + it.second);
      useless++;
      dfs2(it.first, nod);
    }
  bestTime[k] = min(bestTime[k], max(down[nod], up[nod]));
}

int travelTime (int n, int m, int l, int a[], int b[], int t[]) {
  for (int i = 0; i < m; i++) {
    a[i]++; b[i]++;
    G[a[i]].push_back({b[i], t[i]});
    G[b[i]].push_back({a[i], t[i]});
  }
  for (int i = 1; i <= n; i++)
    if (!viz[i]) {
      k++;
      bestTime[k] = 1e9 + 2;
      dfs(i, 0);
      dfs2(i, 0);
    }
  sort(bestTime + 1, bestTime + k + 1, greater<int>());
  if (k == 1)
    return bestTime[1];
  if (k == 2)
    return l + bestTime[1] + bestTime[2];
  else
    return max(l + bestTime[1] + bestTime[2], bestTime[2] + bestTime[3] + 2 * l);
}

int a[N], b[N], t[N], n, m, l;

/*int main ()
{
  cin >> n >> m >> l;
  for (int i = 1; i <= m; i++) {
    cin >> a[i] >> b[i] >> t[i];
        a[i]++; b[i]++;

  }
  cout << timeTravel(n, m, l, a, b, t);
  return 0;
}*/
/**
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

**/

Compilation message

dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (int i = 1; i < pref.size(); i++)
      |                   ~~^~~~~~~~~~~~~
dreaming.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |       if (useless < suf.size() - 1)
      |           ~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 78 ms 17644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 78 ms 17644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 78 ms 17644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 6124 KB Output is correct
2 Correct 27 ms 6124 KB Output is correct
3 Correct 28 ms 6124 KB Output is correct
4 Correct 34 ms 6272 KB Output is correct
5 Correct 29 ms 6124 KB Output is correct
6 Correct 30 ms 6252 KB Output is correct
7 Correct 30 ms 6252 KB Output is correct
8 Correct 26 ms 5996 KB Output is correct
9 Correct 27 ms 5996 KB Output is correct
10 Correct 28 ms 6252 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct
12 Correct 6 ms 3820 KB Output is correct
13 Correct 6 ms 3948 KB Output is correct
14 Correct 8 ms 3820 KB Output is correct
15 Correct 6 ms 3820 KB Output is correct
16 Correct 6 ms 3820 KB Output is correct
17 Correct 5 ms 3436 KB Output is correct
18 Correct 6 ms 3948 KB Output is correct
19 Correct 6 ms 3820 KB Output is correct
20 Correct 2 ms 2668 KB Output is correct
21 Correct 2 ms 2668 KB Output is correct
22 Correct 2 ms 2668 KB Output is correct
23 Correct 6 ms 3820 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 78 ms 17644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 78 ms 17644 KB Output isn't correct
2 Halted 0 ms 0 KB -