Submission #126718

#	Time	Username	Problem	Language	Result	Execution time	Memory
126718		fjzzq2002	Space Pirate (JOI14_space_pirate)	C++14	80 / 100	1508 ms	102776 KiB

space_pirate

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int go[3005][6005];
int n,a[SZ],ff[SZ],sz[SZ]; ll k;
int gf(int x) {return ff[x]?ff[x]=gf(ff[x]):x;}
bool cyc[SZ],vis[SZ];
ll cnt[SZ];
vector<int> cc[SZ],ct[SZ];
int goo(int u,ll k)
{
	if(k>n) k-=(k-n)/cc[gf(u)].size()*cc[gf(u)].size();
	return go[u][k];
}
int cn,cs[SZ]; Edg
int d1[SZ],d2[SZ],D=0,R,ro[SZ],dep[SZ],od[SZ];
void dfs(int t,int fa=0)
{
	d1[t]=++D; ro[t]=R; dep[t]=dep[fa]+1;
	for esb(t,e,b)if(b!=fa&&!cyc[b])
		dfs(b,t);
	d2[t]=D;
}
int main()
{
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",a+i);
		int x=gf(i),y=gf(a[i]);
		if(x<y) swap(x,y);
		if(x!=y) ff[x]=y;
		ad_de(a[i],i);
	}
	if(n>3000)
	{
	#define cs ct
	for(int i=1;i<=n;++i) if(!vis[i])
	{
		vector<int> cy;
		int j=i;
		while(!vis[j])
			cy.pb(j),vis[j]=1,j=a[j];
		cs[++cn]=cy;
	}
	vector<int> s=cs[1];
	int tg=s[k%s.size()];
	cnt[tg]+=(ll)n*(n-int(s.size()));
	for(int p=2;p<=cn;++p)
		for(auto x:cs[p])
			cnt[x]+=(ll)s.size();
	int p=s.size();
	//intact cycle
	for(int i=1;i<=p;++i)
		for(int j=0;j<p;++j)
		{
			ll u=(k-j-1)/(p-i+1),
			d=u*(p-i+1),
			R=min(k-1-d,ll(p-1));
			cnt[s[((k-1-d+i)%p+p)%p]]+=R-j+1;
			j=R;
		}
	for(int i=1;i<=n;++i)
		printf("%lld\n",cnt[i]);
	return 0;
	#undef cs
	}
	for(int i=1;i<=n;++i)
	{
		go[i][0]=i;
		for(int j=1;j<=n+n;++j)
			go[i][j]=a[go[i][j-1]];
	}
	for(int i=1;i<=n;++i)
		++sz[gf(i)],ct[gf(i)].pb(i);
	assert(gf(1)==1);
	for(int i=1;i<=n;++i) if(!ff[i])
	{
		int j=i;
		for(int k=1;k<=sz[i];++k) j=a[j];
		vector<int> cy;
		while(!cyc[j])
			cy.pb(j),cyc[j]=1,j=a[j];
		cs[++cn]=i; cc[i]=cy;
		for(auto t:cy)
			R=t,dfs(t);
	}
	vector<int> pa,s;
	int fd=0;
	{
	int x=1;
	while(!vis[x])
	{
		vis[x]=1,fd+=!cyc[x],
		pa.pb(x); od[x]=pa.size();
		if(cyc[x]) s.pb(x);
		x=a[x];
	}
	}
	ll tt=n*(ll)n;
	for(int j=0;j<pa.size();++j)
	{
		int x=pa[j];
		for(int u=1;u<=n;++u)
			if(gf(u)!=1||(!cyc[x]&&(d1[u]<d1[x]||d1[u]>d2[x])))
//				cout<<x<<"->"<<u<<"\n",
				cnt[goo(u,k-j-1)]++;
	}
//	for(int i=1;i<=n;++i) cout<<cnt[i]<<"|";cout<<"\n";
	for(int u=0;u<pa.size();++u)
	{
		int w=pa[u]; if(cyc[w]) continue;
		ll lkk=k-u; //remained k
		for(auto c:ct[1]) if(d1[w]<=d1[c]&&d1[c]<=d2[w])
		{
			int cl=dep[c]-dep[w]+1;
			ll lk=lkk%cl;
			if(!lk) lk+=cl;
			--lk;
			++cnt[goo(c,lk)];
		}
	}
	for(int u=0;u<pa.size();++u)
	{
		int w=pa[u]; if(!cyc[w]) continue;
		ll lkk=k-u; //remained k
		for(auto c:ct[1])
		{
			int cl=dep[c]+(-od[ro[c]]+od[w]+(int)s.size())%s.size();
			ll lk=lkk%cl;
			if(!lk) lk+=cl;
			--lk;
//			cout<<w<<"->"<<c<<":"<<cl<<" "<<goo(c,lk)<<" "<<lkk<<"\n";
			++cnt[goo(c,lk)];
		}
	}
	for(int i=1;i<=n;++i) tt-=cnt[i];
	cnt[goo(1,k)]+=tt;
	for(int i=1;i<=n;++i)
		printf("%lld\n",cnt[i]);
}

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:131:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<pa.size();++j)
              ~^~~~~~~~~~
space_pirate.cpp:140:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int u=0;u<pa.size();++u)
              ~^~~~~~~~~~
space_pirate.cpp:153:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int u=0;u<pa.size();++u)
              ~^~~~~~~~~~
space_pirate.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~~
space_pirate.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a+i);
   ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 33 / 33
• Subtask 4: 0 / 20