Submission #1244454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244454		shiori_chan	도로 건설 사업 (JOI13_construction)	C++20	0 / 100	296 ms	49460 KiB

construction

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <set>
#include <queue>
#define all(x) x.begin(), x.end()
#define pi pair <int , int> 

using namespace std;
typedef long long ll;
#define int long long

const int nd = 1e6 + 5e5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1 , (int)2e9);

struct node{
	bool type;
	int x , y , id;
	node(){}
	node(bool type , int x , int y , int id) : type(type) , x(x) , y(y) , id(id){}

	bool operator<(const node &o)const{
		if(x == o.x) return y > o.y;
		return x < o.x;
	}
} point[nd];

set <pair <int , int> > st;

struct EDGE{
	int l , r , w; 
	EDGE(){}
	EDGE(int l , int r , int w) : l(l) , r(r) , w(w){}

	bool operator <(const EDGE &o){
		return w < o.w;
	}
};
vector <EDGE> edge;

vector <int> nt(nd) , tmp(nd);
void build(int timer){
	bool valid = true;
	int yr = 0;
	queue <pi> q; 
	st.clear();
	int cur = -1;

	for(int i = 1;i <= timer; ++ i){
		auto [type , x , y , id] = point[i];
		//cout << x << " " << y << " " << id << " " << type << '\n';
		
		if(type == false){
			if(cur == y){
				auto it = st.lower_bound({y , -1});
				while(it != st.end() && y <= (*it).first && (*it).first <= yr) 
				q.push((*it)) , ++ it;
				
				while(q.size()) st.erase(q.front()) , q.pop();
				cur = -1;
			}
			else{
				if(cur == -1) yr = y , cur = nt[id];
				else cur = min(cur , nt[id]);
				//cout << x << " " << y << " " << id << '\n';
				valid = false;
			}
		}
		else{
			if(valid){
				auto it = st.lower_bound({y , -1});
				if(st.size() && (*it).first == y){
					//cout << point[(*it).second].x << " " << x << '\n';
					edge.push_back(EDGE(point[(*it).second].id , id , x - point[(*it).second].x));
					st.erase(it); 
				}
				st.insert({y , i});
			}
		}
		
		//cout << cur << " " << st.size() << '\n';
		if(cur == -1) valid = true;
	}
}

int par[nd] , sz[nd];
int acs(int x){
	return (x == par[x] ? x : par[x] = acs(par[x]));
}

bool join(int u , int v){
	u = acs(u) , v = acs(v);
	if(u == v) return false;

	if(sz[u] > sz[v]) swap(u , v);
	par[u] = v;
	sz[v] += sz[u];
	return true;
}


bool comp(const int a , const int b){
	return a > b;
}

vector <int> val;
int pref[nd];

void solve(){
	int n , m , c; cin >> n >> m >> c;
	int timer = n;
	for(int i = 1;i <= n; ++ i) 
		cin >> point[i].x >> point[i].y , point[i].id = i , point[i].type = true;
		
	for(int i = 1;i <= m; ++ i){
		int s , t , a , b; cin >> s >> t >> a >> b;
		point[++ timer] = node(false , s , t , timer + 1);
		point[++ timer] = node(false , s , b , timer + 1);
		nt[timer] = t;
		point[++ timer] = node(false , a , b , timer + 1);
		nt[timer] = t; tmp[timer] = s;
		point[++ timer] = node(false , a , t , timer + 1);
		tmp[timer] = s;
	}

	sort(point + 1 , point + 1 + timer);
	build(timer);

	for(int i = 1;i <= timer; ++ i) swap(point[i].x , point[i].y);
		//cout << point[i].type << " " << point[i].id << " " << point[i].x << " " << point[i].y << '\n';
	nt = tmp;
	sort(point + 1 , point + 1 + timer);
	build(timer);

	sort(all(edge));
	int timer2 = timer;
	timer = 0;
	val.push_back(2e9);
	
	int cost_road = 0;
	for(int i = 1; i <= n; ++ i) par[i] = i;

	for(auto e : edge){
		if(join(e.l , e.r)) val.push_back(e.w) , ++ timer , cost_road += e.w;
	}
	sort(all(val) , comp); 
	for(int i = 1;i <= timer; ++ i) 
		pref[i] = pref[i - 1] + val[i];
		//cout << pref[i].first << " " << pref[i].second << '\n';
	int cnt = 0;
	for(int i = 1;i <= n; ++ i) cnt += (i == par[i]);
	//cout << cnt;
	//cout << cost_road << '\n';

	while(c --){
		int h , b; cin >> b >> h;

		if(h < cnt) cout << -1 << '\n';
		else{
			int delta = h - cnt;
			int cost = cost_road + b * cnt;
			//cout << cost << " ";
			if(val[delta] >= b) cost += delta * b - pref[delta];
			else{
				auto it = upper_bound(all(val) , b , comp);
				-- it;
				delta = it - val.begin();
				cost += delta * b - pref[delta];
			}
			cout << cost << '\n';
		}
	}
}

signed main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);

	#define task "task" 
	if(fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	solve();

	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:184:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:185:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30