Submission #3144919
Source Code Expand
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(kbrni,n)cout<<" "<<a[kbrni];cout<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define svecp(v) cout<<#v<<":";each(kbrni,v)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl
using namespace std;
typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;
const int MAX_N = 100005;
class FunctionalGraph {
public:
int V;
vector<int> nx,visit;
vector<vector<int> > loop;
vector<vector<int> > G;
vector<int> st;
FunctionalGraph(int node_size) : V(node_size), nx(V, 0), visit(V, 0){}
void add_edge(int u,int v){
nx[u] = v;
}
void make_loop(const int st,int nw,int ch,vector<int>& vec){
while(nx[nw] != st){
vec.push_back(nx[nw]);
visit[nx[nw]] = ch;
nw = nx[nw];
}
}
void dfs(int u,int kind,vector<int>& vec){
visit[u] = kind;
int v = nx[u];
if(visit[v] == kind){
vec.push_back(u),vec.push_back(v);
int ch = (int)(loop.size()) + 1;
visit[u] = visit[v] = -ch;
make_loop(u,v,-ch,vec);
}else if(visit[v] == 0){
dfs(v,kind,vec);
}
}
void solve(){
int id = 1;
for(int i = 0; i < V; i++){
if(visit[i] == 0){
vector<int> vec;
dfs(i,id++,vec);
if((int)vec.size()){
loop.push_back(vec);
}
}
}
make_graph();
}
void make_graph(){
G.resize(V);
vector<bool> flag(V,false);
for(int i = 0; i < V; i++){
if(visit[i] >= 0){
G[nx[i]].push_back(i);
flag[nx[i]] = (visit[nx[i]] < 0);
}
}
for(int i = 0; i < V; i++){
if(flag[i]){
st.push_back(i);
}
}
}
};
vector<int> ord;
int lb[MAX_N],rb[MAX_N],cmp[MAX_N];
void dfs(vvi& G,int u,const int c)
{
lb[u] = (int)ord.size();
cmp[u] = c;
ord.pb(u);
rep(i,G[u].size()){
dfs(G,G[u][i],c);
}
rb[u] = (int)ord.size();
}
template<typename V> class BIT {
private:
int n; vector<V> bit;
public:
void add(int i,V x){ i++; while(i < n) bit[i] += x, i += i & -i;}
V sum(int i){ i++; V s = 0; while(i>0) s += bit[i], i -= i & -i; return s;} //0_indexedでi以下の要素の和
BIT(){} BIT(int sz){ n = sz + 1, bit.resize(n,0);} //初期値がすべて0の場合
BIT(vector<V> v){ n = (int)v.size()+1; bit.resize(n); rep(i,n-1) add(i,v[i]);}
void print(){ rep(i,n-1)cout<<sum(i)-sum(i-1)<< " ";cout<<endl;}
void print_sum(){ rep(i,n)cout<<sum(i-1)<<" ";cout<<endl;} //-1スタート
};
int ad[MAX_N];
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
FunctionalGraph fg(n);
rep(i,n){
int a;
cin >> a;
fg.add_edge(i,a-1);
}
fg.solve();
vvi& G = fg.G;
vi& visit = fg.visit;
each(i,fg.st){
dfs(G,i,visit[i]);
}
BIT<int> bt(len(ord));
rep(i,n){
if(visit[i] < 0){
cout << ad[-visit[i]] << "\n";
ad[-visit[i]]++;
}else{
cout << bt.sum(rb[i]-1) - bt.sum(lb[i]-1) << "\n";
ad[-cmp[i]]++;
bt.add(lb[i],1);
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
report - 報告 (Report) |
User |
kopricky |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
4490 Byte |
Status |
AC |
Exec Time |
44 ms |
Memory |
15352 KB |
Judge Result
Set Name |
Set01 |
Set02 |
Set03 |
Set04 |
Set05 |
Set06 |
Set07 |
Set08 |
Set09 |
Set10 |
Score / Max Score |
10 / 10 |
10 / 10 |
10 / 10 |
10 / 10 |
10 / 10 |
10 / 10 |
10 / 10 |
10 / 10 |
10 / 10 |
10 / 10 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
Set01 |
01-01, 01-02, 01-03 |
Set02 |
02-01, 02-02, 02-03 |
Set03 |
03-01, 03-02, 03-03 |
Set04 |
04-01, 04-02, 04-03 |
Set05 |
05-01, 05-02, 05-03 |
Set06 |
06-01, 06-02, 06-03 |
Set07 |
07-01, 07-02, 07-03, 07-04 |
Set08 |
08-01, 08-02, 08-03, 08-04 |
Set09 |
09-01, 09-02, 09-03, 09-04 |
Set10 |
10-01, 10-02, 10-03, 10-04 |
Case Name |
Status |
Exec Time |
Memory |
01-01 |
AC |
1 ms |
384 KB |
01-02 |
AC |
2 ms |
384 KB |
01-03 |
AC |
1 ms |
384 KB |
02-01 |
AC |
13 ms |
4736 KB |
02-02 |
AC |
12 ms |
3200 KB |
02-03 |
AC |
12 ms |
2560 KB |
03-01 |
AC |
19 ms |
7164 KB |
03-02 |
AC |
18 ms |
4732 KB |
03-03 |
AC |
17 ms |
3836 KB |
04-01 |
AC |
26 ms |
9348 KB |
04-02 |
AC |
23 ms |
6140 KB |
04-03 |
AC |
23 ms |
5000 KB |
05-01 |
AC |
32 ms |
11640 KB |
05-02 |
AC |
30 ms |
7684 KB |
05-03 |
AC |
29 ms |
6264 KB |
06-01 |
AC |
39 ms |
13956 KB |
06-02 |
AC |
37 ms |
9220 KB |
06-03 |
AC |
35 ms |
7288 KB |
07-01 |
AC |
43 ms |
12676 KB |
07-02 |
AC |
43 ms |
14212 KB |
07-03 |
AC |
40 ms |
8184 KB |
07-04 |
AC |
32 ms |
8760 KB |
08-01 |
AC |
43 ms |
13560 KB |
08-02 |
AC |
41 ms |
10116 KB |
08-03 |
AC |
43 ms |
8184 KB |
08-04 |
AC |
24 ms |
7664 KB |
09-01 |
AC |
44 ms |
14468 KB |
09-02 |
AC |
41 ms |
9988 KB |
09-03 |
AC |
40 ms |
8184 KB |
09-04 |
AC |
36 ms |
8888 KB |
10-01 |
AC |
39 ms |
11140 KB |
10-02 |
AC |
44 ms |
15352 KB |
10-03 |
AC |
37 ms |
8184 KB |
10-04 |
AC |
26 ms |
6580 KB |