2014-06-17

■ IOI 2012 Rings 20:23

日本語の問題はJOIのホームページにあります

概要: N頂点のグラフがある。はじめは辺が張られていない。

Link(a,b) -> aとbに辺を結ぶ

count()-> 「その頂点を取り除くと残りのグラフに直線状の鎖しかのこらない」ような頂点の個数を返す

というクエリに対処してください。

解法:

最初20点解法しかわからなくて非常に萎えぽよした。

いろいろ考察すると、

・一度条件を満たさなくなったものは二度と満たすことはない。

・頂点を取り除いたときに次数3以上の頂点が残ってしまうときはだめ。

・上の条件を満たしているならば、ループを含まないかぎりok.

・すなわち「頂点を取り除いたときに次数3以上の頂点が残らない and グラフ内のすべてのループに含まれている」が満たされればよい

・次数に関する条件は適当にほげる(結構面倒)

・ループが1つできたときは、そのループに含まれてない頂点を候補から除外する

・2つ目ができたときを考える。ループができる原因になった辺について

　・両端が1つ目のループに含まれない-> 答えは0

　・両端が1つ目のループに含まれる-> 候補は今見てる辺の両端の2つのみになる

　・どちらでもない-> 辺の両端をa,bとすると、辺を付け加える前のグラフ上での最短パスab上に

　　　　　　　　　　 1つ目のループの頂点が3つ以上ある-> 答えは0. (どれをとってもループがのこるか次数の条件を満たさない)

　　　　　　　　　　 2つ以下-> そいつらが候補になる

・以上より、2つ目のループができた瞬間から候補は高々2つになる！

・それは「頂点vを通らない辺で構成したグラフ」に対するunion-find木をもてるということなので

　ループ検出は頭がなくてもできるようになる。

以上のことを書くと100点がきます。37点とか55点の解法はわかりませんでした...

難易度表☆11のグラフ問題が自力で解けたので春合宿時のvoltage 20点から成長を感じられてよかった。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n,q,all=0;
int ne[1000005];
int ch[1000005];
int four;
bool never[1000005];
bool cand[1000005];
bool nosol;
vector<int>edge[1000005];
vector<int>xx,yy;
int cnt;
int roopcnt;
int v;
int vert[2];
bool another;

struct uf
{
int par[1000005],ran[1000005];
	void init()
	{
		for(int i=0;i<1000005;i++) par[i] = i,ran[i] = 0;
	}
	int find(int x)
	{
		if(x == par[x]) return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x,int y)
	{
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(ran[x] < ran[y])
		{
			par[x] = y;
		}
		else
		{
			par[y] = x;
			if(ran[x] == ran[y]) ran[x]++;
		}
	}
	bool same(int x,int y)
	{
		return find(x) == find(y);
	}
}allt,candt[2];

void add_edge(int aa,int b)
{
	if(edge[aa].size() == 2)
	{
		all++;
		for(int i=0;i<2;i++)
		{
			int v = edge[aa][i];
			if(!never[v])
			{
				ch[ne[v]+(edge[v].size() >= 3)]--;
				ch[1+ne[v]+(edge[v].size() >= 3)]++;
			}
			++ne[v];
		}
	}
	else if(edge[aa].size() == 3)
	{
		four++;
		for(int i=0;i<3;i++)
		{
			int v = edge[aa][i];
			if(!never[v])
			{
				ch[ne[v]+(edge[v].size() >= 3)]--;
				ch[ne[v]-1+(edge[v].size() >= 3)]++;
			}
			--ne[v];
		}
	}

	if(edge[b].size() == 2)
	{
		all++;
		for(int i=0;i<2;i++)
		{
			int v = edge[b][i];
			if(!never[v])
			{
				ch[ne[v]+(edge[v].size() >= 3)]--;
				ch[1+ne[v]+(edge[v].size() >= 3)]++;
			}
			++ne[v];
		}
	}
	else if(edge[b].size() == 3)
	{
		four++;
		for(int i=0;i<3;i++)
		{
			int v = edge[b][i];
			if(!never[v])
			{
				ch[ne[v]+(edge[v].size() >= 3)]--;
				ch[ne[v]-1+(edge[v].size() >= 3)]++;
			}
			--ne[v];
		}
	}
	
	if(!never[aa])
	{
		ch[ne[aa]+(edge[aa].size()>=3)]--;
		
		if(edge[b].size() == 2) ne[aa]++;
		
		ch[ne[aa]+(edge[aa].size()+1>=3)]++;
	}
	if(!never[b])
	{
		ch[ne[b]+(edge[b].size()>=3)]--;
		
		if(edge[aa].size() == 2) ne[b]++;
		
		ch[ne[b]+(edge[b].size()+1>=3)]++;
	}
	edge[aa].push_back(b);
	edge[b].push_back(aa);
	xx.push_back(aa);
	yy.push_back(b);
}

