oj.uz

답안 #411789

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411789 2021-05-26T01:25:36 Z couplefire ČVENK (COI15_cvenk) C++17
100 / 100
 1278 ms 90720 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define int long long
#define pii pair <int , int>
#define X first
#define Y second
#define F first
#define S second
#define mp make_pair
#define all(v) v.begin(), v.end()
const int N = 30, M = 2e5 + 5;
int pw[N], x[M], y[M], cnt[M], sz[M], dw[M], up[M];
vector <pii> P, g[M];
map <pii, int> Label;
 
int Zone(pii p, int n) {
    if (p.X >= pw[n-1]) return 2;
    if (p.Y >= pw[n-1]) return 1;
    return 0;
}
void dfs_order(vector <pii> &vec, int n = N) {
    if (n == 0 || vec.size() == 0) return ;
    vector <pii> v[3];
    for (pii p : vec) {
        int z = Zone(p, n);
        if (z == 1) v[1].push_back({p.X, p.Y - pw[n-1]});
        if (z == 2) v[2].push_back({p.X - pw[n-1], p.Y});
        if (z == 0) v[0].push_back(p);
    }
    vec.clear();
    dfs_order(v[0], n - 1), dfs_order(v[1], n - 1), dfs_order(v[2], n - 1);
    int pnt = 0;
    while (pnt < v[0].size() && v[0][pnt].X == 0) vec.push_back(v[0][pnt++]);
    for (pii p : v[1]) vec.push_back({p.X, p.Y + pw[n-1]});
    while (pnt < v[0].size()) vec.push_back(v[0][pnt++]);
    for (pii p : v[2]) vec.push_back({p.X + pw[n-1], p.Y});
}
pii LCA(pii u, pii v, int n = N) {
    if (n == 0) return {0, 0};
    int zu = Zone(u, n), zv = Zone(v, n);
    if (zu > zv) swap(u, v), swap(zu, zv);
    if (zu == 1 && zv == 2) return {0, 0};
    if (zu == 2 && zv == 2) {
        pii A = LCA({u.X - pw[n-1], u.Y}, {v.X - pw[n-1], v.Y}, n - 1);
        return {A.X + pw[n - 1], A.Y};
    }
    if (zu == 1 && zv == 1) {
        pii A = LCA({u.X, u.Y - pw[n - 1]}, {v.X, v.Y - pw[n - 1]}, n - 1);
        return {A.X, A.Y + pw[n - 1]};
    }
    if (zu == 0 && zv == 0) return LCA(u, v, n - 1);
    if (zv == 2) return LCA(u, {pw[n - 1] - 1, 0});
    if (zv == 1) return LCA(u, {0, pw[n - 1] - 1});
}
int DIS(pii u, pii v, int n = N) {
    if (n == 0) return 0;
    int zu = Zone(u, n), zv = Zone(v, n);
    if (zu > zv) swap(u, v), swap(zu, zv);
    if (zu == 1 && zv == 2) return u.X + u.Y + v.X + v.Y;
    if (zu == 2 && zv == 2) return DIS({u.X - pw[n-1], u.Y}, {v.X - pw[n-1], v.Y}, n - 1);
    if (zu == 1 && zv == 1) return DIS({u.X, u.Y - pw[n-1]}, {v.X, v.Y - pw[n-1]}, n - 1);
    if (zu == 0 && zv == 0) return DIS(u, v, n - 1);
    if (zv == 2) return DIS(u, {pw[n - 1] - 1, 0}) + v.X + v.Y - pw[n-1] + 1;
    if (zv == 1) return DIS(u, {0, pw[n - 1] - 1}) + v.X + v.Y - pw[n-1] + 1;
}
 
void dfs_down(int v) {
    sz[v] = cnt[v];
    for (pii e : g[v]) dfs_down(e.F), dw[v] += e.S * sz[e.F] + dw[e.F], sz[v] += sz[e.F];
}
void dfs_up(int v, int p = -1, int w = 0) {
    if (p != -1)
        up[v] = dw[p] + up[p] + (sz[0] - sz[v]) * w - dw[v] - sz[v] * w;
    for (pii e : g[v]) dfs_up(e.F, v, e.S);
}
 
int32_t main() {
    for (int i = 0; i < N; i++) pw[i] = 1<<i;
    int n; cin >> n, P.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        P[i].X = x[i], P[i].Y = y[i];
    }
    if (n == 2) return cout << DIS(P[0], P[1]) << "\n", 0;
    dfs_order(P);
    for (int i = 1; i < n; i++) P.push_back(LCA(P[i - 1], P[i]));
    P.push_back(LCA(P[0], P[n - 1]));
    dfs_order(P);
    P.resize(unique(all(P)) - P.begin());
    for (int i = 0; i < P.size(); i++) Label[P[i]] = i;
    for (int i = 0; i < n; i++) cnt[Label[{x[i], y[i]}]]++;
    vector <int> s;
    s.push_back(0);
    for (int v = 1; v < P.size(); v++) {
        while (LCA(P[s.back()], P[v]) != P[s.back()]) s.pop_back();
        g[s.back()].push_back(mp(v, DIS(P[s.back()], P[v])));
        s.push_back(v);
    }
    dfs_down(0), dfs_up(0);
    int ans = 1e18;
    for (int i = 0; i < P.size(); i++) ans = min(ans, dw[i] + up[i]);
    cout << ans << "\n";
}

Compilation message

cvenk.cpp: In function 'void dfs_order(std::vector<std::pair<long long int, long long int> >&, long long int)':
cvenk.cpp:34:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while (pnt < v[0].size() && v[0][pnt].X == 0) vec.push_back(v[0][pnt++]);
      |            ~~~~^~~~~~~~~~~~~
cvenk.cpp:36:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     while (pnt < v[0].size()) vec.push_back(v[0][pnt++]);
      |            ~~~~^~~~~~~~~~~~~
cvenk.cpp: In function 'int32_t main()':
cvenk.cpp:91:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < P.size(); i++) Label[P[i]] = i;
      |                     ~~^~~~~~~~~~
cvenk.cpp:95:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int v = 1; v < P.size(); v++) {
      |                     ~~^~~~~~~~~~
cvenk.cpp:102:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 0; i < P.size(); i++) ans = min(ans, dw[i] + up[i]);
      |                     ~~^~~~~~~~~~
cvenk.cpp: In function 'std::pair<long long int, long long int> LCA(std::pair<long long int, long long int>, std::pair<long long int, long long int>, long long int)':
cvenk.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
   55 | }
      | ^
cvenk.cpp: In function 'long long int DIS(std::pair<long long int, long long int>, std::pair<long long int, long long int>, long long int)':
cvenk.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 85372 KB Output is correct
2 Correct 236 ms 85920 KB Output is correct
3 Correct 212 ms 88772 KB Output is correct
4 Correct 231 ms 90720 KB Output is correct
5 Correct 212 ms 88092 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1271 ms 33316 KB Output is correct
2 Correct 1278 ms 35112 KB Output is correct
3 Correct 669 ms 32212 KB Output is correct
4 Correct 712 ms 27816 KB Output is correct
5 Correct 726 ms 27004 KB Output is correct