oj.uz

Submission #289828

# Submission time Handle Problem Language Result Execution time Memory
289828 2020-09-03T06:22:04 Z 반딧불(#5785) None (JOI12_invitation) C++17
100 / 100
 855 ms 30388 KB 
#include <bits/stdc++.h>
#define unq(V) sort(V.begin(), V.end()), V.erase(unique(V.begin(), V.end()), V.end())

using namespace std;

typedef long long ll;

struct Group{
    int p, q, r, s; ll t;
    Group(){}
    Group(int p, int q, int r, int s, ll t): p(p), q(q), r(r), s(s), t(t){}
};

int a, b, c;
int n;
Group group[100002];
ll wA[200002], wB[200002];
ll ans;

void input(){
    ll ra, rb;
    scanf("%d %d %d %d", &a, &b, &c, &n);
    ra = a, rb = b;
    for(int i=1; i<=n; i++){
        scanf("%d %d %d %d %lld", &group[i].p, &group[i].q, &group[i].r, &group[i].s, &group[i].t);
    }

    vector<int> renV (1, 1);
    for(int i=1; i<=n; i++){
        renV.push_back(group[i].p);
        if(group[i].q != a) renV.push_back(group[i].q+1);
    }
    unq(renV); a = (ll)renV.size();
    for(int i=1; i<=n; i++){
        group[i].p = lower_bound(renV.begin(), renV.end(), group[i].p) - renV.begin();
        group[i].q = upper_bound(renV.begin(), renV.end(), group[i].q) - renV.begin() - 1;
    }
    for(int i=0; i<a; i++) wA[i] = (i==a-1 ? ra+1 : renV[i+1]) - renV[i];

    renV = {1};
    for(int i=1; i<=n; i++){
        renV.push_back(group[i].r);
        if(group[i].s != b) renV.push_back(group[i].s+1);
    }
    unq(renV); b = (ll)renV.size();
    for(int i=1; i<=n; i++){
        group[i].r = lower_bound(renV.begin(), renV.end(), group[i].r) - renV.begin();
        group[i].s = upper_bound(renV.begin(), renV.end(), group[i].s) - renV.begin() - 1;
    }
    for(int i=0; i<b; i++) wB[i] = (i==b-1 ? rb+1 : renV[i+1]) - renV[i];
}

struct segTree{
    ll tree[800002], lazy[800002];
    void initialize(int i, int l, int r){
        if(l==r){
            tree[i] = lazy[i] = -1;
            return;
        }
        tree[i] = lazy[i] = -1;
        int m = (l+r)>>1;
        initialize(i*2, l, m), initialize(i*2+1, m+1, r);
    }

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

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

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

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;
    }
};
priority_queue<Edge> pq;

ll aLink[200002], aAlone[200002];
ll bLink[200002], bAlone[200002];

void makeEdges(){
    tree.initialize(1, 0, a-1);
    for(int i=1; i<=n; i++) tree.update(1, 0, a-1, group[i].p, group[i].q, group[i].t);
    for(int i=0; i<a; i++) aAlone[i] = tree.getMax(1, 0, a-1, i, i);

    tree.initialize(1, 0, b-1);
    for(int i=1; i<=n; i++) tree.update(1, 0, b-1, group[i].r, group[i].s, group[i].t);
    for(int i=0; i<b; i++) bAlone[i] = tree.getMax(1, 0, b-1, i, i);

    tree.initialize(1, 0, a-1);
    for(int i=1; i<=n; i++) tree.update(1, 0, a-1, group[i].p, group[i].q-1, group[i].t);
    for(int i=0; i<a-1; i++) aLink[i] = tree.getMax(1, 0, a-1, i, i);

    tree.initialize(1, 0, b-1);
    for(int i=1; i<=n; i++) tree.update(1, 0, b-1, group[i].r, group[i].s-1, group[i].t);
    for(int i=0; i<b-1; i++) bLink[i] = tree.getMax(1, 0, b-1, i, i);

    for(int i=0; i<a; i++){
        if(aAlone[i] == -1){
            printf("-1");
            exit(0);
        }
        ans += aAlone[i] * (wA[i] - 1);
    }
    for(int i=0; i<b; i++){
        if(bAlone[i] == -1){
            printf("-1");
            exit(0);
        }
        ans += bAlone[i] * (wB[i] - 1);
    }

    for(int i=0; i<a-1; i++) if(aLink[i] != -1) pq.push(Edge(i, i+1, aLink[i]));
    for(int i=0; i<b-1; i++) if(bLink[i] != -1) pq.push(Edge(i+a, i+a+1, bLink[i]));

    for(int i=1; i<=n; i++){
        pq.push(Edge(group[i].p, group[i].r+a, group[i].t));
    }
}

int par[400002];
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[y] = x;
}

void kruskal(){
    for(int i=0; i<a+b; i++) par[i] = i;

    while(!pq.empty()){
        Edge tmp = pq.top(); pq.pop();
        if(find(tmp.x) == find(tmp.y)) continue;
        merge(tmp.x, tmp.y);
        ans += tmp.w;
    }

    int tmp = find(0);
    for(int i=0; i<a+b; i++){
        if(find(i) != tmp){
            printf("-1");
            exit(0);
        }
    }

    printf("%lld", ans);
}

int main(){
    input();
    makeEdges();
    kruskal();
}

Compilation message

invitation.cpp: In function 'void input()':
invitation.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%d %d %d %d", &a, &b, &c, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
invitation.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |         scanf("%d %d %d %d %lld", &group[i].p, &group[i].q, &group[i].r, &group[i].s, &group[i].t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1152 KB Output is correct
2 Correct 10 ms 1152 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1152 KB Output is correct
2 Correct 10 ms 1152 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 30388 KB Output is correct
2 Correct 211 ms 6092 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 29896 KB Output is correct
2 Correct 663 ms 29764 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 30264 KB Output is correct
2 Correct 211 ms 6092 KB Output is correct
3 Correct 531 ms 19912 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 29848 KB Output is correct
2 Correct 641 ms 29892 KB Output is correct
3 Correct 527 ms 19784 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 4968 KB Output is correct
2 Correct 692 ms 25804 KB Output is correct
3 Correct 829 ms 30024 KB Output is correct