Submission #6774

#	Time	Username	Problem	Language	Result	Execution time	Memory
6774		cki86201	수족관 3 (KOI13_aqua3)	C++98	100 / 100	260 ms	21816 KiB

aqua3

#include<stdio.h>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;

#define X first
#define Y second
typedef pair<int,int> Pi;
typedef long long ll;
typedef pair<ll, int> Pl;

struct str{
	str(){}
	str(int h,int l,int r):h(h),l(l),r(r){}
	int h, l, r;
	bool operator<(const str &a)const{
		return h!=a.h ? h<a.h : r<a.r;
	}
}inp[150050];

struct tree{
	static const int N_ = 150050;
	int st[N_], en[N_<<1], nxt[N_<<1], sz, par[N_], chk[N_], mx[N_];
	ll val[N_], mxv[N_];
	void addE(int s,int e,int c){nxt[c]=st[s],st[s]=c,en[c]=e;}
	void update(int p,ll v){
		val[++sz] = v;
		addE(sz, p, sz*2-1);
		addE(p, sz, sz*2);
	}
	void dfs(int x,int fa){
		for(int i=st[x];i;i=nxt[i]){
			if(en[i] != fa){
				par[en[i]] = x;
				dfs(en[i], x);
				if(mx[x] == 0 || mxv[mx[x]] < mxv[en[i]])mx[x] = en[i];
			}
		}
		mxv[x] = mxv[mx[x]] + val[x];
	}
	ll solve(int k){
		dfs(1,-1);
		priority_queue <Pl> pq;
		pq.push(Pl(mxv[1], 1));
		ll res = 0;
		while(k-- && !pq.empty()){
			Pl t = pq.top();
			pq.pop();
			res += t.X;
			for(int i=t.Y;i;i=mx[i]){
				for(int j=st[i];j;j=nxt[j]){
					if(par[i] != en[j] && !chk[en[j]] && en[j] != mx[i]){
						pq.push(Pl(mxv[en[j]], en[j]));
					}
				}
				chk[i] = 1;
			}
		}
		return res;
	}
}Tr;

int n, k, R;
map <int, int> M;
map <int, int>::iterator it1, it2;

int main(){
	scanf("%d",&n);
	int i;
	scanf("%*d%*d");
	n = n/2 - 1;
	for(i=0;i<n;i++){
		int x, y, z;
		scanf("%d%d%d%*d",&x,&y,&z);
		inp[i] = str(y, x, z);
	}
	scanf("%d%*d",&R);
	sort(inp,inp+n);
	M[0] = -1;
	M[R+R] = -1;
	M[inp[0].r+inp[0].l] = 0;
	Tr.val[1] = (ll)R * inp[0].h, Tr.sz = 1;
	for(i=1;i<n;i++){
		it2 = M.upper_bound(inp[i].r+inp[i].l);
		it1 = it2;
		--it1;
		int wid = (it2->Y==-1 ? R : inp[it2->Y].l) - (it1->Y==-1 ? 0 : inp[it1->Y].r);
		if(it1->Y > it2->Y)Tr.update(it1->Y+1, (ll)(inp[i].h - inp[it1->Y].h) * wid);
		else Tr.update(it2->Y+1, (ll)(inp[i].h - inp[it2->Y].h) * wid);
		M[inp[i].r+inp[i].l] = i;
	}
	scanf("%d",&k);
	printf("%lld",Tr.solve(k));
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 21 / 21
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16