AOJ 0564 Bug Party, 0575 Festivals in JOI Kingdom

とりあえず本選5番を2つ倒しました。
まずはBug Partyから。

解法

問題名が縁起悪いですね（笑）
…
…
実際バグらせまくりました（汗）
と同時に重大な勘違いに気づくことができました。
K匹同時に入れられるかどうかで二分探索します。
同時に入れられるかを判定するときは許容量が最も少ないものしか影響しません。
そこで、最低許容量を順に下げていきK匹入れられるかチェックすることを考えます。
最低許容量をPとし、許容量がp以上の微生物のうち、放出量が少ないほうからK匹の放出量の合計をXとすると、PK≧XであればK匹入れることが可能です。
具体的には、許容量でソートしてゴニョゴニョするのですが日本語が辛いのでソースを見てください。
seg1[0]はその時点で選ばれているK匹の放出量の最大値,seg2[0]はその微生物のインデックスを表しています。
2^18が300000より大きいと勘違いしてずっと悩んでました…
こういうミスは減らしていきたい…

ソースコード

#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
struct bug{ll in,out;};
int N,size;
int seg1[1<<20],seg2[1<<20];//ここが1<<19になっていた…
bug foo[300050];
bool comp(const bug& a,const bug& b)
{
	return a.in > b.in;
}
struct segtree
{
	segtree(int n)//constructor making segtree
	{
		size=1;
		memset(seg1,0,sizeof(seg1));
		memset(seg2,0,sizeof(seg2));
		while(size<n)size*=2;
	}
	void update(int k,int x)
	{
		k+=size;
		seg1[k]=x;
		seg2[k]=k-size;
		while(k>0)
		{
			k=(k-1)/2;
			if(seg1[k*2+1]>seg1[k*2+2])
			{
				seg1[k]=seg1[k*2+1];
				seg2[k]=seg2[k*2+1];
			}
			else
			{
				seg1[k]=seg1[k*2+2];
				seg2[k]=seg2[k*2+2];
			}
		}
		return;
	}
	int max_id()
	{
		return seg2[0];
	}
	int max_num()
	{
		return seg1[0];
	}
};
bool C(int K)
{
	segtree seg(K);
	ll sum=0ll;
	for(int i=0;i<K-1;i++)
	{
		sum+=(ll)foo[i].out;
		seg.update(i,foo[i].out);
	}
	for(int i=K-1;i<N;i++)
	{
		if(i==K-1)
		{
			sum+=(ll)foo[i].out;
			seg.update(i,foo[i].out);
		}
		else
		{
			if(seg.max_num()>foo[i].out)
			{
				sum-=(ll)(seg.max_num()-foo[i].out);
				seg.update(seg.max_id(),foo[i].out);
			}
		}
		if(sum<=(ll)K*foo[i].in)return true;
	}
	return false;
}
int main()
{
	cin >> N;
	for(int i=0;i<N;i++)cin >> foo[i].out >> foo[i].in;
	sort(foo,foo+N,comp);
	int l=0,r=N;
	while(r>l)
	{
		if(r-l==1)
		{
			if(C(r))l=r;
			break;
		}
		int mid=(l+r)/2;
		if(C(mid))l=mid;
		else r=mid;
	}
	cout << l << endl;
	return 0;
}

勘違いしていたこと、というのは二分探索に関することで、今まで二分探索は

//最大値を求める場合
int l=0,r=MAX_N;
while(r-l>1)
{
        int mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
}
cout << l << endl;

のように書いてきました。
しかし、コレでは答えがMAX_Nの時に正しい答えを出せないことに今までずっと気づきませんでした。どうして今まで二分探索の問題でACできたのか不思議です…
続いてFestivals in JOI Kingdom。

解法

各町の、最も近い祭りをしている町までの距離を町のコストと呼ぶことにします。
まず、各町のコストをdijkstraで計算しておきます。
各道のコストを、その両端の町のコストの最小値とします(その道を通るという事はその両端の町を通るという事なので)。
次にこの道のコストを元に最大全域木を構築します。(最大全域木を通れば、その他の道を通る以上にお祭りから離れて移動できるため)
コレは、Prim法やKruskal法を使えばできます(この場合、合計コストではなく使う辺に注目するのでKruskalのほうが書きやすいかも)
できたものは木なので、ある頂点s,tを行き来するには,s,tのLCAをuとするとs->u,u->tと行くしかありません。
なのでダブリング(今回EulerTour+RMQは不向きだと思う)でLCAを求めて走査してコストの最小値を求めればそれが答えです。
iwiさんの解説スライドに少し工夫をすれば根に近いほどコストが小さくなるようにできるとかいてあったのですがわからないので教えていただければ嬉しいです。

