JOI 春合宿 2010 Day 3

何日か前にやったのに書くの忘れてた

本選会場

うまいこと待ってやれば、最小全域木のコスト分しかかからない。K個まで分割することが許されるので、全域木に含まれる辺からコストの大きい順にK-1個とって木をK個に分割してやればいい。

int N,M,K;
struct edge
{
	int from,to,cost;
	edge(int from,int to,int cost):from(from),to(to),cost(cost){}
	bool operator < (const edge& a) const
	{
		return cost < a.cost;
	}
};
struct UnionFind
{
	int par[100100],rank[100100];
	void init(){rep(i,100100)par[i]=i;}
	int find(int x)
	{
		if(par[x]==x)return x;
		return par[x]=find(par[x]);
	}
	void unite(int a,int b)
	{
		a = find(a);
		b = find(b);
		if(a==b)return;
		if(rank[a]<rank[b])par[a]=b;
		else
		{
			par[b]=a;
			if(rank[a]==rank[b])rank[a]++;
		}
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
}uf;
vector<edge> es;
int main()
{
	scanf("%d %d %d",&N,&M,&K);
	rep(i,M)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		es.pb(edge(a,b,c));
	}
	sort(all(es));
	uf.init();
	int cnt = 0,ans = 0;
	rep(i,es.size())
	{
		if(cnt==N-K)break;
		if(uf.same(es[i].from,es[i].to))continue;
		uf.unite(es[i].from,es[i].to);
		cnt++;
		ans += es[i].cost;
	}
	printf("%d\n",ans);
	return 0;
}

かくれんぼ

よくある感じのsegtreeで平面走査。
すんなり書けた。
前に一度解いたことがあるらしいけど、全然覚えてなかったので初見と同じ感覚で解いた。
前解いたときは何日もつかった気がするけど今回はサクッと解けたのでなんとなく成長を感じた(?)

const int SIZE = 1<<17;
struct segtree
{
	int seg[SIZE*2],lazy[SIZE*2];
	void lazy_evaluate(int k)
	{
		seg[k]+=lazy[k];
		if(k<SIZE-1)
		{
			lazy[2*k+1]+=lazy[k];
			lazy[2*k+2]+=lazy[k];
		}
		lazy[k]=0;
	}
	void update(int a,int b,int k,int l,int r,int x)
	{
		lazy_evaluate(k);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b)
		{
			lazy[k]+=x;
			lazy_evaluate(k);
		}
		else
		{
			update(a,b,k*2+1,l,(l+r)/2,x);
			update(a,b,k*2+2,(l+r)/2,r,x);
			seg[k] = max(seg[k*2+1],seg[k*2+2]);
			return;
		}
	}
	int query(int a,int b,int k,int l,int r)
	{
		lazy_evaluate(k);
		if(r<=a||b<=l)return 0;
		if(a<=l&&r<=b)return seg[k];
		else
		{
			int lch = query(a,b,k*2+1,l,(l+r)/2);
			int rch = query(a,b,k*2+2,(l+r)/2,r);
			seg[k] = max(seg[k*2+1],seg[k*2+2]);
			return max(lch,rch);
		}
	}
	int value(int v){return seg[v]+lazy[v];}
	int get_index(int x)
	{
		int p=0;
		while(p<SIZE-1)
		{
			lazy_evaluate(p);
			if(value(2*p+1)>=x)p = p*2+1;
			else p = p*2+2;
		}
		return p-(SIZE-1);
	}
}seg;
int N,M;
struct obstacle
{
	int x,y,w;
	obstacle(int x,int y,int w):x(x),y(y),w(w){}
	bool operator < (const obstacle a) const
	{
		if(y!=a.y)return y < a.y;
		return x < a.x;
	}
};
int a[100100],ans_x[100100],ans_y[100100];
vector<int> weapon;
vector<obstacle> obs;
int main()
{
	scanf("%d %d",&N,&M);
	rep(i,N)
	{
		int x,y,w;
		scanf("%d %d %d",&x,&y,&w);
		obs.pb(obstacle(x,y,w));
	}
	sort(all(obs));
	rep(i,M)
	{
		scanf("%d",&a[i]);
		weapon.pb(a[i]);
	}
	sort(all(weapon));
	weapon.erase(unique(all(weapon)),weapon.end());
	memset(ans_x,-1,sizeof(ans_x));
	memset(ans_y,-1,sizeof(ans_y));
	int id = 0;
	rep(i,obs.size())
	{
		seg.update(obs[i].x,obs[i].x+obs[i].w,0,0,SIZE,1);
		int max_val = seg.query(0,SIZE,0,0,SIZE);
		while(id<M&&weapon[id]<max_val)
		{
			ans_y[id] = obs[i].y;
			ans_x[id] = seg.get_index(weapon[id]+1);
			id++;
		}
	}
	rep(i,M)
	{
		int k = lower_bound(all(weapon),a[i])-weapon.begin();
		printf("%d %d\n",ans_x[k],ans_y[k]);
	}
	return 0;
}

シムロード

実は始めてのOutput onlyだった。
シュタイナー木やんこれ、ってなって適当にdijkstraで貪欲チックにやったら96.3点も帰ってきて
驚愕。snukeさんどうやって解いてるんだろう…

string s[105];
int d[105][105];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int W,H;
P village[10010];
P prev[10010];
int sx,sy;
void dijkstra()
{
	rep(i,H)rep(j,W)d[i][j]=INF;
	rep(i,H)rep(j,W)prev[i*W+j]=P(-1,-1);
	d[sx][sy]=0;
	priority_queue<T,vector<T>,greater<T> > q;
	q.push(T(0,P(sx,sy)));
	while(!q.empty())
	{
		T a = q.top();
		q.pop();
		rep(i,4)
		{
			int nx=a.sec.fi+dx[i],ny=a.sec.sec+dy[i];
			if(nx<0||nx>=H||ny<0||ny>=W)continue;
			int ne = a.fi;
			if(s[nx][ny]=='w')ne++;
			if(d[nx][ny]>ne)
			{
				d[nx][ny]=ne;
				prev[nx*W+ny]=a.sec;
				q.push(T(ne,P(nx,ny)));
			}
		}
	}
}
void cut(int v)
{
	P cur = village[v];
	while(1)
	{
		cur = prev[cur.fi*W+cur.sec];
		if(cur==village[0])break;
		if(s[cur.fi][cur.sec]=='w')s[cur.fi][cur.sec]='.';
	}
	return;
}
int main()
{
	scanf("%d %d",&W,&H);
	rep(i,H)cin >> s[i];
	int num = 0;
	rep(i,H)rep(j,W)if(s[i][j]=='@')village[num++]=P(i,j);
	sx = village[0].fi,sy = village[0].sec;
	while(1)
	{
		dijkstra();
		int mv,mn=INF;
		rep(i,num)
		{
			if(d[village[i].fi][village[i].sec]<=0)continue;
			if(mn>d[village[i].fi][village[i].sec])
			{
				mn = d[village[i].fi][village[i].sec];
				mv = i;
			}
		}
		if(mn==INF)break;
		cut(mv);
	}
	rep(i,H)cout << s[i] << endl;
	return 0;
}

100+100+96.3 = 296.3
全完出来なくて悲しいけどわりと嬉しい点数だった