oj.uz

Submission #787872

# Submission time Handle Problem Language Result Execution time Memory
787872 2023-07-19T13:43:33 Z puppy 도로 건설 사업 (JOI13_construction) C++17
40 / 100
 5000 ms 172072 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
vector<int> cpx, cpy;
int N, M, C, x[200005], y[200005], P[200005], Q[200005], R[200005], S[200005];
vector<int> xlist[600005], ylist[600005];
struct UnionFind
{
    vector<int> par;
    UnionFind(int n){par.resize(n+1); for(int i=1;i<=n;i++) par[i] = i;}
    int fin(int i){return i==par[i]?i:(par[i] = fin(par[i]));}
    void uni(int u, int v){par[fin(u)] = fin(v);}
    bool isuni(int u, int v){return fin(u) == fin(v);}
};
vector<pair<int, pair<int, int>>> edge;
vector<pair<int, pair<int, int>>> redge;
vector<pair<int, pair<int, int>>> cand;
int maxc;
int tree[600005];
const long long inf = 1e18;
void init()
{
    fill(tree, tree + 600005, 0);
}
void upd(int id, int x)
{
    for (int i = id; i <= maxc; i += i&-i) tree[i] += x;
}
int query(int id)
{
    int ret = 0;
    for (int i = id; i; i -= i&-i) ret += tree[i];
    return ret;
}
int sum(int l, int r)
{
    return query(r) - query(l-1);
}
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> M >> C;
    for (int i = 1; i <= N; i++) {
        cin >> x[i] >> y[i];
        cpx.push_back(x[i]);
        cpy.push_back(y[i]);
    }
    for (int i = 1; i <= M; i++) {
        cin >> P[i] >> Q[i] >> R[i] >> S[i];
        cpx.push_back(P[i]); cpx.push_back(R[i]);
        cpy.push_back(Q[i]); cpy.push_back(S[i]);
    }
    sort(cpx.begin(), cpx.end());
    sort(cpy.begin(), cpy.end());
    for (int i = 1; i <= N; i++) {
        x[i] = lower_bound(cpx.begin(), cpx.end(), x[i]) - cpx.begin() + 1;
        y[i] = lower_bound(cpy.begin(), cpy.end(), y[i]) - cpy.begin() + 1;
    }
    for (int i = 1; i <= M; i++) {
        P[i] = lower_bound(cpx.begin(), cpx.end(), P[i]) - cpx.begin() + 1;
        R[i] = lower_bound(cpx.begin(), cpx.end(), R[i]) - cpx.begin() + 1;
        Q[i] = lower_bound(cpy.begin(), cpy.end(), Q[i]) - cpy.begin() + 1;
        S[i] = lower_bound(cpy.begin(), cpy.end(), S[i]) - cpy.begin() + 1;
    }
    for (int i = 1; i <= N; i++) {
        xlist[x[i]].push_back(i);
        ylist[y[i]].push_back(i);
    }
    maxc = N + 2 * M;
    for (int i = 1; i <= maxc; i++) {
        sort(xlist[i].begin(), xlist[i].end(), [&](int p, int q){return y[p] < y[q];});
        for (int j = 0; j < (int)xlist[i].size() - 1; j++) {
            edge.push_back(make_pair(cpy[y[xlist[i][j+1]]-1] - cpy[y[xlist[i][j]]-1], make_pair(xlist[i][j], xlist[i][j+1])));
        }
    }
    for (int i = 1; i <= maxc; i++) {
        sort(ylist[i].begin(), ylist[i].end(), [&](int p, int q){return x[p] < x[q];});
        for (int j = 0; j < (int)ylist[i].size() - 1; j++) {
            edge.push_back(make_pair(cpx[x[ylist[i][j+1]]-1] - cpx[x[ylist[i][j]]-1], make_pair(ylist[i][j], ylist[i][j+1])));
        }
    }
    sort(edge.begin(), edge.end());
    vector<vector<int>> linex(maxc+2), liney(maxc+2);
    vector<vector<int>> rectx(maxc+2), recty(maxc+2);
    for (int i = 0; i < (int)edge.size(); i++) {
        if (x[edge[i].second.first] == x[edge[i].second.second]) {
            linex[x[edge[i].second.first]].push_back(i);
        }
        else {
            liney[y[edge[i].second.first]].push_back(i);
        }
    }
    for (int i = 1; i <= M; i++) {
        rectx[P[i]].push_back(Q[i]);
        rectx[P[i]].push_back(S[i]);
        rectx[R[i]+1].push_back(-Q[i]);
        rectx[R[i]+1].push_back(-S[i]);
        recty[Q[i]].push_back(P[i]);
        recty[Q[i]].push_back(R[i]);
        recty[S[i]+1].push_back(-P[i]);
        recty[S[i]+1].push_back(-R[i]);
    }
    init();
    for (int i = 1; i <= maxc; i++) {
        for (int j:rectx[i]) {
            if (j > 0) upd(j, 1);
            else upd(-j, -1);
        }
        for (int j:linex[i]) {
            if (sum(y[edge[j].second.first], y[edge[j].second.second]) == 0) redge.push_back(edge[j]);
        }
    }
    init();
    for (int i = 1; i <= maxc; i++) {
        for (int j:recty[i]) {
            if (j > 0) upd(j, 1);
            else upd(-j, -1);
        }
        for (int j:liney[i]) {
            if (sum(x[edge[j].second.first], x[edge[j].second.second]) == 0) redge.push_back(edge[j]);
        }
    }
    sort(redge.begin(), redge.end());
    UnionFind uf(N);
    for (auto i:redge) {
        if (uf.isuni(i.second.first, i.second.second)) continue;
        cand.push_back(i);
        uf.uni(i.second.first, i.second.second);
    }
    vector<int> weight;
    for (auto i:cand) weight.push_back(i.first);
    vector<long long> costs(weight.size()+1);
    for (int i = 1; i <= weight.size(); i++) costs[i] = costs[i-1] + weight[i-1];
    for (int i = 1; i <= C; i++) {
        long long ans = inf;
        long long b, k; cin >> b >> k;
        for (int j = 1; j <= k; j++) {
            if (weight.size() >= N - j) ans = min(ans, costs[N-j] + b * j);
        }
        if (ans == inf) cout << -1 << '\n';
        else cout << ans << '\n';
    }
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:135:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = 1; i <= weight.size(); i++) costs[i] = costs[i-1] + weight[i-1];
      |                     ~~^~~~~~~~~~~~~~~~
