Submission #42196261

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using db = double;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::vector<std::vector<T>> &r){
    if(r.size() == 0){
        out << "||";
        return out;
    }
    for(const auto&v : r) out << v << endl;
    out << endl;
    return out;
}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &r){
    if(r.size() == 0){
        out << "[]";
        return out;
    }
    out << "[";
    for(int i{}; i < (int)r.size() - 1; ++i) out << r[i] << ",";
    out << r.back() << "]";
    return out;
}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::set<T> &r){
    if(r.size() == 0){
        out << "{}";
        return out;
    }
    out << "{";
    auto e = r.end(); --e;
    for(auto it = r.begin(); it != e; ++it) out << *it << ",";
    out << *e << "}";
    return out;
}

template <class T, class U>
std::ostream &operator<<(std::ostream &out, const std::map<T, U> &r){
    if(r.size() == 0){
        out << "{}";
        return out;
    }
    out << "{";
    auto e = r.end(); --e;
    for(auto it = r.begin(); it != e; ++it) out << it -> first << ":" << it -> second << ",";
    out << e -> first << ":" << e -> second << "}";
    return out;
}
 
template <class T, class U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &r){
    out << "(" << r.first << "," << r.second << ")";
    return out;
}

mt19937 engine;
using Point = pair<int, int>;

struct Edge{
    int from, to;
    ll len;
    Edge(int _from = 0, int _to = 0, ll _len = 0) :
    from(_from), to(_to), len(_len){}
};

Point rand_p()
{
    return {engine() % 20001 - 10000, engine() % 20001 - 10000};
}

db norm(Point x)
{
    return sqrt(db(x.first) * db(x.first) + db(x.second) * db(x.second));
}

db dist(Point x, Point y)
{
    return norm(Point(x.first - y.first, x.second - y.second));
}

ll norm_ex(Point x)
{
    return ll(x.first) * ll(x.first) + ll(x.second) * ll(x.second);
}

db dist_ex(Point x, Point y)
{
    return norm_ex(Point(x.first - y.first, x.second - y.second));
}

vector<Point> Cluster(vector<Point>& v)
{
    int k = 40;
    vector<Point> center(k);
    for(auto& p : center) p = rand_p();
    bool ch = false;
    int n = v.size();
    vector<int> w(n);
    bool conti = true;
    vector<int> X(k), Y(k), cnt(k);
    do
    {
        vector<int> nw(n);
        for (int i = 0; i < n; i++)
        {
            db d = 1e9;
            for (int j = 0; j < k; j++)
            {
                if(chmin(d, dist(v[i], center[j])))
                {
                    nw[i] = j;
                }
            }
        }
        if(w == nw) conti = false;
        w = nw;
        X.assign(k, 0);Y.assign(k, 0);cnt.assign(k, 0);
        for (int i = 0; i < n; i++)
        {
            X[w[i]] += v[i].first;
            Y[w[i]] += v[i].second;
            cnt[w[i]]++;
        }
        for (int j = 0; j < k; j++)
        {
            if(cnt[j] > 0)
            {
                center[j] = Point(X[j] / cnt[j], Y[j] / cnt[j]);
            }
            else
            {
                center[j] = rand_p();
            }
        }
    }while(conti);
    vector<Point> c;
    for (int j = 0; j < k; j++)
    {
        if(cnt[j] > 0) c.push_back(center[j]);
    }
    k = c.size();
    for (int j = 0; j < k; j++)
    {
        for (int i = j+1; i < k; i++)
        {
            if(dist(c[i], c[j]) < 1000)
            {
                if(j < k-1) swap(c[j], c.back());
                c.pop_back();
                --k;
            }
        }
    }
    return c;
}

ll isqrt(ll x){
    db s = sqrt(db(x));
    ll si = s;
    --si;
    chmax(si, 0);
    while(si * si < x) ++si;
    return si;
}

struct answer{
    static inline vector<Point> BC;
    static inline vector<Edge> E;
    static inline vector<Point> H;
    vector<ll> P;
    vector<bool> B;
    ll score;
    answer() : P(), B(), score(1e16) {}
    answer(vector<ll>& p, vector<bool>& b) :
    P(p), B(b), score()
    {
        for(auto&i:P)
        {
            i = isqrt(i);
            chmin(i, 5000);
        }
        int n = BC.size();
        int k = H.size();
        int cnt = 0;
        for (int i = 0; i < k; i++)
        {
            bool can = false;
            for (int j = 0; j < n; j++)
            {
                if(dist_ex(H[i], BC[j]) <= P[j] * P[j]) can = true;
            }
            if(can) ++cnt;
        }
        if(cnt < k){
            score = 1e15 - cnt;
            return;
        }
        for (int j = 0; j < n; j++)
        {
            score += P[j] * P[j];
        }
        for (int i = 0; i < B.size(); i++)
        {
            if(B[i]) score += E[i].len;
        }
    }

