JOI春合宿 2011-day3 report

問題文 : 報告

解法 :

まず, 問題文の例を解析する.

報告先でサイクルになっている頂点達について, サイクル内の頂点v に仕事の報告が来れば, 必ず他の頂点でも仕事の報告が来ることがわかるので, 閉路を潰す.

次に, 閉路を潰して出来たグラフの逆辺からなるグラフを考えると, これが木構造になることがわかる. (大きなデータの場合は森になりそうなことも考察できる)

ここまでわかれば, 根からeuler-tourに似たような番号付けをすることで(ただし, 辺ではなく頂点について番号付けをする) BIT でうまく加算や総和計算をすることが出来る.

コード :

#include <cstdio>
#include <vector>
#include <cstring>

#define MAX_N (100100)

using namespace std;

int Vid[2 * MAX_N];
int bit[2 * MAX_N];
int gr[MAX_N];
bool vis[MAX_N];
vector<int> G[MAX_N], rev[MAX_N], cmp[MAX_N], ord;

void add(int n){
	while (n < 2 * MAX_N){
		bit[n] += 1;
		n += n & -n;
	}
}

int sum(int pos)
{
	int ret = 0;
	
	while (pos){
		ret += bit[pos];
		pos &= (pos - 1);
	}
	
	return (ret);
}

void dfs(int v)
{
	vis[v] = true;
	for (int i = 0; i < G[v].size(); i++)
		if (!vis[G[v][i]]) dfs(G[v][i]);
	ord.push_back(v);
}

void revdfs(int v, int k)
{
	vis[v] = true; gr[v] = k;
	for (int i = 0; i < rev[v].size(); i++)
		if (!vis[rev[v][i]]) revdfs(rev[v][i], k);
}

void number(int v, int &k)
{
	vis[v] = true; Vid[v * 2] = k++;
	
	for (int i = 0; i < cmp[v].size(); i++)
		if (!vis[cmp[v][i]]) number(cmp[v][i], k);
	
	Vid[v * 2 + 1] = k++;
}	


int main()
{
	int N;
	int to[MAX_N];
	
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++){
		scanf("%d", to + i);
	}
	
	for (int i = 0; i < N; i++){
		G[i].push_back(--to[i]);
		rev[to[i]].push_back(i);
	}
	
	memset(vis, false, sizeof(vis));
	for (int i = 0; i < N; i++) if (!vis[i]) dfs(i);
	
	memset(vis, false, sizeof(vis));
	int k = 0;
	for (int i = N - 1; i >= 0; i--)
		if (!vis[ord[i]]) revdfs(ord[i], k++);
	
	for (int i = 0; i < N; i++) rev[i].clear();
	
	for (int i = 0; i < N; i++){
		if (gr[i] != gr[to[i]]){
			cmp[gr[to[i]]].push_back(gr[i]);
			rev[gr[i]].push_back(gr[to[i]]);
		}
	}
	
	k = 1;
	memset(vis, false, sizeof(vis));
	for (int i = 0; i < N; i++){
		if (!vis[gr[i]] && rev[gr[i]].size() == 0) number(gr[i], k);
	}
	
	for (int i = 0; i < N; i++){
		printf("%d\n", sum(Vid[gr[i] * 2 + 1]) - sum(Vid[gr[i] * 2] - 1));
		add(Vid[gr[i] * 2]);
	}
	
	return (0);
}