int main()
{
	scanf("%d %d",&n,&q); ch[0] = n;
	allt.init();
	for(int i=0;iint a,b;
		scanf("%d",&a);

		if(a == -1)
		{
			if(nosol || four >= 2) puts("0");
			else printf("%d\n",max(0,ch[all]));
			
		}
		else
		{
			scanf("%d",&b);
			if(nosol || four>=2) continue;
			if(another)
			{
				for(int j=0;jif(never[vert[j]]) continue;
					
					if(vert[j] != a && vert[j] != b)
					{
						if(!candt[j].same(a,b)) candt[j].unite(a,b);
						else if(!never[vert[j]])
						{
							ch[ne[vert[j]]+(edge[vert[j]].size() >= 3)]--;
							never[vert[j]] = true;
						}
					}
				}
			}
			else if(!allt.same(a,b))
			{
				allt.unite(a,b);
			}
			else if(roopcnt == 0)
			{
				roopcnt++;
				
				int dist[1000005];
				bool used[1000005]={};
				queue<int>que;
				fill(dist,dist+1000005,1e9);
				dist[a] = 0;
				que.push(a);
				while(!que.empty())
				{
					int q = que.front(); que.pop();
					if(used[q]) continue;
					used[q] = true;
					for(int j=0;j1);
						if(used[edge[q][j]]) continue;
						que.push(edge[q][j]);
					}
				}
				int dist2[1000005];
				bool used2[1000005]={};
				fill(dist2,dist2+1000005,1e9);
				dist2[b] = 0;
				que.push(b);
				while(!que.empty())
				{
					int q = que.front(); que.pop();
					if(used2[q]) continue;
					used2[q] = true;
					for(int j=0;j1);
						if(used2[edge[q][j]]) continue;
						que.push(edge[q][j]);
					}
				}
				bool composed[1000005]={};
				composed[b] = true;
				int cur = a;
				while(cur != b)
				{
					composed[cur] = true;
					int lb = dist[cur];
					int ub = dist2[cur];
					for(int j=0;jif(dist[edge[cur][j]] + dist2[edge[cur][j]] == lb+ub && lb+1 == dist[edge[cur][j]])
						{
							cur = edge[cur][j];
							break;
						}
					}
				}
				for(int j=0;jif(!composed[j] && !never[j])
					{
						never[j] = true;
						ch[ne[j]+(edge[j].size()>=3)]--;
					}
				}
			}
			else
			{
				roopcnt++;
				
				int dist[1000005];
				bool used[1000005]={};
				queue<int>que;
				fill(dist,dist+1000005,1e9);
				dist[a] = 0;
				que.push(a);
				while(!que.empty())
				{
					int q = que.front(); que.pop();
					if(used[q]) continue;
					used[q] = true;
					for(int j=0;j1);
						if(used[edge[q][j]]) continue;
						que.push(edge[q][j]);
					}
				}
				int dist2[1000005];
				bool used2[1000005]={};
				fill(dist2,dist2+1000005,1e9);
				dist2[b] = 0;
				que.push(b);
				while(!que.empty())
				{
					int q = que.front(); que.pop();
					if(used2[q]) continue;
					used2[q] = true;
					for(int j=0;j1);
						if(used2[edge[q][j]]) continue;
						que.push(edge[q][j]);
					}
				}
				bool composed[1000005]={};
				composed[b] = true;
				int cur = a;
				while(cur != b)
				{
					composed[cur] = true;
					int lb = dist[cur];
					int ub = dist2[cur];
					for(int j=0;jif(dist[edge[cur][j]] + dist2[edge[cur][j]] == lb+ub && lb+1 == dist[edge[cur][j]])
						{
							cur = edge[cur][j];
							break;
						}
					}
				}
				vector<int>cl;
				bool cutroop = true;
				for(int j=0;jif(!composed[j] && !never[j])
					{
						never[j] = true;
						ch[ne[j]+(edge[j].size()>=3)]--;
					}
					else if(composed[j] && !never[j])
					{
						cl.push_back(j);
					}
					else if(composed[j] && never[j])
					{
						cutroop = false;
					}
				}
				if(cutroop)
				{
					for(int i=0;iif(!never[i] && i!=a && i!=b)
						{
							never[i] =true;
							ch[ne[i]+(edge[i].size()>=3)]--;
						}
					}
					cl.clear();
					cl.push_back(a); cl.push_back(b);
				}
				if(cl.size() >= 3 || cl.empty()) nosol = true;
				else
				{
					another = true;
					v = cl.size();
					for(int i=0;ifor(int i=0;iif(a != vert[i] && b != vert[i]) candt[i].unite(a,b);
						for(int s = 0;s < xx.size();s++)
						{
							if(xx[s] == vert[i] || yy[s] == vert[i]) continue;
							if(!candt[i].same(xx[s],yy[s])) candt[i].unite(xx[s],yy[s]);
							else if(!never[vert[i]])
							{
								never[vert[i]] = true;
								ch[ne[vert[i]] + (edge[vert[i]].size()>=3)]--;
							}
						}
					}
				}
			}
			add_edge(a,b);
		}
	}
}

ツイートする