Submission #787333

# Submission time Handle Problem Language Result Execution time Memory
787333 2023-07-19T05:42:40 Z 반딧불(#10031) 도로 건설 사업 (JOI13_construction) C++17
0 / 100
20 ms 1488 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
void makeEdges();
void getMST();
void answerQuery();

int main(){
    input();
    makeEdges();
    getMST();
    answerQuery();
}

struct Point{
    int x, y, idx;
    Point(){}
    Point(int x, int y): x(x), y(y){}

    bool operator<(const Point &r)const{
        if(y != r.y) return y<r.y;
        return x<r.x;
    }
};

int n, k, q;
Point arr[200002];
int x1[200002], y_1[200002], x2[200002], y2[200002];

void input(){
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &arr[i].x, &arr[i].y);
        arr[i].idx = i;
    }
    for(int i=1; i<=k; i++){
        scanf("%d %d %d %d", &x1[i], &y_1[i], &x2[i], &y2[i]);
    }
}

struct segTree{
    ll tree[1<<21], lazy[1<<21];

    void propagate(int i, int l, int r){
        tree[i] += lazy[i] * (r-l+1);
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    void update(int i, int l, int r, int s, int e, int v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] += v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    ll query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return 0;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
    }
} tree;

struct Query{
    int type;
    int l, r, t, pa, pb;
    Query(){}
    Query(int type, int l, int r, int t): type(type), l(l), r(r), t(t){}

    bool operator<(const Query &nxt)const{
        if(t != nxt.t) return t < nxt.t;
        return type < nxt.type;
    }
};

struct Edge{
    int x, y; ll w;
    Edge(){}
    Edge(int x, int y, ll w): x(x), y(y), w(w){}

    bool operator<(const Edge &r)const{
        return w<r.w;
    }
};
vector<Edge> edges;

void makeEdges(){
    vector<Query> vec;
    vector<Point> points (arr+1, arr+n+1);
    vector<int> xCoord;
    int L;
    int done = 0;

    while(1){
        sort(points.begin(), points.end());
        for(int i=0; i<n-1; i++){
            if(points[i].y == points[i+1].y){
                vec.push_back(Query(0, points[i].x, points[i+1].x, points[i].y));
                vec.back().pa = points[i].idx;
                vec.back().pb = points[i+1].idx;
            }
        }
        for(int i=1; i<=k; i++){
            vec.push_back(Query(-1, x1[i], x2[i], y_1[i]));
            vec.push_back(Query( 1, x1[i], x2[i], y2[i]));
        }
        for(Query p: vec) xCoord.push_back(p.l), xCoord.push_back(p.r);
        sort(xCoord.begin(), xCoord.end());
        xCoord.erase(unique(xCoord.begin(), xCoord.end()), xCoord.end());
        L = (int)xCoord.size();
        for(Query &p: vec){
            p.l = lower_bound(xCoord.begin(), xCoord.end(), p.l) - xCoord.begin();
            p.r = lower_bound(xCoord.begin(), xCoord.end(), p.r) - xCoord.begin();
        }
        sort(vec.begin(), vec.end());
        for(Query &p: vec){
            if(p.type == 0){
                ll v = tree.query(1, 0, L-1, p.l, p.r);
                if(!v) edges.push_back(Edge(p.pa, p.pb, xCoord[p.r]-xCoord[p.l]));
            }
            else tree.update(1, 0, L-1, p.l, p.r, -p.type);
        }

        if(++done == 2) return;
        for(Point &p: points) swap(p.x, p.y);
        for(int i=1; i<=k; i++) swap(x1[i], y_1[i]), swap(x2[i], y2[i]);
        xCoord.clear();
        vec.clear();
    }
}

struct unionFind{
    int par[200002];
    void init(int n){
        for(int i=1; i<=n; i++) par[i] = i;
    }
    int find(int x){
        if(x==par[x]) return x;
        return par[x] = find(par[x]);
    }
    void merge(int x, int y){
        x=find(x), y=find(y);
        par[x] = y;
    }
} dsu;
int l;
ll weight[200002];
ll sum[200002];
int MIN;

void getMST(){
    dsu.init(n);
    sort(edges.begin(), edges.end());
    for(Edge p: edges){
        if(dsu.find(p.x) == dsu.find(p.y)) continue;
        dsu.merge(p.x, p.y);
        weight[++l] = p.w;
    }
    MIN = n-l;
    for(int i=1; i<=l; i++) sum[i] = sum[i-1] + weight[i];

    #ifdef TEST
    printf("%d roads: ", l);
    for(int i=1; i<=l; i++) printf("%lld ", weight[i]);
    puts("");
    #endif
}

void answerQuery(){
    while(q--){
        ll a; int b;
        scanf("%lld %d", &a, &b);
        if(b < MIN){
            puts("-1");
            continue;
        }
        b -= MIN;

        int L = max(l-b+1, 1), R = l, ans = l+1;
        while(L<=R){
            int M=(L+R)/2;
            if(weight[M] > a) ans = M, R = M-1;
            else L = M+1;
        }
        printf("%lld\n", sum[ans-1] + ll(n-ans+1)*a);
    }
}

Compilation message

construction.cpp: In function 'void input()':
construction.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d %d", &arr[i].x, &arr[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d %d %d %d", &x1[i], &y_1[i], &x2[i], &y2[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp: In function 'void answerQuery()':
construction.cpp:185:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         scanf("%lld %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1488 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1488 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1488 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1488 KB Output isn't correct
2 Halted 0 ms 0 KB -