Submission #1197708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197708		InvMOD	도로 건설 사업 (JOI13_construction)	C++17	0 / 100	10 ms	5952 KiB

construction

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back

#define vi vector<int>
#define pi pair<int,int>
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())

template<class T> using upq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int lwrbound(const vector<T>& a, const T& b, const int s = 0){return int(lower_bound(s + all(a), b) - a.begin());}
template<class T> int uprbound(const vector<T>& a, const T& b, const int s = 0){return int(upper_bound(s + all(a), b) - a.begin());}

#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define ROF(i, a, b) for(int i = (a); i >= (b); i--)
#define sumof(x) accumulate(all(x), 0ll)
#define dbg(x) "[" << #x " = " << (x) << "]"
#define el "\n"

using ll = long long;
using ld = long double;

template<class T> bool ckmx(T& a, const T b){return (a < b ? a = b, true : false);}
template<class T> bool ckmn(T& a, const T b){return (a > b ? a = b, true : false);}

struct Edge{
    int u,v; ll w;
    Edge(int u = 0, int v = 0, ll w = 0): u(u), v(v), w(w) {}

    bool operator < (const Edge& q) const{
        return w < q.w;
    }

    bool operator > (const Edge& q) const{
        return w > q.w;
    }
};

struct DSU{
    vector<int> par; int comp;

    DSU(int n = 0): comp(n), par(n + 1, -1) {}

    int asc(int x){
        return par[x] < 0 ? x : par[x] = asc(par[x]);
    }

    bool join(int u, int v){
        u = asc(u), v = asc(v);
        if(u == v) return false;
        if(par[u] > par[v]) swap(u, v);

        par[u] += par[v], par[v] = u, comp--;
        return true;
    }

    int component(){
        return comp;
    }
};

const int N = 2e5 + 5;

int n, m, q, vil[N][2], zone[N][4];

vector<int> comp[2]; vector<pi> event[N]; vector<Edge> E, nE;


void get_edge(){
    FOR(i, 1, n){
        event[vil[i][0]].push_back(make_pair(vil[i][1], i));
    }

    FOR(i, 1, n){
        event[zone[i][0]].push_back(make_pair(zone[i][2], +1));
        event[zone[i][3] + 1].push_back(make_pair(zone[i][2], -1));
    }

    multiset<int> s;
    FOR(tx, 1, sz(comp[0])){
        vector<int> node;

        for(pair<int,int>& e : event[tx]){
            if(e.se == 1) s.insert(e.fi);
            else if(e.se == -1) s.erase(e.fi);
            else node.eb(e.se);
        }

        sort(all(node), [&](int x, int y){
            return vil[x][1] < vil[y][1];
        });

        for(int i = 0; i < sz(node) - 1; i++){
            auto it = s.lower_bound(vil[node[i]][1]);
            if(it != s.end() || *it < vil[node[i + 1]][1]){
                ll w = comp[1][vil[node[i + 1]][1]] - comp[1][vil[node[i]][1]];

                E.push_back(Edge(node[i], node[i + 1], w));
                //cout << node[i] <<" " << node[i + 1] <<" " << w << el;
            }
        }

        event[tx].clear();
    }
}

void init(){
    comp[0].eb(-1), comp[1].eb(-1);

    FOR(i, 0, 1) sort(all(comp[i])), compact(comp[i]);

    FOR(i, 1, n){
        FOR(j, 0, 1){
            vil[i][j] = lwrbound(comp[j], vil[i][j]);
        }
    }

    FOR(i, 1, m){
        FOR(j, 0, 3){
            zone[i][j] = lwrbound(comp[j & 1], vil[i][j]);
        }
    }
}

void Main()
{
    cin >> n >> m >> q;

    FOR(i, 1, n){
        FOR(j, 0, 1){
            cin >> vil[i][j];
            comp[j].eb(vil[i][j]);
        }
    }

    FOR(i, 1, m){
        FOR(j, 0, 3){
            cin >> zone[i][j];
            comp[j & 1].eb(zone[i][j]);
        }
    }
    init(), get_edge();

    swap(comp[0], comp[1]);
    FOR(i, 1, n) swap(vil[i][0], vil[i][1]);
    FOR(i, 1, m) swap(zone[i][0], zone[i][1]), swap(zone[i][2], zone[i][3]);

    get_edge(); sort(all(E));

    DSU dsu(n); nE.pb(Edge());
    for(const Edge& e : E){
        if(dsu.join(e.u, e.v)) nE.pb(e);
    }

    sort(1 + all(nE), greater<Edge>());

    vector<ll> pref(sz(nE));
    FOR(i, 1, sz(nE) - 1){
        pref[i] = pref[i - 1] + nE[i].w;
    }

    while(q--){
        ll cost, Max; cin >> cost >> Max;

        auto calc_ans = [&]() -> ll{
            if(Max < dsu.component()){
                return -1;
            }

            Max -= dsu.component();

            int l = 0, r = min(Max + 1, 1ll * sz(nE));
            while(l + 1 < r){
                int m = l+r>>1;
                if(cost < nE[m].w){
                    l = m;
                }
                else r = m;
            }

            return cost * dsu.component() + pref.back() - pref[l] + 1ll * l * cost;
        };

        cout << calc_ans() << "\n";
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    int t = 1; while(t--) Main();
    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int32_t main()':
construction.cpp:201:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:202:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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