| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 787353 |
2023-07-19T06:04:38 Z |
반딧불(#10031) |
도로 건설 사업 (JOI13_construction) |
C++17 |
|
16 ms |
852 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;
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