construction.cpp:140:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  140 |             if (weight.size() >= N - j) ans = min(ans, costs[N-j] + b * j);
      |                 ~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 36524 KB Output is correct
2 Correct 353 ms 87768 KB Output is correct
3 Correct 294 ms 88048 KB Output is correct
4 Correct 389 ms 100384 KB Output is correct
5 Correct 308 ms 93372 KB Output is correct
6 Correct 296 ms 88312 KB Output is correct
7 Correct 197 ms 99832 KB Output is correct
8 Correct 203 ms 93616 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 36524 KB Output is correct
2 Correct 353 ms 87768 KB Output is correct
3 Correct 294 ms 88048 KB Output is correct
4 Correct 389 ms 100384 KB Output is correct
5 Correct 308 ms 93372 KB Output is correct
6 Correct 296 ms 88312 KB Output is correct
7 Correct 197 ms 99832 KB Output is correct
8 Correct 203 ms 93616 KB Output is correct
9 Correct 997 ms 160044 KB Output is correct
10 Correct 983 ms 160088 KB Output is correct
11 Correct 948 ms 159924 KB Output is correct
12 Correct 1065 ms 159916 KB Output is correct
13 Correct 678 ms 157500 KB Output is correct
14 Correct 306 ms 93384 KB Output is correct
15 Correct 953 ms 160016 KB Output is correct
16 Correct 376 ms 172072 KB Output is correct
17 Correct 361 ms 171436 KB Output is correct
18 Correct 533 ms 162112 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 36524 KB Output is correct
2 Correct 353 ms 87768 KB Output is correct
3 Correct 294 ms 88048 KB Output is correct
4 Correct 389 ms 100384 KB Output is correct
5 Correct 308 ms 93372 KB Output is correct
6 Correct 296 ms 88312 KB Output is correct
7 Correct 197 ms 99832 KB Output is correct
8 Correct 203 ms 93616 KB Output is correct
9 Execution timed out 5047 ms 89500 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 36524 KB Output is correct
2 Correct 353 ms 87768 KB Output is correct
3 Correct 294 ms 88048 KB Output is correct
4 Correct 389 ms 100384 KB Output is correct
5 Correct 308 ms 93372 KB Output is correct
6 Correct 296 ms 88312 KB Output is correct
7 Correct 197 ms 99832 KB Output is correct
8 Correct 203 ms 93616 KB Output is correct
9 Correct 997 ms 160044 KB Output is correct
10 Correct 983 ms 160088 KB Output is correct
11 Correct 948 ms 159924 KB Output is correct
12 Correct 1065 ms 159916 KB Output is correct
13 Correct 678 ms 157500 KB Output is correct
14 Correct 306 ms 93384 KB Output is correct
15 Correct 953 ms 160016 KB Output is correct
16 Correct 376 ms 172072 KB Output is correct
17 Correct 361 ms 171436 KB Output is correct
18 Correct 533 ms 162112 KB Output is correct
19 Execution timed out 5047 ms 89500 KB Time limit exceeded
20 Halted 0 ms 0 KB -