tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

Codeforces Round #310 (Div. 1)

Codeforces

久しぶりに参加しました。全問やるだけセットなんて初めて見た。

A:
やるだけ。

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

int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int v=0;
	for(int i=0;i<b;i++){
		int c;scanf("%d",&c);
		int last=0;
		int len=0;
		for(int j=0;j<c;j++){
			int p;scanf("%d",&p);
			if(p==last+1){
				last++;
				len++;
			}
		}
		v=max(v,len);
	}
	printf("%d\n",(a-b-v+1)+(a-v));
}

B:
やるだけ。

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
long long L[210000];
long long R[210000];
long long c[210000];
int ret[210000];
pair<long long,int> z[210000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	long long ll,lr;
	for(int i=0;i<a;i++){
		long long p,q;
		scanf("%lld%lld",&p,&q);
		if(i){
			L[i-1]=p-lr;
			R[i-1]=q-ll;
			z[i-1]=make_pair(R[i-1],i-1);
		}
		ll=p;
		lr=q;
	}
	a--;
	std::sort(z,z+a);
	for(int i=0;i<b;i++)scanf("%lld",c+i);
	bool ok=true;
	set<pair<long long,int> > S;
	for(int i=0;i<b;i++)S.insert(make_pair(c[i],i));
	S.insert(make_pair(1000000000000000001LL,0));
	for(int i=0;i<a;i++){
		long long left=L[z[i].second];
		long long right=R[z[i].second];
		pair<long long,int> val=*(S.lower_bound(make_pair(left,0)));
		if(val.first>right){
			ok=false;break;
		}
		ret[z[i].second]=val.second;
		S.erase(val);
	}
	if(!ok)printf("No\n");
	else{
		printf("Yes\n");
		for(int i=0;i<a;i++){
			if(i)printf(" ");
			printf("%d",ret[i]+1);
		}
		printf("\n");
	}
}

C:
やるだけ。

#include<stdio.h>
#include<set>
#include<algorithm>
using namespace std;
int row[210000];
int col[210000];
char dir[210000];
int segtree[2][524288];
int z[210000];
set<pair<int,char> > S;
void update(int a,int b,int c,int d,int e,int t,int to){
	if(d<a||b<c)return ;
	if(c<=a&&b<=d){
		segtree[t][e]=max(segtree[t][e],to);return;
	}
	update(a,(a+b)/2,c,d,e*2,t,to);
	update((a+b)/2+1,b,c,d,e*2+1,t,to);
}
int query(int t,int at){
	int ret=0;
	at+=262144;
	while(at){
		ret=max(segtree[t][at],ret);
		at/=2;
	}
	return ret;
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		scanf("%d%d%s",col+i,row+i,dir+i);
		row[i]--;col[i]--;
		z[i]=col[i];
	}
	std::sort(z,z+b);
	for(int i=0;i<b;i++){
		if(S.count(make_pair(col[i],dir[i]))){
			printf("0\n");continue;
		}
		S.insert(make_pair(col[i],dir[i]));
		int at=lower_bound(z,z+b,col[i])-z;
		if(dir[i]=='U'){
			int to=query(0,at);
			printf("%d\n",row[i]+1-to);
			int tmp=lower_bound(z,z+b,a-to)-z;
			update(0,262143,at,tmp,1,1,col[i]+1);
		}else{
			int to=query(1,at);
			printf("%d\n",col[i]+1-to);
			int tmp=lower_bound(z,z+b,to-1)-z;
			update(0,262143,tmp,at,1,0,row[i]+1);
		}
	}
}

D:
シミュレーション。

#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
int c[210000];
int z[210000];
map<int,int> ans;
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",c+i);
		z[i]=c[i];
		ans[c[i]]=i;
	}
	z[a++]=-2010000000;
	z[a++]=2010000000;
	std::sort(z,z+a);
	
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		int at=c[p-1];
		int len=q;
		int lr=-1000000007;
		int ll=-1000000007;
		while(1){
			bool turn=false;
			int use=0;
			int to=*(upper_bound(z,z+a,at+len)-1);
			if(to>at){
				turn=true;
				use+=to-at;
				len-=to-at;
				at=to;
			}
			int to2=*(lower_bound(z,z+a,at-len));
			if(to2<at){
				turn=true;
				use+=at-to2;
				len-=at-to2;
				at=to2;
			}
			if(!turn)break;
			if(lr==to&&ll==to2){
				len%=use;
			}
			lr=to;
			ll=to2;
		}
		printf("%d\n",ans[at]+1);
	}
}

E:
dfsinfoライブラリを張ってあとはひたすら気合。segtreeとライブラリ部分の配列のサイズが足りなくて通らなかった。250行もあるしどうしようもない。

