oj.uz

답안 #787357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
787357 2023-07-19T06:06:46 Z 반딧불(#10031) 도로 건설 사업 (JOI13_construction) C++17
0 / 100
 14 ms 596 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<Point> points (arr+1, arr+n+1);
    sort(points.begin(), points.end());
    for(int i=1; i<n; i++){
        if(points[i].y != points[i+1].y) continue;
        bool good = 1;
        for(int j=1; j<=k; j++){
            if(y_1[j]<=points[i].y && points[i].y<=y2[j] && !(x2[j] < points[i].x || points[i+1].x < x1[j])){
                good = 0;
                break;
            }
        }
        if(good) edges.push_back(Edge(points[i].idx, points[i+1].idx, points[i+1].x - points[i].x));
    }
    sort(points.begin(), points.end(), [&](Point a, Point b){
        if(a.x!=b.x) return a.x<b.x;
        return a.y<b.y;
    });
    for(int i=1; i<n; i++){
        if(points[i].x != points[i+1].x) continue;
        bool good = 1;
        for(int j=1; j<=k; j++){
            if(x1[j]<=points[i].x && points[i].x<=x2[j] && !(y2[j] < points[i].y || points[i+1].y < y_1[j])){
                good = 0;
                break;
            }
        }
        if(good) edges.push_back(Edge(points[i].idx, points[i+1].idx, points[i+1].y - points[i].y));
    }

    return;

//    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;

        ll ans = MIN * a;
        for(int i=l; i>=1; i--){
            if(b>0) b--, ans += min(weight[i], a);
            else ans += weight[i];
        }
        printf("%lld\n", ans);

//        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:216:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |         scanf("%lld %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -