Algoogle

Algorithm for Programming Contest

JOI 春合宿 2011 Report

Category: JOI Tag: binary-indexed-tree, strongly-connected-component

Report

問題概要


N個の人がいる, 各人はその番号より小さい番号の人の仕事が終わってから始める.
またそれぞれ仕事の報告をする相手が決まっている.
報告を受けたらさらにその報告を回す.
また2回以上報告を受ける場合は2回目以降は無視する.
それぞれの人が仕事の開始時までに受ける報告の仕事の数を求めよ.

解法


閉路が存在する場合, その閉路内で報告が回せるので1つ塊としてみて良い.
そこで閉路を強連結成分分解して潰す.
そうすると複数の木ができるので各木で根からオイラーツアーして頂点に入るときと出るときに番号をふる.
あとは各人が属する強連結成分について, そこに入ってから出るまでの部分木内で発生した報告の総数を求める.
これはオイラーツアーしで振った番号で区間になるのでBITで管理すれば良い.
仕事が完了したらその強連結成分に入るときの位置に1足せばその強連結成分内で発生した報告のカウントが出来る.

####


(report.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;

template<class T> class bit
{
public:
        vector<T> dat;
        int N;

        bit(){}
        bit(int N) : N(N){
                dat.assign(N,0);
        }
        // sum [0,i)
        T sum(int i){
                T ret = 0;
                for(--i; i>=0; i=(i&(i+1))-1) ret += dat[i];
                return ret;
        }
        // sum [i,j)
        T sum(int i, int j){ return sum(j) - sum(i);}
        // add x to i
        void add(int i, T x){ for(; i < N; i|=i+1) dat[i] += x;}
};


int n, m, done[1<<17], id[1<<17], in[1<<17], out[1<<17];
vector<int> G[1<<17], rG[1<<17], vs;
vector<vector<int>> scc;
bit<int> b;

void scc_dfs(int v)
{
        done[v] = 1;
        for(auto &w: G[v]) if(!done[w]) scc_dfs(w);
        vs.push_back(v);
}

void scc_rdfs(int v, int k)
{
        done[v] = 1;
        id[v] = k;
        scc.back().push_back(v);
        for(auto &w: rG[v]) if(!done[w]) scc_rdfs(w,k);
}

void stronglyCC()
{
        for (int i = 0; i < n; i++)
                if(!done[i]) scc_dfs(i);
        memset(done,0,sizeof(done));
        reverse(begin(vs),end(vs));
        int k = 0;
        for(auto &v: vs) if(!done[v]) {
                        scc.push_back(vector<int>());
                        scc_rdfs(v,k++);
                }
}

void dfs(int v, int &idx)
{
        done[v] = 1;
        in[v] = idx++;
        int cnt = 0;
        for(auto &w: scc[v]) {
                for(auto &x: G[w])
                        if(!done[id[x]]) dfs(id[x], idx);
        }
        if(!cnt) vs.push_back(v);
        out[v] = idx;
}

void solve()
{
        stronglyCC();
        m = scc.size();
        vs.clear();

        int idx = 0;
        memset(done,0,sizeof(done));
        for (int i = 0; i < m; i++) {
                if(done[i]) continue;
                int f = 1;
                for(auto &w: scc[i]) {
                        for(auto &x: rG[w])
                                if(id[x] != i) {
                                        f = 0;
                                        break;
                                }
                        if(!f) break;
                }
                if(f) dfs(i,idx);
        }

        memset(done,0,sizeof(done));
        b = bit<int>(2*m);
        for (int i = 0; i < n; i++) {
                cout << b.sum(in[id[i]],out[id[i]]) << endl;
                b.add(in[id[i]], 1);
        }
}

void input()
{
        cin >> n;
        int p;
        for (int i = 0; i < n; i++) {
                cin >> p; p--;
                G[p].push_back(i);
                rG[i].push_back(p);
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        solve();
        return 0;
}

Comments