Submission #105534

#	Time	Username	Problem	Language	Result	Execution time	Memory
105534		jwvg0425	도로 건설 사업 (JOI13_construction)	C++17	0 / 100	5113 ms	260508 KiB

construction

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


class Mapping
{
public:
    void init(const vector<i64>& raw, int base = 0)
    {
        start = base;
        arr = raw;
        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(), arr.end()), arr.end());

        for (int i = 0; i < arr.size(); i++)
            idx[arr[i]] = base + i;
    }

    int get_idx(i64 k)
    {
        return idx[k];
    }

    i64 get_value(int idx)
    {
        return arr[idx - start];
    }

private:
    int start;
    vector<i64> arr;
    map<i64, int> idx;
};

class FenwickTree
{
public:
    FenwickTree(int k)
    {
        data.resize(k);
    }

    i64 sum(int n)
    {
        i64 ans = 0;

        while (n > 0)
        {
            ans += data[n];
            n -= (n & -n);
        }

        return ans;
    }

    void add(int n, i64 num)
    {
        while (n < data.size())
        {
            data[n] += num;
            n += (n & -n);
        }
    }

    int search(i64 k)
    {
        int lo = 0, hi = data.size() - 1;
        int ans = 0;

        while (lo <= hi)
        {
            int mid = (lo + hi) / 2;

            i64 q = sum(mid);

            if (q >= k)
            {
                ans = mid;
                hi = mid - 1;
            }
            else
            {
                lo = mid + 1;
            }
        }

        return ans;
    }

private:
    vector<i64> data;
};

struct Edge
{
    Edge() = default;

    Edge(int start, int end, int cost)
        : s(start), e(end), c(cost) {}

    int s, e, c;
};

vector<Edge> edges;
int parent[200005];

int find(int x)
{
    if (parent[x] == x)
        return x;

    return parent[x] = find(parent[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);

    parent[x] = y;
}

struct Events
{
    //l ~ r 영역(l에 +1, r에 -1)
    vector<ii> area;

    // xpos, idx
    vector<ii> pos;
};

void buildGraph(Mapping& mapping, vector<Events>& events)
{
    FenwickTree cover(1000005);
    FenwickTree points(1000005);

    for (auto& es : events)
    {
        sort(all(es.pos));

        for (auto& area : es.area)
        {
            cover.add(mapping.get_idx(area.xx), 1);
            cover.add(mapping.get_idx(area.yy), -1);

            if (area.xx < area.yy)
            {
                points.add(mapping.get_idx(area.xx), 1);
                points.add(mapping.get_idx(area.yy - 1), 1);
            }
            else
            {
                points.add(mapping.get_idx(area.xx - 1), -1);
                points.add(mapping.get_idx(area.yy), -1);
            }
        }

        if (es.pos.empty())
            continue;

        for (int i = 0; i < es.pos.size() - 1; i++)
        {
            int sx = mapping.get_idx(es.pos[i].xx);
            int ex = mapping.get_idx(es.pos[i + 1].xx);

            if (cover.sum(sx) > 0 || cover.sum(ex) > 0)
                continue;

            if (points.sum(ex) - points.sum(sx - 1) > 0)
                continue;

            edges.emplace_back(es.pos[i].yy, es.pos[i + 1].yy,
                es.pos[i + 1].xx - es.pos[i].xx);
        }
    }
}

int main()
{
    int n, m, c;
    scanf("%d %d %d", &n, &m, &c);

    vector<ii> towns(n + 1);
    vector<ii> st(m), ed(m);
    vector<i64> xpos, ypos;

    // y 좌표, (해당 y에서 event)
    vector<Events> xEvents(5 * n);
    vector<Events> yEvents(5 * n);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &towns[i].xx, &towns[i].yy);
        xpos.push_back(towns[i].xx);
        ypos.push_back(towns[i].yy);
    }

    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d %d", &st[i].xx, &st[i].yy, &ed[i].xx, &ed[i].yy);
        xpos.push_back(st[i].xx);
        xpos.push_back(ed[i].xx);
        xpos.push_back(ed[i].xx + 1);
        ypos.push_back(st[i].yy);
        ypos.push_back(ed[i].yy);
        ypos.push_back(ed[i].yy + 1);
    }

    Mapping xMapping;
    Mapping yMapping;

    xMapping.init(xpos, 1);
    yMapping.init(ypos, 1);

    for (int i = 1; i <= n; i++)
    {
        xEvents[yMapping.get_idx(towns[i].yy)].pos.emplace_back(towns[i].xx, i);
        yEvents[xMapping.get_idx(towns[i].xx)].pos.emplace_back(towns[i].yy, i);
    }

    for (int i = 0; i < m; i++)
    {
        xEvents[yMapping.get_idx(st[i].yy)].area.emplace_back(st[i].xx, ed[i].xx + 1);
        xEvents[yMapping.get_idx(ed[i].yy + 1)].area.emplace_back(ed[i].xx + 1, st[i].xx);

        yEvents[xMapping.get_idx(st[i].xx)].area.emplace_back(st[i].yy, ed[i].yy + 1);
        yEvents[xMapping.get_idx(ed[i].xx + 1)].area.emplace_back(ed[i].yy + 1, st[i].yy);
    }

    buildGraph(xMapping, xEvents);
    buildGraph(yMapping, yEvents);

    sort(all(edges), [](const Edge& l, const Edge& r) 
    {
        return l.c < r.c;
    });

    vector<int> used;

    for (int i = 1; i <= n; i++)
        parent[i] = i;

    for (auto& e : edges)
    {
        if (find(e.s) == find(e.e))
            continue;

        merge(e.s, e.e);
        used.push_back(e.c);
    }

    int minNeed = 0;

    for (int i = 1; i <= n; i++)
    {
        if (find(i) != i)
            continue;

        minNeed++;
    }

    used.push_back(0); // sentry
    sort(all(used));

    vector<i64> usedSum(used.size());

    for (int i = 1; i < used.size(); i++)
        usedSum[i] = usedSum[i - 1] + used[i];

    for (int i = 0; i < c; i++)
    {
        i64 b, h;
        scanf("%lld %lld", &b, &h);
        
        if (h < minNeed)
        {
            printf("-1\n");
            continue;
        }

        // 이분 탐색으로, 코스트가 b이상인 맨 왼쪽 간선 찾는다.
        // b이상인것 전부 제외하면 됨
        int ignore = lower_bound(all(used), b) - used.begin();
        int setup = used.size() - ignore;

        i64 total = usedSum[ignore - 1]
            + (minNeed + setup) * b;

        printf("%lld\n", total);
    }

    return 0;
}

Compilation message (stderr)

construction.cpp: In member function 'void Mapping::init(const std::vector<long long int>&, int)':
construction.cpp:38:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < arr.size(); i++)
                         ~~^~~~~~~~~~~~
construction.cpp: In member function 'void FenwickTree::add(int, i64)':
construction.cpp:81:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (n < data.size())
                ~~^~~~~~~~~~~~~
construction.cpp: In function 'void buildGraph(Mapping&, std::vector<Events>&)':
construction.cpp:184:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < es.pos.size() - 1; i++)
                         ~~^~~~~~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:290:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < used.size(); i++)
                     ~~^~~~~~~~~~~~~
construction.cpp:204:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:216:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &towns[i].xx, &towns[i].yy);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:223:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &st[i].xx, &st[i].yy, &ed[i].xx, &ed[i].yy);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:296:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &b, &h);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30