oj.uz

Submission #23031

# Submission time Handle Problem Language Result Execution time Memory
23031 2017-05-02T04:24:37 Z model_code Grad (COI14_grad) C++14
100 / 100
 286 ms 148024 KB 
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <string>

#define MAXN 100010
#define LOG_MAXN 18

using namespace std;

double const oo = 1e15;

struct Point {
  double x, y;
};

double Dist(Point const& a, Point const& b) {
  double dx = a.x - b.x;
  double dy = a.y - b.y;
  return sqrt(dx*dx + dy*dy);
}

struct Node;
struct Edge;

struct Jump {
  Edge* edge;
  double cost[2][2];
};

struct Edge {
  int depth;
  Node* node[2];
  Jump jumps[LOG_MAXN];

  Edge() {
    depth = 0;
    node[0] = node[1] = NULL;
    for (int p = 0; p < LOG_MAXN; ++p) {
      jumps[p].edge = NULL;
      for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
          jumps[p].cost[i][j] = oo;
        }
      }
    }
  }
};

struct Node {
  Point point;
  Edge edge[2];
};

Node A[MAXN + 1];

void AssignNodes(Edge* edge, Node* a, Node* b) {
  edge->node[0] = a;
  edge->node[1] = b;
}

void AssignParent(Edge* child, Edge* parent) {
  child->depth = parent->depth + 1;
  child->jumps[0].edge = parent;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      child->jumps[0].cost[i][j] = Dist(child->node[i]->point,
                                        parent->node[j]->point);
    }
  }
  for (int p = 1; (1 << p) <= child->depth; ++p) {
    Edge const* midway = child->jumps[p - 1].edge;
    child->jumps[p].edge = midway->jumps[p - 1].edge;
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        double* cost_ij = &child->jumps[p].cost[i][j];
        *cost_ij = oo;
        for (int k = 0; k < 2; ++k) {
          double const cost_ik = child->jumps[p - 1].cost[i][k];
          double const cost_kj = midway->jumps[p - 1].cost[k][j];
          *cost_ij = min(*cost_ij, cost_ik + cost_kj);
        }
      }
    }
  }
}

void Climb(Edge** a, double cost[2], int p) {
  double new_cost[2] = { oo, oo };
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      new_cost[j] = min(new_cost[j], cost[i] + (*a)->jumps[p].cost[i][j]);
    }
  }
  *a = (*a)->jumps[p].edge;
  assert(*a != NULL);
  cost[0] = new_cost[0];
  cost[1] = new_cost[1];
}

double Solve(Edge* a, Edge* b) {
  if (a->depth > b->depth) {
    swap(a, b);
  }
  double a_cost[2] = {0, Dist(a->node[0]->point, a->node[1]->point)};
  double b_cost[2] = {0, Dist(b->node[0]->point, b->node[1]->point)};

  for (int p = LOG_MAXN - 1; p >= 0; --p) {
    if (b->depth - (1<<p) >= a->depth) {
      Climb(&b, b_cost, p);
    }
  }

  for (int p = LOG_MAXN - 1; p >= 0; --p) {
    if (a->jumps[p].edge != b->jumps[p].edge) {
      Climb(&a, a_cost, p);
      Climb(&b, b_cost, p);
    }
  }

  double ret = oo;
  if (a->node[0] == b->node[0]) {
    ret = a_cost[0] + b_cost[0];
  }
  if (a != b) {
    Climb(&a, a_cost, 0);
    Climb(&b, b_cost, 0);
  }

  assert(a == b);
  ret = min(ret, a_cost[0] + b_cost[0]);
  ret = min(ret, a_cost[1] + b_cost[1]);
  return ret;
}
int main() {
  A[0].point.x = oo;
  A[0].point.y = oo;
  scanf("%lf%lf", &A[1].point.x, &A[1].point.y);

  A[1].edge[0].depth = 0;
  AssignNodes(&A[1].edge[0], &A[1], &A[0]);
  scanf("%lf%lf", &A[2].point.x, &A[2].point.y);

  AssignNodes(&A[2].edge[0], &A[2], &A[1]);
  AssignParent(&A[2].edge[0], &A[1].edge[0]);
  int n = 2;

  int Q;
  scanf("%d", &Q);
  for (int q = 0; q < Q; ++q) {
    static char op[8];
    scanf("%s", op);
    if (op[0] == 'd') {
      int a, b;
      int c = ++n;
      scanf("%lf%lf%d%d", &A[c].point.x, &A[c].point.y, &a, &b);
      if (a > b) {
        swap(a, b);
      }
      Edge* ca = &A[c].edge[0];
      AssignNodes(ca, &A[c], &A[a]);
      Edge* cb = &A[c].edge[1];
      AssignNodes(cb, &A[c], &A[b]);
      Edge* ba = (A[b].edge[0].node[1] == &A[a]) 
          ? &A[b].edge[0]
          : &A[b].edge[1];
      assert(ba->node[0] == &A[b]);
      assert(ba->node[1] == &A[a]);
      AssignParent(ca, ba);
      AssignParent(cb, ba);
    } else {
      int a, b;
      scanf("%d%d", &a, &b);
      printf("%lf\n", Solve(&A[a].edge[0], &A[b].edge[0]));
    }
  }
  return 0;
}

Compilation message

grad.cpp: In function 'int main()':
grad.cpp:139:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%lf", &A[1].point.x, &A[1].point.y);
                                                ^
grad.cpp:143:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%lf", &A[2].point.x, &A[2].point.y);
                                                ^
grad.cpp:150:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Q);
                  ^
grad.cpp:153:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", op);
                    ^
grad.cpp:157:64: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lf%lf%d%d", &A[c].point.x, &A[c].point.y, &a, &b);
                                                                ^
grad.cpp:174:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &a, &b);
                            ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 148024 KB 41 numbers

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 148024 KB 300 numbers

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 148024 KB 500 numbers

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 148024 KB 15000 numbers
2 Correct 79 ms 148024 KB 15000 numbers
3 Correct 116 ms 148024 KB 30000 numbers

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 148024 KB 28333 numbers
2 Correct 149 ms 148024 KB 28333 numbers
3 Correct 169 ms 148024 KB 40000 numbers

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 148024 KB 50000 numbers
2 Correct 163 ms 148024 KB 50000 numbers
3 Correct 219 ms 148024 KB 50000 numbers

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 148024 KB 55000 numbers
2 Correct 206 ms 148024 KB 55000 numbers
3 Correct 216 ms 148024 KB 50000 numbers

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 148024 KB 50000 numbers
2 Correct 216 ms 148024 KB 50000 numbers
3 Correct 209 ms 148024 KB 50000 numbers
4 Correct 273 ms 148024 KB 50000 numbers

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 148024 KB 44000 numbers
2 Correct 216 ms 148024 KB 44000 numbers
3 Correct 199 ms 148024 KB 44000 numbers
4 Correct 263 ms 148024 KB 44000 numbers

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 148024 KB 50000 numbers
2 Correct 243 ms 148024 KB 50000 numbers
3 Correct 203 ms 148024 KB 50000 numbers
4 Correct 256 ms 148024 KB 50000 numbers

Subtask #11
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 148024 KB 45713 numbers
2 Correct 269 ms 148024 KB 54285 numbers
3 Correct 236 ms 148024 KB 58571 numbers
4 Correct 283 ms 148024 KB 57000 numbers

Subtask #12
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 148024 KB 49285 numbers
2 Correct 269 ms 148024 KB 49285 numbers
3 Correct 199 ms 148024 KB 49285 numbers
4 Correct 259 ms 148024 KB 45000 numbers