제출 #1260266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260266		SalihSahin	City Mapping (NOI18_citymapping)	C++20	25 / 100	8 ms	2120 KiB

citymapping

// kodumu runlayabilir misin canim cms
// sihirli kelimeyi de soyleyeyim lutfen :((
 
#include "citymapping.h"
 
// void piri_reis(int N, int Q, int A[], int B[], int W[]){
//  int X = gezinti(5, 4);
//  X = gezinti(2, 4);
//  X = gezinti(1, 3);
//  X = gezinti(1, 2);
//  A[0] = 3, A[1] = 4, A[2] = 4, A[3] = 5;
//  B[0] = 4, B[1] = 1, B[2] = 2, B[3] = 3;
//  W[0] = 7, W[1] = 8, W[2] = 1, W[3] = 3;
//  return;
// }
 
#include "bits/stdc++.h"
 
using i64 = long long;
 
#ifdef DEBUG
    #include "../debug.h"
#else
    #define debug(...) void(23)
#endif
 
 
int N;
std::vector<int> A, B, W;
 
std::map<std::pair<int ,int>, i64> save;
i64 ask(int a, int b) {
    if (a > b) {
        std::swap(a, b);
    } else if (a == b) {
        return 0;
    } 
    if (save.contains({a, b})) {
        return save[{a, b}];
    }
    return save[{a, b}] = get_distance(a, b);
}
 
std::random_device rd;
std::mt19937 rng(rd());
 
int get(int l, int r) {
    return l + rng() % (r - l + 1);
}
 
std::pair<int, std::vector<i64>> bfs(int s, std::vector<int> v) {
    int n = int(v.size());
    std::vector<i64> dis(n);
    for (int i = 0; i < n; ++i) {
        dis[i] = ask(s, v[i]);
    }
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        if (dis[i] > dis[mx]) {
            mx = i;
        }
    }
    return {mx, dis};
}
 
