Croc Champ 2013 - Round 1 : A. SMSC, B. Network Topology

続いてRound1。なんとかABDEを時間内に解けて突破できてよかった。
Cは実装時間切れ。というのもA,Bでしょうもないミスをしていたため…。
http://codeforces.com/contest/292/problem/A
http://codeforces.com/contest/292/problem/B

A. SMSC

1秒当たり1つのメッセージが処理される環境がある。
T秒後にC個のメッセージがキューに積まれる、というクエリが何個か与えられたとき、最後のメッセージが掃ける時間とキューの最大長を答える。

指示通りシミュレートすればよい。
最初、「キューの最大長」を「クエリの最大長」と勘違いしたため、どのクエリのメッセージが残ってるかいちいち処理してしまいWA…。

int N;
ll T[1000001],C[1000001];

void solve() {
	int r,i,j,k,l,x,y;
	
	N=GETi();
	
	ll la=0;
	ll f=0,ma=0;
	FOR(i,N) {
		T[i]=GETi();
		C[i]=GETi();
		
		if(i>0) f=max(0LL,f-(T[i]-T[i-1]));
		
		f+=C[i];
		ma=max(ma,f);
		la=T[i];
	}
	la+=f;
	
	cout << la << " " << ma << endl;
	
	return;
}

B. Network Topology

すべての点が連結したグラフが与えられる。
このグラフの形状が一直線・リング・スター・それ以外のいずれかを答える。

各点につながる辺の数を数えればよい。

• 一直線 ： ２点は１辺のみ、それ以外の点は２辺とつながる。
• リング ： 全点２辺とつながる。
• スター ： 1点は(点数-1)辺とつながり、残りの全点は1辺とつながる。

本番、「すべての点が連結している」の条件を読み落として、本当に連結しているかチェックするコードを書いてしまい時間をロスした。
問題文中だと「You've got a connected non-directed graph」のconnectedでしかその条件がわからず、単語１個なので見落とした…。

int N,M;
vector<int> E[100001];

int star() {
	int i,ng=0;
	int e=0,m=0;
	
	FOR(i,N) {
		if(E[i].size()==1) e++;
		if(E[i].size()==M) m++;
	}
	return (e==N-1 && m==1);
}
int vis[1000001];
int ring() {
	int i,s=0,pre;
	
	ZERO(vis);
	FOR(i,N) {
		int c=s;
		vis[s]=1;
		if(i==0) s=E[s][0];
		else s=E[s][0]+E[s][1]-pre;
		if(i!=N-1 && vis[s]) return 0;
		pre=c;
	}
	
	return s==0;
}

int bus() {
	int s=-1,e=-1;
	int i,n;
	
	FOR(i,N) {
		if(E[i].size()==1) {
			if(s>=0 && e>=0) return 0;
			if(s==-1) s=i;
			else e=i;
		}
		else if(E[i].size()!=2) return 0;
	}
	if(e==-1) return 0;
	
	int pre;
	FOR(i,N-1) {
		int c=s;
		if(i==0) s=E[s][0];
		else s=E[s][0]+E[s][1]-pre;
		pre=c;
	}
	
	return s==e;
}

void solve() {
	int f,r,i,j,k,l,x,y;
	
	N=GETi();
	M=GETi();
	
	if(N!=M && N!=M+1) {
		_P("unknown topology\n");
		return;
	}
	
	FOR(i,M) {
		x=GETi()-1;
		y=GETi()-1;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	if(N==M) {
		if(ring()) {
			_P("ring topology\n");
			return;
		}
	}
	else {
		if(bus()) {
			_P("bus topology\n");
			return;
		}
		if(star()) {
			_P("star topology\n");
			return;
		}
	}
	
	_P("unknown topology\n");
	
	return;
}

まとめ

どちらも簡単だが、問題文の読み間違いで大きく時間をロスした。
ここでロスしなければCも解く時間が残ったのに…。