ソースコード

#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <iostream>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define INF 2000000000
#define fi first
#define sec second
#define MAX_N 100000
#define MAX_LOG_V 19
struct edge{int from,to,cost;};
int N,M,K,Q;
vector<edge> g[MAX_N];
vector<edge> all;
int d[MAX_N];
bool f[MAX_N];
int depth[MAX_N];
int parent[MAX_LOG_V][MAX_N];
struct UnionFind
{
	int par[MAX_N];
	int rank[MAX_N];
	void init(int n)
	{
		for(int i=0;i<n;i++)
		{
			par[i]=i;
			rank[i]=0;
		}
		return;
	}
	int find(int i)
	{
		if(par[i]==i)return i;
		else return find(par[i]);
	}
	void unite(int a,int b)
	{
		a=find(a);
		b=find(b);
		if(rank[a]>rank[b])
		{
			par[b]=a;
		}
		else
		{
			par[a]=b;
			if(rank[a]==rank[b])rank[b]++;
		}
		return;
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
};
void dijkstra()
{
	priority_queue<P,vector<P>,greater<P> > q;
	for(int i=0;i<N;i++)
	{
		d[i]=INF;
		if(f[i])
		{
			d[i]=0;
			q.push(mp(0,i));
		}
	}
	while(!q.empty())
	{
		P a=q.top();
		q.pop();
		int v=a.sec;
		if(d[v]<a.fi)continue;
		for(int i=0;i<g[v].size();i++)
		{
			if(d[g[v][i].to]>d[v]+g[v][i].cost)
			{
				d[g[v][i].to]=d[v]+g[v][i].cost;
				q.push(mp(d[g[v][i].to],g[v][i].to));
			}
		}
	}
	return;
}
void dfs(int v,int p,int d)
{
	parent[0][v]=p;
	depth[v]=d;
	for(int i=0;i<g[v].size();i++)
	{
		if(g[v][i].to!=p)
		{
			dfs(g[v][i].to,v,d+1);
		}
	}
	return;
}
void init()
{
	dfs(0,-1,0);
	for(int k=0;k<MAX_LOG_V-1;k++)
	{
		for(int i=0;i<N;i++)
		{
			if(parent[k][i]==-1)parent[k+1][i]=-1;
			else parent[k+1][i]=parent[k][parent[k][i]];
		}
	}
	return;
}
int lca(int u,int v)
{
	int res=min(d[u],d[v]);
	if(depth[u]>depth[v])swap(u,v);
	int x=u,y=v;
	for(int i=0;i<MAX_LOG_V;i++)
	{
		if((depth[v]-depth[u])>>i&1)
		{
			v=parent[i][v];
		}
	}
	if(u==v)goto skip;
	for(int i=MAX_LOG_V-1;i>=0;i--)
	{
		if(parent[i][u]!=parent[i][v])
		{
			u=parent[i][u];
			v=parent[i][v];
		}
	}
	u=parent[0][u];
	skip:;
	while(x!=u)
	{
		x=parent[0][x];
		res=min(res,d[x]);
	}
	while(y!=u)
	{
		y=parent[0][y];
		res=min(res,d[y]);
	}
	return res;
}
bool comp(const edge& x,const edge& y)
{
	return x.cost > y.cost;
}
void input()
{
	cin >> N >> M >> K >> Q;
	for(int i=0;i<M;i++)
	{
		edge e;
		cin >> e.from >> e.to >> e.cost;
		e.from--;e.to--;
		all.pb(e);
		g[e.from].pb(e);
		swap(e.from,e.to);
		g[e.from].pb(e);
	}
	memset(f,false,sizeof(f));
	for(int i=0;i<K;i++)
	{
		int fes;
		cin >> fes;
		fes--;
		f[fes]=true;
	}
	dijkstra();
	for(int i=0;i<all.size();i++)
	{
		all[i].cost=min(d[all[i].from],d[all[i].to]);
	}
	for(int i=0;i<N;i++)
	{
		g[i].clear();
	}
	sort(all.begin(),all.end(),comp);
	UnionFind uf;
	uf.init(N);
	for(int i=0;i<all.size();i++)
	{
		int a=all[i].from,b=all[i].to;
		if(!uf.same(a,b))
		{
			edge e=all[i];
			g[a].pb(e);
			swap(e.from,e.to);
			g[b].pb(e);
			uf.unite(a,b);
		}
	}
	init();
	for(int i=0;i<Q;i++)
	{
		int s,t;
		cin >> s >> t;
		s--;t--;
		cout << lca(s,t) << endl;
	}
	return;
} 
int main()
{
	input();
	return 0;
}