結果
問題 | No.1013 〇マス進む |
ユーザー |
![]() |
提出日時 | 2020-03-20 23:05:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 191 ms / 2,000 ms |
コード長 | 3,515 bytes |
コンパイル時間 | 1,500 ms |
コンパイル使用メモリ | 111,752 KB |
実行使用メモリ | 21,632 KB |
最終ジャッジ日時 | 2024-12-15 08:16:00 |
合計ジャッジ時間 | 8,991 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 62 |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <map> #include <queue> #include <iomanip> #include <set> #include <tuple> #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) using namespace std; typedef long long ll; const ll MOD=1e9+7; template<class T> void chmin(T &a,const T &b){if(a>b) a=b;} template<class T> void chmax(T &a,const T &b){if(a<b) a=b;} class DisjointSet{ public: vector<int> rank,p; vector<int> sz; DisjointSet(){} DisjointSet(int size){ rank.resize(size,0); p.resize(size,0); sz.resize(size,0); for(int i=0;i<size;i++) makeSet(i); } void makeSet(int x){ p[x]=x; rank[x]=0; sz[x]=1; } bool same(int x,int y){ return findSet(x)==findSet(y); } void unite(int x,int y){ if(same(x,y)) return; link(findSet(x),findSet(y)); } void link(int x,int y){ if(rank[x]>rank[y]){ p[y]=x; sz[x]+=sz[y]; }else{ p[x]=y; sz[y]+=sz[x]; if(rank[x]==rank[y]){ rank[y]++; } } } int findSet(int x){ if(x!=p[x]){ p[x]=findSet(p[x]); } return p[x]; } int findSize(int x){ return sz[findSet(x)]; } }; int N,K; vector<int> P; vector<vector<int>> g; vector<vector<int>> rg; vector<ll> last,used,in,dist; vector<ll> ans; void dfs(int now,vector<ll> &v,vector<ll> &sum,int M,int i){ v.push_back(last[now]); for(auto nex:rg[now]){ if(used[nex]){ dist[nex]=dist[now]+1; last[nex]=last[now]+P[nex]; { if(dist[nex]>=K){ ans[nex]=last[nex]-v[dist[nex]-K]; }else{ ans[nex]+=last[nex]; ll rest=K-dist[nex]; ans[nex]+=sum[M]*(rest/M); ans[nex]+=sum[i+rest%M]-sum[i]; } } dfs(nex,v,sum,M,i); } } v.pop_back(); } void solve(vector<int> &nodes){ int n=nodes.size(); queue<int> Q; for(auto p:nodes) if(in[p]==0) Q.push(p); while(!Q.empty()){ int now=Q.front();Q.pop(); used[now]=1; for(auto nex:g[now]){ in[nex]--; if(in[nex]==0) Q.push(nex); } } vector<int> circuit; int st=0; for(auto p:nodes) if(used[p]==0) st=p; Q.push(st); while(!Q.empty()){ int now=Q.front(); Q.pop(); circuit.push_back(now); for(auto nex:g[now]){ if(nex!=st) Q.push(nex); } } int M=circuit.size(); vector<ll> sum(2*M+1,0); for(int i=0;i<2*M;i++) sum[i+1]=sum[i]+P[circuit[i%M]]; for(int i=0;i<M;i++){ int p=circuit[i]; dist[p]=0; last[p]=0; vector<ll> v; dfs(p,v,sum,M,i); } for(int i=0;i<M;i++){ int p=circuit[i]; ans[p]+=sum[M]*(K/M); ans[p]+=sum[i+K%M]-sum[i]; } } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin>>N>>K; P.resize(N); rep(i,N) cin>>P[i]; g.resize(N); rg.resize(N); last.resize(N,0); used.resize(N,0); in.resize(N,0); dist.resize(N,MOD); ans.resize(N,0); DisjointSet us(N); for(int i=0;i<N;i++){ int tar=(i+P[i])%N; us.unite(i,tar); g[i].push_back(tar); rg[tar].push_back(i); } rep(i,N) in[i]=rg[i].size(); vector<vector<int>> nodes(N); for(int i=0;i<N;i++) nodes[us.findSet(i)].push_back(i); for(int i=0;i<N;i++){ if(nodes[i].size()==0) continue; solve(nodes[i]); } for(int i=0;i<N;i++) cout<<ans[i]+i+1<<endl; return 0; }