Submission #24905

#	Time	Username	Problem	Language	Result	Execution time	Memory
24905		khsoo01	도로 건설 사업 (JOI13_construction)	C++11	100 / 100	1303 ms	74032 KiB

construction

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> plll;

ll n, m, q, par[200005];
pll a[200005];
vector<ll> xcp, ycp, wgt, sum;
vector<plll> edg;

struct world {
	ll mx, idx[200005];
	vector<ll> xl[200005];
	vector<pll> c, swp[200005];
	set<ll> exi;
	void solve (vector<ll> &B) {
		for(ll i=0;i<c.size();i++) {
			xl[c[i].X].push_back(i);
			mx = max(mx, c[i].X);
		}
		for(ll i=0;i<=mx;i++) {
			for(auto &T : swp[i]) {
				ll S = T.X, E = T.Y;
				while(true) {
					auto it = exi.lower_bound(S);
					if(it == exi.end() || (*it) >= E) break;
					exi.erase(it);
				}
			}
			for(auto &T : xl[i]) {
				if(exi.find(c[T].Y) != exi.end()) {
					ll L = B[c[T].X] - B[c[idx[c[T].Y]].X];
					edg.push_back({L, {T, idx[c[T].Y]}});
				}
				exi.insert(c[T].Y);
				idx[c[T].Y] = T;
			}
		}
	}
} w1, w2;

void compr (ll &X, vector<ll> &V) {
	X = lower_bound(V.begin(), V.end(), X) - V.begin();
}

ll Find (ll X) {
	if(par[X] == X) return X;
	return par[X] = Find(par[X]);
}

int main()
{
	scanf("%lld%lld%lld",&n,&m,&q);
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld",&a[i].X,&a[i].Y);
		xcp.push_back(a[i].X);
		ycp.push_back(a[i].Y);
	}
	sort(xcp.begin(), xcp.end());
	xcp.erase(unique(xcp.begin(), xcp.end()), xcp.end());
	sort(ycp.begin(), ycp.end());
	ycp.erase(unique(ycp.begin(), ycp.end()), ycp.end());
	for(ll i=1;i<=n;i++) {
		compr(a[i].X, xcp);
		compr(a[i].Y, ycp);
		w1.c.push_back({a[i].X, a[i].Y});
		w2.c.push_back({a[i].Y, a[i].X});
	}
	for(ll i=1;i<=m;i++) {
		ll xs, xe, ys, ye;
		scanf("%lld%lld%lld%lld",&xs,&ys,&xe,&ye);
		xe++; ye++;
		compr(xs, xcp); compr(xe, xcp);
		compr(ys, ycp); compr(ye, ycp);
		w1.swp[xs].push_back({ys, ye});
		w2.swp[ys].push_back({xs, xe});
	}
	w1.solve(xcp);
	w2.solve(ycp);
	sort(edg.begin(), edg.end());
	for(ll i=0;i<n;i++) par[i] = i;
	for(auto &T : edg) {
		ll A = T.Y.X, B = T.Y.Y, C = T.X;
		A = Find(A); B = Find(B);
		if(A != B) {
			par[A] = B;
			wgt.push_back(C);
		}
	}
	sort(wgt.begin(), wgt.end());
	for(auto &T : wgt) {
		sum.push_back((sum.empty()?0:sum.back()) + T);
	}
	for(ll i=1;i<=q;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B); B--;
		if(wgt.size() + B < n-1) {puts("-1"); continue;}
		ll I = A; compr(I, wgt);
		ll C = max(n-1-B, I);
		printf("%lld\n",(C?sum[C-1]:0)+(n-C)*A);
	}
}

Compilation message (stderr)

construction.cpp: In member function 'void world::solve(std::vector<long long int>&)':
construction.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll i=0;i<c.size();i++) {
               ^
construction.cpp: In function 'int main()':
construction.cpp:100:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(wgt.size() + B < n-1) {puts("-1"); continue;}
                     ^
construction.cpp:56:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&m,&q);
                                ^
construction.cpp:58:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a[i].X,&a[i].Y);
                                    ^
construction.cpp:74:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld",&xs,&ys,&xe,&ye);
                                            ^
construction.cpp:99:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B); B--;
                          ^

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