oj.uz

Submission #787359

# Submission time Handle Problem Language Result Execution time Memory
787359 2023-07-19T06:08:32 Z 반딧불(#10031) 도로 건설 사업 (JOI13_construction) C++17
10 / 100
 5000 ms 14124 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=0; i<n-1; 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=0; i<n-1; 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 596 KB Output is correct
2 Correct 114 ms 7888 KB Output is correct
3 Correct 113 ms 7980 KB Output is correct
4 Correct 150 ms 14124 KB Output is correct
5 Correct 110 ms 10608 KB Output is correct
6 Correct 101 ms 7884 KB Output is correct
7 Correct 123 ms 14076 KB Output is correct
8 Correct 108 ms 10716 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 596 KB Output is correct
2 Correct 114 ms 7888 KB Output is correct
3 Correct 113 ms 7980 KB Output is correct
4 Correct 150 ms 14124 KB Output is correct
5 Correct 110 ms 10608 KB Output is correct
6 Correct 101 ms 7884 KB Output is correct
7 Correct 123 ms 14076 KB Output is correct
8 Correct 108 ms 10716 KB Output is correct
9 Correct 1406 ms 8936 KB Output is correct
10 Correct 1424 ms 8404 KB Output is correct
11 Correct 839 ms 8372 KB Output is correct
12 Correct 894 ms 8396 KB Output is correct
13 Execution timed out 5034 ms 8608 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 596 KB Output is correct
2 Correct 114 ms 7888 KB Output is correct
3 Correct 113 ms 7980 KB Output is correct
4 Correct 150 ms 14124 KB Output is correct
5 Correct 110 ms 10608 KB Output is correct
6 Correct 101 ms 7884 KB Output is correct
7 Correct 123 ms 14076 KB Output is correct
8 Correct 108 ms 10716 KB Output is correct
9 Execution timed out 5090 ms 9004 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 596 KB Output is correct
2 Correct 114 ms 7888 KB Output is correct
3 Correct 113 ms 7980 KB Output is correct
4 Correct 150 ms 14124 KB Output is correct
5 Correct 110 ms 10608 KB Output is correct
6 Correct 101 ms 7884 KB Output is correct
7 Correct 123 ms 14076 KB Output is correct
8 Correct 108 ms 10716 KB Output is correct
9 Correct 1406 ms 8936 KB Output is correct
10 Correct 1424 ms 8404 KB Output is correct
11 Correct 839 ms 8372 KB Output is correct
12 Correct 894 ms 8396 KB Output is correct
13 Execution timed out 5034 ms 8608 KB Time limit exceeded
14 Halted 0 ms 0 KB -