#include<stdio.h>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<string.h>
#include<vector>
#define MAXN 210000
using namespace std;
int ptr[410000];
int next[410000];
int zu[410000];
int zeit, dis[MAXN], fin[MAXN], low[MAXN], par[MAXN], dep[MAXN];
int kodat[MAXN], koptr[MAXN + 1];
//よく考えると250行とはいえ不要なライブラリ部分とか繰り返しとかも多いのであんまりボリューム感はない
int UF[210000];
vector<int>g[210000];
vector<int>g2[210000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
int uf[210000];
int fi(int a){
	if(uf[a]<0)return a;
	return uf[a]=fi(uf[a]);
}
void uni(int a,int b){
	a=fi(a);b=fi(b);if(a==b)return;uf[a]+=uf[b];uf[b]=a;
}

int L[210000];
int R[210000];
int tmp[420000];
int conv[210000];
int bit[2][210000];
int pos[210000];
int rev[210000];
int sz;
int cur;
int sum(int a,int b,int t){
	if(a)return sum(0,b,t)-sum(0,a-1,t);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[t][b];
	return ret;
}
void add(int a,int b,int t){
	for(;a<n;a|=a+1){
		bit[t][a]+=b;
	}
}
int segtree[1048576];
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 99999999;
	if(c<=a&&b<=d)return segtree[e];
	return min(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
void update(int a,int b){
	a+=524288;
	while(a){
		segtree[a]=min(segtree[a],b);
		a/=2;
	}
}
void dfs(int a,int b){
	tmp[cur++]=a;
	conv[a]=sz;
	rev[sz++]=a;
	for(int i=0;i<g2[a].size();i++){
		if(g2[a][i]==b)continue;
		dfs(g2[a][i],a);
		tmp[cur++]=a;
	}
}
void dfs2(int a,int b){
	L[a]=cur++;
	for(int i=0;i<g2[a].size();i++){
		if(g2[a][i]==b)continue;
		dfs2(g2[a][i],a);
	}
	R[a]=cur-1;
}
set<pair<int,int> > S;
int P[210000];
int Q[210000];
int A[210000];
int B[210000];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++){
		UF[i]=-1;
		uf[i]=-1;
	}
	int m=0;
	n=a;
	for(int i=0;i<410000;i++)ptr[i]=next[i]=-1;
	for(int i=0;i<b;i++){
		scanf("%d%d",P+i,Q+i);
		P[i]--;Q[i]--;
		uni(P[i],Q[i]);
	}
	for(int i=0;i<c;i++){
		scanf("%d%d",A+i,B+i);
		A[i]--;B[i]--;
		if(fi(A[i])!=fi(B[i])){
			printf("No\n");return 0;
		}
	}
	int las=-1;
	for(int i=0;i<a;i++){
		if(uf[i]<0){
			if(~las){
		g[i].push_back(las);
		g[las].push_back(i);
		zu[m]=las;
		next[m]=ptr[i];
		ptr[i]=m++;
		zu[m]=i;
		next[m]=ptr[las];
		ptr[las]=m++;
			}
			las=i;
		}
	}
	for(int i=0;i<b;i++){
	//	int p,q;
	//	scanf("%d%d",&p,&q);
	//	p--;q--;
		int p=P[i];
		int q=Q[i];
		if(S.count(make_pair(min(p,q),max(p,q)))){
			UNION(p,q);continue;
		}
		S.insert(make_pair(min(p,q),max(p,q)));
		g[p].push_back(q);
		g[q].push_back(p);
		zu[m]=q;
		next[m]=ptr[p];
		ptr[p]=m++;
		zu[m]=p;
		next[m]=ptr[q];
		ptr[q]=m++;
	}
	dfsInfos();
	for(int i=0;i<a;i++){
		for(int j=0;j<g[i].size();j++){
			if(!isBridge(i,g[i][j]))UNION(i,g[i][j]);
		}
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<g[i].size();j++){
			if(i<g[i][j]&&FIND(i)!=FIND(g[i][j])){
				g2[FIND(i)].push_back(FIND(g[i][j]));
				g2[FIND(g[i][j])].push_back(FIND(i));
		//		printf("%d %d\n",FIND(i),FIND(g[i][j]));
			}
		}
	}
	dfs(FIND(0),-1);
	for(int i=0;i<cur;i++){
		pos[tmp[i]]=i;
	}
	for(int i=0;i<1048576;i++)segtree[i]=99999999;
	for(int i=0;i<cur;i++){
		update(i,conv[tmp[i]]);
	}
	cur=0;
	dfs2(FIND(0),-1);
	for(int i=0;i<c;i++){
	//	int p,q;
	//	scanf("%d%d",&p,&q);p--;q--;
		int p=A[i];
		int q=B[i];
		p=FIND(p);q=FIND(q);if(p==q)continue;
		int q1=pos[p];
		int q2=pos[q];
		int at=query(0,524287,min(q1,q2),max(q1,q2),1);
	//	if(at<0||at>999999)while(1);
		int lca=rev[at];
		if(p<0||q<0||lca<0)while(1);
		add(L[p],1,0);
		add(L[lca],-1,0);
		add(L[q],1,1);
		add(L[lca],-1,1);
	}
	bool ok=true;
	for(int i=0;i<a;i++){
		if(UF[i]>=0)continue;
		int up=sum(L[i],R[i],0);
		int down=sum(L[i],R[i],1);
		if(up&&down)ok=false;
	}
	if(ok)printf("Yes\n");
	else printf("No\n");
}

gyazo.com
Rating: 2406 -> 2510 (+104)