    void normal(int n, int k)
    {
        vector<int> a(k);
        vector<vector<int>> st(n);
        for (int j = 0; j < n; j++)
        {
            for (int i = 0; i < k; i++)
            {
                if(dist_ex(H[i], BC[j]) <= P[j] * P[j])
                {
                    st[j].push_back(i);
                    ++a[i];
                }
            }
        }
        vector<int> p(n);
        iota(begin(p), end(p), 0);
        shuffle(begin(p), end(p), engine);
        for (int j : p)
        {
            P[j] = 0;
            for (int i : st[j])
            {
                if(a[i] == 1)
                {
                    chmax(P[j], isqrt(dist_ex(H[i], BC[j])));
                }
                --a[i];
            }
            for (int i : st[j])
            {
                if(dist_ex(H[i], BC[j]) <= P[j] * P[j])
                {
                    ++a[i];
                }
            }
        }
    }
};

void output(const answer& ans)
{
    for(auto i : ans.P) cout << i << " ";
    cout << '\n';
    for(auto i : ans.B) cout << i << " ";
    cout << '\n';
}

struct Edge_ad{
    int id, to;
    ll len;
    Edge_ad(int _id = 0, int _to = 0, ll _len = 0) :
    id(_id), to(_to), len(_len){}
};
using Edges = vector<Edge_ad>;

vector<bool> way(int m, const vector<Edges>& E, const vector<bool>& use)
{
    int n = E.size();
    vector<bool> B(m), reach(n);
    reach[0] = true;
    while(true)
    {
        bool br = true;
        for (int i = 0; i < n; i++)
        {
            if(use[i] and (not reach[i]))
            {
                br = false;
                break;
            }
        }
        if(br) break;

        std::vector<ll> d(n, 1e16);
        using PUint = std::pair<ll,int>;
        std::priority_queue<PUint,std::vector<PUint>,std::greater<>> pq;
        for (int i = 0; i < n; i++)
        {
            if(reach[i])
            {
                d[i] = 0;
                pq.emplace(0, i);
            }
        }
        vector<pair<int, int>> prev(n, pair<int, int>(-1, -1));
        while(!pq.empty()){
            auto [D, i] = pq.top();
            pq.pop();
            if(d[i] < D) continue;
            if(use[i] and (not reach[i]))
            {
                while(prev[i].first != -1)
                {
                    B[prev[i].second] = true;
                    reach[i] = true;
                    i = prev[i].first;
                }
                break;
            }
            for(const Edge_ad& e : E[i]){
                ll nD = D + e.len;
                if(d[e.to] <= nD) continue;
                prev[e.to] = pair<int, int>(i, e.id);
                d[e.to] = nD;
                pq.emplace(nD, e.to);
            }
        }
    }
    return B;
}

void solve(){
    chrono::system_clock::time_point start, now;
    start = chrono::system_clock::now();
    chrono::system_clock::time_point limits = start + chrono::milliseconds(1950);
    engine = mt19937{42};
    int n, m, k;
    cin >> n >> m >> k;
    vector<Point> BC(n);
    for(auto&[x, y] : BC) cin >> x >> y;
    vector<Edge> E(m);
    for(auto&[u, v, w] : E)
    {
        cin >> u >> v >> w;
        --u, --v;
    }
    vector<Edges> E_ad(n);
    for (int i = 0; i < m; i++)
    {
        E_ad[E[i].from].emplace_back(i, E[i].to, E[i].len);
        E_ad[E[i].to].emplace_back(i, E[i].from, E[i].len);
    }
    

    vector<Point> H(k);
    for(auto&[a, b] : H) cin >> a >> b;
    vector<Point> c = Cluster(H);
    int s = c.size();
    vector<int> p(n);
    iota(begin(p), end(p), 0);
    answer::E = E;
    answer::BC = BC;
    answer::H = H;
    answer ans{};
    vector<int> ran(4, 4);
    ran[1] = 12, ran[2] = 24, ran[3] = 32;
    while(chrono::system_clock::now() < limits)
    //while(true)
    {
        vector<bool> use(n);
        for (int i = 0; i < s; i++)
        {
            vector<db> d(n);
            for (int j = 0; j < n; j++)
            {
                d[j] = dist(c[i], BC[j]);
            }
            partial_sort(begin(p), begin(p) + 4, end(p), [&](int l, int r){
                return d[l] < d[r];
            });
            for (int j = 0; j < 4; j++)
            {

                if(engine() % ran[j] < 4) use[p[j]] = true;
            }
        }


        vector<ll> P(n);
        for (int i = 0; i < k; i++)
        {
            ll d = 1e16;
            int id = -1;
            for (int j = 0; j < n; j++)
            {
                if(not use[j]) continue;
                if(chmin(d, dist_ex(H[i], BC[j]))) id = j;
            }
            chmax(P[id], d);
        }
        for (int i = 0; i < n; i++)
        {
            if(P[i] == 0) use[i] = false;
        }

        vector<bool> B = way(m, E_ad, use);

        answer nans(P, B);

        if(nans.score < ans.score)
        {
            ans = nans;
        }
    }

    ans.normal(n, k);
    output(ans);
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
}

Submission Info

Compile Error

./Main.cpp: In function ‘std::vector<std::pair<int, int> > Cluster(std::vector<std::pair<int, int> >&)’:
./Main.cpp:105:10: warning: unused variable ‘ch’ [-Wunused-variable]
  105 |     bool ch = false;
      |          ^~
./Main.cpp: In constructor ‘answer::answer(std::vector<long long int>&, std::vector<bool>&)’:
./Main.cpp:211:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<bool>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  211 |         for (int i = 0; i < B.size(); i++)
      |                         ~~^~~~~~~~~~

Judge Result