Submission #1058369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058369		vjudge1	Fountain Parks (IOI21_parks)	C++17	15 / 100	2147 ms	164020 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

int DX[] = {-1, 0, 1, 0};
int DY[] = {0, 1, 0, -1};

struct DSU {
    int nrc;
    vi e;
    DSU(int n) : nrc(n), e(n, -1) {}
    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    bool same(int u, int v) { return repr(u) == repr(v); }

    void join(int u, int v) {
        u = repr(u);
        v = repr(v);
        if(u == v) return;
        --nrc;
        if(e[u] >= e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
    }
};

vi solve_assign(int m, int len, vector<vector<ii> > &G0, bool &ok) {
    /// will return a vector of len elements, with the id of the bench assigned to path i
    vector<set<ii> > G(m);
    for(int i = 0; i < m; ++i) {
        for(auto it : G0[i]) G[i].insert(it);
    }
   // printf("m=%d len=%d\n", m, len);
   // for(int i = 0; i < m; ++i) {
   //     printf("G[%d]: ", i);
   //     for(auto [a, b] : G[i]) printf("(%d, %d) ", a, b);
   //     printf("\n");
   // }
   // printf("\n");
    vi Re(len, -1);
    
    set<int> noduri_singure;
    for(int i = 0; i < m; ++i) {
        if(G[i].size() == 1) {
            noduri_singure.insert(i);
        }
    }
    while(!noduri_singure.empty()) {
        auto u = *noduri_singure.begin();
        noduri_singure.erase(u);
        if(G[u].empty()) continue;

        /// am muchia u<->v, care se refera la drumul cul
        auto [v, cul] = *G[u].begin(); 

        Re[cul] = u;
        G[v].erase({u, cul});
        G[u].clear();
        if(G[v].size() == 1) noduri_singure.insert(v);
    }


    ///fiecare nod are outdeg > 1 acum
    ///ar trebuii sa fi ramas doar cu un ciclu

    vi viz(m, 0);
    function<void(int, int)> dfs = [&](int u, int p) {
        for(auto [v, cul] : G[u]) {
            if(v == p) continue;
            if(!viz[v]) {
                viz[v] = 1;
                Re[cul] = v;
                dfs(v, u);
            }
            if(viz[u]) break;
        }
    };
    for(int i = 0; i < m; ++i) {
        if(G[i].size() > 1) {
            dfs(i, -1);
            break;
        }
    }
  //  printf("Re: ");
  //  for(auto it : Re) {
  //      printf("%d ", it);
  //  }
  //  printf("\n");
    for(auto it : Re) if(it == -1) ok = 0;
    return Re;
}

int construct_roads(vi x, vi y) {
    int n = (int)x.size();
    map<ii, int> Id;
    for(int i = 0; i < n; ++i)
        Id[ii{x[i], y[i]}] = i;
    auto get_bs_coord = [&](int u, int v) -> pair<ii, ii> {
        int x1 = x[u], y1 = y[u], x2 = x[v], y2 = y[v];
        int xcm = (x1 + x2) / 2, ycm = (y1 + y2) / 2;
        int dx = 2 - abs(x1 - x2), dy = 2 - abs(y1 - y2);
        assert(dx >= 0 && dy >= 0); // alaturate
        return make_pair(ii{xcm + dx / 2, ycm + dy / 2}, ii{xcm - dx / 2, ycm - dy / 2});
    };
    vector<ii> B;
    for(int i = 0; i < n; ++i) {
        for(int d = 0; d < 4; ++d) {
            int nx = x[i] + DX[d] * 2, ny = y[i] + DY[d] * 2;
            if(Id.count({nx, ny})) {
                int u = Id[ii{nx, ny}];
                auto [a, b] = get_bs_coord(i, u);
                assert(a.first & 1);
                assert(a.second & 1);
                assert(b.first & 1);
                assert(b.second & 1);
                B.push_back(a);
                B.push_back(b);
            }
        }
    }

    sort(B.begin(), B.end());
    B.resize(unique(B.begin(), B.end()) - B.begin());

    map<ii, int> BenchId;
    int m = (int)B.size();

    vector<vi> L(n); /// graful pe fantani
    vector<ii> E; // edges
    set<ii> SetEdges;
    vector<vector<ii> > G(m); /// graful pe banci
    for(int i = 0; i < B.size(); ++i)
        BenchId[B[i]] = i;
    
    auto get_bs_id = [&](int u, int v) {
        auto [a, b] = get_bs_coord(u, v);
        return ii{BenchId[a], BenchId[b]};
    };

    vector<ii> DupaY;
    for(int i = 0; i < n; ++i)
        DupaY.push_back({y[i], i});
    sort(DupaY.begin(), DupaY.end());

    vi Speciale = {DupaY[0].second};

    DSU UF(n);

    auto add_edge = [&](int u, int v) {
        if(SetEdges.count({u, v})) return;
        if(UF.same(u, v)) return;
        SetEdges.insert({u, v});
        SetEdges.insert({v, u});
        auto [a, b] = get_bs_id(u, v);
        G[a].push_back({b, E.size()});
        G[b].push_back({a, E.size()});
        L[u].push_back(v);
        L[v].push_back(u);
        E.push_back({u, v});
        UF.join(u, v);
    };

    for(int i = 1; i < n; ++i) {
        int u = DupaY[i - 1].second, v = DupaY[i].second;
        if(y[u] != y[v] || abs(x[u] - x[v]) > 2) {
            Speciale.push_back(v);
            Speciale.push_back(u);
        }
        else add_edge(u, v);
    }

    mt19937 rng(1);
    auto nr = [&](int a, int b) { return uniform_int_distribution<int>(a, b)(rng); };

    shuffle(Speciale.begin(), Speciale.end(), rng);
    for(auto it : Speciale) {
        for(int d = 0; d < 4; ++d) {
            int nx = x[it] + DX[d] * 2, ny = y[it] + DY[d] * 2;
            if(Id.count({nx, ny})) {
                int u = Id[ii{nx, ny}];
                add_edge(it, u);
            }
        }
    }

    if(UF.nrc != 1) return 0;

   // printf("muchile pe fantani:\n");
   // for(auto [u, v] : E) {
   //     printf("%d %d\n", u, v);
   // }
   // printf("\n");

    bool ok = 1;
    auto Re = solve_assign(m, E.size(), G, ok);
    if(!ok) return 0;

    int len = E.size();
    vi U(len), V(len), RA(len), RB(len);
    for(int i = 0; i < len; ++i) {
        tie(U[i], V[i]) = E[i];
        int id = Re[i];
        assert(id >= 0 && id < B.size());
        tie(RA[i], RB[i]) = B[id];
    }

    build(U, V, RA, RB);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(vi, vi)':
parks.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for(int i = 0; i < B.size(); ++i)
      |                    ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from parks.cpp:2:
parks.cpp:210:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |         assert(id >= 0 && id < B.size());
      |                           ~~~^~~~~~~~~~
parks.cpp:180:10: warning: variable 'nr' set but not used [-Wunused-but-set-variable]
  180 |     auto nr = [&](int a, int b) { return uniform_int_distribution<int>(a, b)(rng); };
      |          ^~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30