void kodumu_runla_lutfen(int come_from_god, std::vector<int> v) {
    int n = int(v.size());
    if (n == 1) {
        return;
    }
 
    debug(v);
 
    int leaf1, leaf2;
    std::vector<i64> dis1, dis2;
    if (come_from_god != -1) {
        leaf1 = come_from_god;
        auto[l2, d1] = bfs(v[leaf1], v);
        leaf2 = l2;
        dis1 = d1;
        auto[___, d2] = bfs(v[leaf2], v);
        dis2 = d2;
    } else {
        auto[y, d] = bfs(v[0], v);
        leaf1 = y;
        auto[l2, d1] = bfs(v[leaf1], v);
        leaf2 = l2;
        dis1 = d1;
        auto[___, d2] = bfs(v[leaf2], v);
        dis2 = d2;
    }
 
    debug(leaf1, v[leaf1], dis1);
    debug(leaf2, v[leaf2], dis2);
 
    std::vector<int> ondia(n);
    for (int i = 0; i < n; ++i) {
        // debug(dis1[i] + dis2[i], dis2[leaf2]);
        if (dis1[i] + dis2[i] == dis1[leaf2]) {
            ondia[i] = true;
        }
    }
 
    std::vector<int> dia;
    for (int i = 0; i < n; ++i) {
        if (ondia[i]) {
            dia.emplace_back(i);
        }
    }
 
    std::sort(dia.begin(), dia.end(), [&](auto lhs, auto rhs) {
        return dis1[lhs] < dis1[rhs];
    });
 
    int m = int(dia.size());
 
    // #ifdef DEBUG
    //  debug("diameter:");
    //  for (int i = 0; i < m; ++i) {
    //      debug(v[dia[i]]);
    //  }
    // #endif
 
    for (int i = 0; i < m - 1; ++i) {
        int j = dia[i], k = dia[i + 1];
        A.emplace_back(v[j]);
        B.emplace_back(v[k]);
        W.emplace_back(dis1[k] - dis1[j]);
    }
 
    std::vector<std::vector<int>> g(m);
 
    for (int i = 0; i < n; ++i) {
        if (ondia[i]) {
            continue;
        }
        int lo = 1, hi = m - 2;
        while (lo < hi) {
            int mid = (lo + hi + 1) >> 1;
            if (dis1[dia[mid]] + ask(v[dia[mid]], v[i]) == dis1[i]) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        // debug(v[i], lo);
        g[lo].emplace_back(i);
    }
 
    for (int i = 0; i < m; ++i) {
        if (g[i].empty()) {
            continue;
        }
        int sizg = int(g[i].size());
        int mn = 0, mx = 0;
        for (int j = 0; j < sizg; ++j) {
            if (dis1[g[i][j]] < dis1[g[i][mn]]) {
                mn = j;
            }
            if (dis1[g[i][j]] > dis1[g[i][mx]]) {
                mx = j;
            }
        }
        // debug(v[dia[i]], v[g[i][mn]]);
        A.emplace_back(v[dia[i]]);
        B.emplace_back(v[g[i][mn]]);
        W.emplace_back(dis1[g[i][mn]] - dis1[dia[i]]);
        std::vector<int> yolla(sizg);
        for (int j = 0; j < sizg; ++j) {
            yolla[j] = v[g[i][j]];
        }
        kodumu_runla_lutfen(mx, yolla);
    }
}
 
void solve_sub(int come_from_god, std::vector<int> v) {
    int n = int(v.size());
    if (n == 1) {
        return;
    } else if (n == 2) {
        A.emplace_back(v[0]);
        B.emplace_back(v[1]);
        W.emplace_back(ask(v[0], v[1]));
        return;
    } else if (n <= 10) {
        kodumu_runla_lutfen(come_from_god, v);
        return;
    }
 
    std::shuffle(v.begin(), v.end(), rng);
    // debug(v);
 
    // int leaf1, leaf2;
    // std::vector<i64> dis1, dis2;
    // if (come_from_god != -1) {
    //  leaf1 = come_from_god;
    //  auto[l2, d2] = bfs(v[leaf1], v);
    //  leaf2 = l2;
    //  dis2 = d2;
    //  auto[___, d1] = bfs(v[leaf2], v);
    //  dis1 = d1;
    // } else {
    //  auto[y, d] = bfs(v[0], v);
    //  leaf1 = y;
    //  auto[l2, d2] = bfs(v[leaf1], v);
    //  leaf2 = l2;
    //  dis2 = d2;
    //  auto[___, d1] = bfs(v[leaf2], v);
    //  dis1 = d1;
    // }
    int leaf1 = 0;
    int leaf2 = 1;
    leaf2 += (leaf2 == leaf1);
    auto[__, dis1] = bfs(v[leaf1], v);
    auto[___, dis2] = bfs(v[leaf2], v);
 
    debug(leaf1, v[leaf1], dis1);
    debug(leaf2, v[leaf2], dis2);
 
    std::vector<int> ondia(n);
    for (int i = 0; i < n; ++i) {
        debug(dis1[i] + dis2[i], dis1[leaf2]);
        if (dis1[i] + dis2[i] == dis1[leaf2]) {
            ondia[i] = true;
        }
    }
 
    std::vector<int> dia;
    for (int i = 0; i < n; ++i) {
        if (ondia[i]) {
            dia.emplace_back(i);
        }
    }
 
    std::sort(dia.begin(), dia.end(), [&](auto lhs, auto rhs) {
        return dis1[lhs] < dis1[rhs];
    });
 
    int m = int(dia.size());
 
    #ifdef DEBUG
        debug("diameter:");
        for (int i = 0; i < m; ++i) {
            debug(v[dia[i]]);
        }
    #endif
 
    for (int i = 0; i < m - 1; ++i) {
        int j = dia[i], k = dia[i + 1];
        A.emplace_back(v[j]);
        B.emplace_back(v[k]);
        W.emplace_back(dis1[k] - dis1[j]);
    }
 
    std::vector<std::vector<int>> g(m);
 
    for (int i = 0; i < n; ++i) {
        if (ondia[i]) {
            continue;
        }
        int lo = 0, hi = m - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) >> 1;
            if (dis1[dia[mid]] + ask(v[dia[mid]], v[i]) == dis1[i]) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        debug(v[i], lo);
        g[lo].emplace_back(i);
    }
 
    for (int i = 1; i < m - 1; ++i) {
        if (g[i].empty()) {
            continue;
        }
        int sizg = int(g[i].size());
        int mn = 0, mx = 0;
        for (int j = 0; j < sizg; ++j) {
            if (dis1[g[i][j]] < dis1[g[i][mn]]) {
                mn = j;
            }
            if (dis1[g[i][j]] > dis1[g[i][mx]]) {
                mx = j;
            }
        }
        debug(v[dia[i]], v[g[i][mn]]);
        A.emplace_back(v[dia[i]]);
        B.emplace_back(v[g[i][mn]]);
        W.emplace_back(dis1[g[i][mn]] - dis1[dia[i]]);
        std::vector<int> yolla(sizg);
        for (int j = 0; j < sizg; ++j) {
            yolla[j] = v[g[i][j]];
        }
        solve_sub(mx, yolla);
    }
    for (int i : {0, m - 1}) {
        if (g[i].empty()) {
            continue;
        }
        int sizg = int(g[i].size());
        std::vector<int> yolla(sizg);
        for (int j = 0; j < sizg; ++j) {
            yolla[j] = v[g[i][j]];
        }
        yolla.emplace_back(v[dia[i]]);
        solve_sub(-1, yolla);
    }
}
 
void solve() {
    std::vector<int> all;
    all.resize(N);
    std::iota(all.begin(), all.end(), 1);
    solve_sub(-1, all);
 
    // debug(A);
    // debug(B);
    // debug(W);
}
 
void find_roads(int N, int Q, int A[], int B[], int W[]) {
    ::N = N;
 
    solve();
 
    for (int i = 0; i < N - 1; ++i) {
        A[i] = ::A[i];
        B[i] = ::B[i];
        W[i] = ::W[i];
    }
 
    return;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 43