oj.uz

Submission #142859

# Submission time Handle Problem Language Result Execution time Memory
142859 2019-08-11T16:18:12 Z Milki Dreaming (IOI13_dreaming) C++14
18 / 100
 79 ms 14836 KB 
//#ifndef DREAMING_H_INCLUDED
//#define DREAMING_H_INCLUDED

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

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 1e5 + 5;

vector <point> E[MAXN];
vector <int> component[MAXN];
int boja[MAXN], mx[MAXN], dp_down[MAXN], dp_up[MAXN], sol;


void color(int x, int Time){
  boja[x] = Time;
  component[Time].pb(x);
  for(auto e : E[x]){
    if(boja[e.first] != -1) continue;
    color(e.first, Time);
  }
}

void dfs_down(int x, int p = -1){
  for(auto e : E[x]){
    if(e.first == p) continue;
    dfs_down(e.first, x);
    dp_down[x] = max(dp_down[x], dp_down[e.first] + e.second);
  }
}

void merge(point &a, int x){
  if(x > a.first){
    a.second = a.first;
    a.first = x;
  }
  else if(x > a.second)
    a.second = x;
}

void dfs_up(int x, int p = -1){
  point maxi = point(0, 0);

  for(auto e : E[x]){
    if(e.first == p) continue;
    merge(maxi, dp_down[e.first] + e.second);
  }

  for(auto e : E[x]){
    if(e.first == p) continue;
    if(maxi.first == dp_down[e.first] + e.second)
      dp_up[e.first] = maxi.second + e.second;
    else
      dp_up[e.first] = maxi.first + e.second;

    dp_up[e.first] = max(dp_up[e.first], dp_up[x] + e.second);
    dfs_up(e.first, x);
  }

  sol = max(sol, maxi.first + maxi.second);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  REP(i, M){
    E[ A[i] ].pb( point( B[i], T[i] ) );
    E[ B[i] ].pb( point( A[i], T[i] ) );
  }

  memset(boja, -1, sizeof(boja));
  int Time = 0;
  REP(i, N)
    if(boja[i] == -1)
      color(i, Time ++);

  vector<int> v;
  REP(i, Time){
    dfs_down(component[i][0]);
    dfs_up(component[i][0]);

    int mn = 1e9;
    for(auto it : component[i]){
      mn = min(mn, max(dp_down[it], dp_up[it]));
    }
    v.pb(mn);
  }

  sort(v.rbegin(), v.rend());

  if(Time == 1)
    return sol;
  else if(Time == 2)
    return max(sol, mx[0] + mx[1] + L);
  else
    return max(v[1] + v[2] + 2 * L, max(sol, v[0] + v[1] + L));
}

//#endif // DREAMING_H_INCLUDED

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14448 KB Output is correct
2 Correct 74 ms 14836 KB Output is correct
3 Correct 51 ms 13428 KB Output is correct
4 Correct 16 ms 6904 KB Output is correct
5 Correct 14 ms 6392 KB Output is correct
6 Correct 23 ms 7800 KB Output is correct
7 Incorrect 7 ms 5500 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14448 KB Output is correct
2 Correct 74 ms 14836 KB Output is correct
3 Correct 51 ms 13428 KB Output is correct
4 Correct 16 ms 6904 KB Output is correct
5 Correct 14 ms 6392 KB Output is correct
6 Correct 23 ms 7800 KB Output is correct
7 Incorrect 7 ms 5500 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14448 KB Output is correct
2 Correct 74 ms 14836 KB Output is correct
3 Correct 51 ms 13428 KB Output is correct
4 Correct 16 ms 6904 KB Output is correct
5 Correct 14 ms 6392 KB Output is correct
6 Correct 23 ms 7800 KB Output is correct
7 Incorrect 7 ms 5500 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 10864 KB Output is correct
2 Correct 43 ms 10876 KB Output is correct
3 Correct 50 ms 10744 KB Output is correct
4 Correct 70 ms 10872 KB Output is correct
5 Correct 67 ms 10792 KB Output is correct
6 Correct 66 ms 11380 KB Output is correct
7 Correct 73 ms 11104 KB Output is correct
8 Correct 60 ms 10740 KB Output is correct
9 Correct 43 ms 10612 KB Output is correct
10 Correct 66 ms 11000 KB Output is correct
11 Correct 6 ms 5372 KB Output is correct
12 Correct 18 ms 9844 KB Output is correct
13 Correct 18 ms 9864 KB Output is correct
14 Correct 19 ms 9820 KB Output is correct
15 Correct 19 ms 9720 KB Output is correct
16 Correct 18 ms 9720 KB Output is correct
17 Correct 18 ms 9464 KB Output is correct
18 Correct 16 ms 9848 KB Output is correct
19 Correct 18 ms 9724 KB Output is correct
20 Correct 8 ms 5368 KB Output is correct
21 Correct 6 ms 5368 KB Output is correct
22 Correct 7 ms 5496 KB Output is correct
23 Correct 18 ms 9720 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14448 KB Output is correct
2 Correct 74 ms 14836 KB Output is correct
3 Correct 51 ms 13428 KB Output is correct
4 Correct 16 ms 6904 KB Output is correct
5 Correct 14 ms 6392 KB Output is correct
6 Correct 23 ms 7800 KB Output is correct
7 Incorrect 7 ms 5500 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14448 KB Output is correct
2 Correct 74 ms 14836 KB Output is correct
3 Correct 51 ms 13428 KB Output is correct
4 Correct 16 ms 6904 KB Output is correct
5 Correct 14 ms 6392 KB Output is correct
6 Correct 23 ms 7800 KB Output is correct
7 Incorrect 7 ms 5500 KB Output isn't correct
8 Halted 0 ms 0 KB -