oj.uz

Submission #38332

# Submission time Handle Problem Language Result Execution time Memory
38332 2018-01-04T02:04:20 Z funcsr Dreaming (IOI13_dreaming) C++14
14 / 100
 535 ms 11896 KB 
#include "dreaming.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define INF 1005141919
#define _1 first
#define _2 second

int N, L;
vector<P> G[100000];
bool used[100000];
int dp1[100000], dp2[100000], src[100000];
inline void update(int x, int v, int s) {
  if (v > dp1[x]) dp2[x] = dp1[x], dp1[x] = v, src[x] = s;
  else if (v > dp2[x]) dp2[x] = v;
}
void dfs(int x, int p) {
  used[x] = true;
  dp1[x] = dp2[x] = 0;
  src[x] = -1;
  for (P pp : G[x]) if (pp._1 != p) {
    int t = pp._1, len = pp._2;
    dfs(t, x);
    update(x, dp1[t]+len, t);
  }
}

int dfs2(int x, int p, int plen, int X) {
  if (p != -1) {
    int v = dp1[p];
    if (src[p] == x) v = dp2[p];
    update(x, v+plen, p);
  }
  int m = INF;
  if (dp1[x]+dp2[x] <= X) m = dp1[x];
  for (P pp : G[x]) if (pp._1 != p) {
    int t = pp._1, len = pp._2;
    m = min(m, dfs2(t, x, len, X));
  }
  return m;
}

bool f(int X) {
  vector<int> R;
  rep(i, N) used[i] = false;
  rep(i, N) if (!used[i]) {
    dfs(i, -1);
    R.pb(dfs2(i, -1, -1, X));
    if (R.back() > X) return false;
  }
  //cout<<"{";for(int x:R)cout<<x<<",";cout<<"}\n";
  int cur_r = R[0];
  for (int i=1; i<R.size(); i++) {
    int r = R[i];
    if (cur_r+r+L > X) return false;
    cur_r = min(max(cur_r, r+L), max(cur_r+L, r));
  }
  return true;
}

int travelTime(int N_, int M, int L_, int A[], int B[], int T[]) {
  N = N_, L = L_;
  rep(i, M) {
    G[A[i]].pb(P(B[i], T[i]));
    G[B[i]].pb(P(A[i], T[i]));
  }
  int lo = -1, hi = INF;
  while (hi-lo > 1) {
    int mid = (lo+hi)/2;
    if (f(mid)) hi = mid;
    else lo = mid;
  }
  return hi;
}

Compilation message

dreaming.cpp: In function 'bool f(int)':
dreaming.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=1; i<R.size(); i++) {
                 ~^~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 11896 KB Output is correct
2 Correct 367 ms 11512 KB Output is correct
3 Correct 307 ms 9976 KB Output is correct
4 Correct 37 ms 3968 KB Output is correct
5 Correct 43 ms 3456 KB Output is correct
6 Correct 85 ms 4736 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 156 ms 6488 KB Output is correct
9 Correct 258 ms 8564 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 381 ms 9240 KB Output is correct
12 Correct 535 ms 10488 KB Output is correct
13 Correct 5 ms 2816 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 11896 KB Output is correct
2 Correct 367 ms 11512 KB Output is correct
3 Correct 307 ms 9976 KB Output is correct
4 Correct 37 ms 3968 KB Output is correct
5 Correct 43 ms 3456 KB Output is correct
6 Correct 85 ms 4736 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 156 ms 6488 KB Output is correct
9 Correct 258 ms 8564 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 381 ms 9240 KB Output is correct
12 Correct 535 ms 10488 KB Output is correct
13 Correct 5 ms 2816 KB Output is correct
14 Incorrect 4 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 11896 KB Output is correct
2 Correct 367 ms 11512 KB Output is correct
3 Correct 307 ms 9976 KB Output is correct
4 Correct 37 ms 3968 KB Output is correct
5 Correct 43 ms 3456 KB Output is correct
6 Correct 85 ms 4736 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 156 ms 6488 KB Output is correct
9 Correct 258 ms 8564 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 381 ms 9240 KB Output is correct
12 Correct 535 ms 10488 KB Output is correct
13 Correct 5 ms 2816 KB Output is correct
14 Incorrect 4 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 6760 KB Output is correct
2 Incorrect 181 ms 6812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 11896 KB Output is correct
2 Correct 367 ms 11512 KB Output is correct
3 Correct 307 ms 9976 KB Output is correct
4 Correct 37 ms 3968 KB Output is correct
5 Correct 43 ms 3456 KB Output is correct
6 Correct 85 ms 4736 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 156 ms 6488 KB Output is correct
9 Correct 258 ms 8564 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 381 ms 9240 KB Output is correct
12 Correct 535 ms 10488 KB Output is correct
13 Correct 5 ms 2816 KB Output is correct
14 Incorrect 5 ms 2816 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 11896 KB Output is correct
2 Correct 367 ms 11512 KB Output is correct
3 Correct 307 ms 9976 KB Output is correct
4 Correct 37 ms 3968 KB Output is correct
5 Correct 43 ms 3456 KB Output is correct
6 Correct 85 ms 4736 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 156 ms 6488 KB Output is correct
9 Correct 258 ms 8564 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 381 ms 9240 KB Output is correct
12 Correct 535 ms 10488 KB Output is correct
13 Correct 5 ms 2816 KB Output is correct
14 Incorrect 4 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -