oj.uz

Submission #787330

# Submission time Handle Problem Language Result Execution time Memory
787330 2023-07-19T05:40:15 Z 이동현(#10034) 도로 건설 사업 (JOI13_construction) C++17
40 / 100
 5000 ms 89836 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

struct Data{
    int x, y, ey, id;

    Data(){}
    Data(int x, int y, int ey, int id):x(x), y(y), ey(ey), id(id){}

    bool operator<(const Data&r)const{
        return x < r.x;
    }
};

struct Dsu{
    int n;
    vector<int> pr;
    Dsu(int m){
        n = m + 4;
        pr.resize(n);
        iota(pr.begin(), pr.end(), 0);
    }
    int fd(int x){
        return (x == pr[x] ? x : pr[x] = fd(pr[x]));
    }
    bool unite(int x, int y){
        x = fd(x), y = fd(y);
        if(x == y) return false;
        pr[y] = x;
        return true;
    }
};

struct Fenwick{
    int n;
    vector<int> tr;
    Fenwick(int m){
        n = m + 4;
        tr.resize(n);
    }

    void push(int pos, int val){
        ++pos;
        for(int i = pos; i < n; i += (i & -i)){
            tr[i] += val;
        }
    }

    int get(int pos){
        ++pos;
        int rv = 0;
        for(int i = pos; i > 0; i -= (i & -i)){
            rv += tr[i];
        }

        return rv;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, c;
    cin >> n >> m >> c;

    vector<vector<int>> a(n, vector<int>(2)), b(m, vector<int>(4));
    for(int i = 0; i < n; ++i){
        cin >> a[i][0] >> a[i][1];
    }
    for(int i = 0; i < m; ++i){
        cin >> b[i][0] >> b[i][1] >> b[i][2] >> b[i][3];
    }

    vector<vector<int>> way;
    auto makeway = [&](){
        vector<int> srt;
        for(int i = 0; i < n; ++i){
            srt.push_back(a[i][1]);
        }
        for(int i = 0; i < m; ++i){
            srt.push_back(b[i][1]);
            srt.push_back(b[i][3]);
        }
        sort(srt.begin(), srt.end());
        srt.erase(unique(srt.begin(), srt.end()), srt.end());
        for(int i = 0; i < n; ++i){
            a[i][1] = lower_bound(srt.begin(), srt.end(), a[i][1]) - srt.begin();
        }
        for(int i = 0; i < m; ++i){
            b[i][1] = lower_bound(srt.begin(), srt.end(), b[i][1]) - srt.begin();
            b[i][3] = lower_bound(srt.begin(), srt.end(), b[i][3]) - srt.begin();
        }

        vector<Data> que;
        for(int i = 0; i < n; ++i){
            que.push_back(Data(a[i][0], a[i][1], -1, i));
        }
        for(int i = 0; i < m; ++i){
            que.push_back(Data(b[i][0], b[i][1], b[i][3], 1));
        }

        sort(que.begin(), que.end());
        Fenwick tr((int)srt.size());
        vector<int> lst((int)srt.size(), -1), val((int)srt.size());
        for(int i = 0; i < (int)que.size(); ++i){
            if(que[i].ey == -1){
                if(lst[que[i].y] != -1 && tr.get(que[i].y) == val[que[i].y]){
                    way.push_back({que[i].x - que[lst[que[i].y]].x, que[i].id, que[lst[que[i].y]].id});
                }
                lst[que[i].y] = i;
                val[que[i].y] = tr.get(que[i].y);
            }
            else{
                // cout << "LINE " << que[i].x << ' ' << que[i].y << ' ' << que[i].ey + 1 << endl;
                tr.push(que[i].y, que[i].id);
                tr.push(que[i].ey + 1, -que[i].id);
            }
        }

        for(int i = 0; i < n; ++i){
            a[i][1] = srt[a[i][1]];
        }
        for(int i = 0; i < m; ++i){
            b[i][1] = srt[b[i][1]];
            b[i][3] = srt[b[i][3]];
        }
    };

    makeway();
    for(int i = 0; i < n; ++i){
        swap(a[i][0], a[i][1]);
    }
    for(int i = 0; i < m; ++i){
        swap(b[i][0], b[i][1]);
        swap(b[i][2], b[i][3]);
    }
    makeway();

    sort(way.begin(), way.end());

    // for(auto&i:way){
    //     cout << i[0] << ' ' << i[1] << ' ' << i[2] << endl;
    // }

    while(c--){
        Dsu gr(n);

        int x, y;
        cin >> x >> y;

        y = n - y;

        int ans = 0, i, air = n;
        for(i = 0; i < (int)way.size() && y; ++i){
            if(gr.unite(way[i][1], way[i][2])){
                ans += way[i][0];
                --y;
                --air;
            }
        }
        if(y){
            cout << "-1\n";

            continue;
        }
        for(; i < (int)way.size() && way[i][0] < x; ++i){
            if(gr.unite(way[i][1], way[i][2])){
                ans += way[i][0];
                --air;
            }
        }

        ans += air * x;

        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1912 KB Output is correct
2 Correct 360 ms 34844 KB Output is correct
3 Correct 353 ms 34808 KB Output is correct
4 Correct 3292 ms 47752 KB Output is correct
5 Correct 1266 ms 42756 KB Output is correct
6 Correct 431 ms 34868 KB Output is correct
7 Correct 636 ms 49448 KB Output is correct
8 Correct 552 ms 42612 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1912 KB Output is correct
2 Correct 360 ms 34844 KB Output is correct
3 Correct 353 ms 34808 KB Output is correct
4 Correct 3292 ms 47752 KB Output is correct
5 Correct 1266 ms 42756 KB Output is correct
6 Correct 431 ms 34868 KB Output is correct
7 Correct 636 ms 49448 KB Output is correct
8 Correct 552 ms 42612 KB Output is correct
9 Correct 533 ms 74136 KB Output is correct
10 Correct 560 ms 74196 KB Output is correct
11 Correct 569 ms 74208 KB Output is correct
12 Correct 530 ms 74212 KB Output is correct
13 Correct 405 ms 65560 KB Output is correct
14 Correct 740 ms 42860 KB Output is correct
15 Correct 564 ms 74084 KB Output is correct
16 Correct 891 ms 89836 KB Output is correct
17 Correct 828 ms 89728 KB Output is correct
18 Correct 547 ms 81080 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1912 KB Output is correct
2 Correct 360 ms 34844 KB Output is correct
3 Correct 353 ms 34808 KB Output is correct
4 Correct 3292 ms 47752 KB Output is correct
5 Correct 1266 ms 42756 KB Output is correct
6 Correct 431 ms 34868 KB Output is correct
7 Correct 636 ms 49448 KB Output is correct
8 Correct 552 ms 42612 KB Output is correct
9 Execution timed out 5044 ms 35068 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1912 KB Output is correct
2 Correct 360 ms 34844 KB Output is correct
3 Correct 353 ms 34808 KB Output is correct
4 Correct 3292 ms 47752 KB Output is correct
5 Correct 1266 ms 42756 KB Output is correct
6 Correct 431 ms 34868 KB Output is correct
7 Correct 636 ms 49448 KB Output is correct
8 Correct 552 ms 42612 KB Output is correct
9 Correct 533 ms 74136 KB Output is correct
10 Correct 560 ms 74196 KB Output is correct
11 Correct 569 ms 74208 KB Output is correct
12 Correct 530 ms 74212 KB Output is correct
13 Correct 405 ms 65560 KB Output is correct
14 Correct 740 ms 42860 KB Output is correct
15 Correct 564 ms 74084 KB Output is correct
16 Correct 891 ms 89836 KB Output is correct
17 Correct 828 ms 89728 KB Output is correct
18 Correct 547 ms 81080 KB Output is correct
19 Execution timed out 5044 ms 35068 KB Time limit exceeded
20 Halted 0 ms 0 KB -