oj.uz

Submission #6774

# Submission time Handle Problem Language Result Execution time Memory
6774 2014-07-06T05:30:12 Z cki86201 수족관 3 (KOI13_aqua3) C++
100 / 100
 260 ms 21816 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10008 KB Output is correct
2 Correct 0 ms 10008 KB Output is correct
3 Correct 0 ms 10008 KB Output is correct
4 Correct 0 ms 10008 KB Output is correct
5 Correct 0 ms 10008 KB Output is correct
6 Correct 0 ms 10008 KB Output is correct
7 Correct 0 ms 10008 KB Output is correct
8 Correct 0 ms 10008 KB Output is correct
9 Correct 0 ms 10008 KB Output is correct
10 Correct 0 ms 10008 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10008 KB Output is correct
2 Correct 0 ms 10008 KB Output is correct
3 Correct 0 ms 10136 KB Output is correct
4 Correct 0 ms 10136 KB Output is correct
5 Correct 0 ms 10136 KB Output is correct
6 Correct 0 ms 10008 KB Output is correct
7 Correct 0 ms 10136 KB Output is correct
8 Correct 0 ms 10136 KB Output is correct
9 Correct 0 ms 10136 KB Output is correct
10 Correct 0 ms 10136 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 16080 KB Output is correct
2 Correct 192 ms 16080 KB Output is correct
3 Correct 168 ms 18416 KB Output is correct
4 Correct 168 ms 18416 KB Output is correct
5 Correct 168 ms 18416 KB Output is correct
6 Correct 172 ms 20528 KB Output is correct
7 Correct 156 ms 21816 KB Output is correct
8 Correct 172 ms 20276 KB Output is correct
9 Correct 252 ms 17004 KB Output is correct
10 Correct 252 ms 17004 KB Output is correct
11 Correct 172 ms 20524 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 16080 KB Output is correct
2 Correct 188 ms 16080 KB Output is correct
3 Correct 164 ms 18412 KB Output is correct
4 Correct 168 ms 18412 KB Output is correct
5 Correct 160 ms 18416 KB Output is correct
6 Correct 188 ms 20520 KB Output is correct
7 Correct 160 ms 21812 KB Output is correct
8 Correct 152 ms 21816 KB Output is correct
9 Correct 236 ms 17004 KB Output is correct
10 Correct 228 ms 17004 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 16924 KB Output is correct
2 Correct 228 ms 16924 KB Output is correct
3 Correct 176 ms 19184 KB Output is correct
4 Correct 192 ms 19184 KB Output is correct
5 Correct 188 ms 19180 KB Output is correct
6 Correct 180 ms 21816 KB Output is correct
7 Correct 196 ms 21816 KB Output is correct
8 Correct 260 ms 17812 KB Output is correct
9 Correct 260 ms 17812 KB Output is correct