oj.uz

Submission #126710

# Submission time Handle Problem Language Result Execution time Memory
126710 2019-07-08T09:47:54 Z fjzzq2002 Space Pirate (JOI14_space_pirate) C++14
10 / 100
 2000 ms 63260 KB 
#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[64][100055];
int goo(int u,ll k)
{
	for(int i=61;i>=0;--i) if(k&(1LL<<i))
		u=go[i][u];
	return u;
}
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 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);
	}
	for(int i=1;i<=n;++i)
		go[0][i]=a[i];
	for(int i=1;i<64;++i)
		for(int j=1;j<=n;++j)
			go[i][j]=go[i-1][go[i-1][j]];
	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

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:98:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<pa.size();++j)
              ~^~~~~~~~~~
space_pirate.cpp:107:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int u=0;u<pa.size();++u)
              ~^~~~~~~~~~
space_pirate.cpp:120:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int u=0;u<pa.size();++u)
              ~^~~~~~~~~~
space_pirate.cpp:57: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:60: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32064 KB Output is correct
2 Correct 30 ms 31992 KB Output is correct
3 Correct 30 ms 32076 KB Output is correct
4 Correct 31 ms 32120 KB Output is correct
5 Correct 31 ms 32120 KB Output is correct
6 Correct 31 ms 32092 KB Output is correct
7 Correct 34 ms 32116 KB Output is correct
8 Correct 30 ms 31992 KB Output is correct
9 Correct 38 ms 32092 KB Output is correct
10 Correct 30 ms 32120 KB Output is correct
11 Correct 32 ms 32120 KB Output is correct
12 Correct 32 ms 32120 KB Output is correct
13 Correct 32 ms 32092 KB Output is correct
14 Correct 31 ms 31992 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32064 KB Output is correct
2 Correct 30 ms 31992 KB Output is correct
3 Correct 30 ms 32076 KB Output is correct
4 Correct 31 ms 32120 KB Output is correct
5 Correct 31 ms 32120 KB Output is correct
6 Correct 31 ms 32092 KB Output is correct
7 Correct 34 ms 32116 KB Output is correct
8 Correct 30 ms 31992 KB Output is correct
9 Correct 38 ms 32092 KB Output is correct
10 Correct 30 ms 32120 KB Output is correct
11 Correct 32 ms 32120 KB Output is correct
12 Correct 32 ms 32120 KB Output is correct
13 Correct 32 ms 32092 KB Output is correct
14 Correct 31 ms 31992 KB Output is correct
15 Correct 58 ms 33016 KB Output is correct
16 Correct 36 ms 33008 KB Output is correct
17 Correct 77 ms 32988 KB Output is correct
18 Correct 1485 ms 33080 KB Output is correct
19 Correct 1233 ms 33056 KB Output is correct
20 Correct 681 ms 33144 KB Output is correct
21 Execution timed out 2025 ms 33116 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 63260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32064 KB Output is correct
2 Correct 30 ms 31992 KB Output is correct
3 Correct 30 ms 32076 KB Output is correct
4 Correct 31 ms 32120 KB Output is correct
5 Correct 31 ms 32120 KB Output is correct
6 Correct 31 ms 32092 KB Output is correct
7 Correct 34 ms 32116 KB Output is correct
8 Correct 30 ms 31992 KB Output is correct
9 Correct 38 ms 32092 KB Output is correct
10 Correct 30 ms 32120 KB Output is correct
11 Correct 32 ms 32120 KB Output is correct
12 Correct 32 ms 32120 KB Output is correct
13 Correct 32 ms 32092 KB Output is correct
14 Correct 31 ms 31992 KB Output is correct
15 Correct 58 ms 33016 KB Output is correct
16 Correct 36 ms 33008 KB Output is correct
17 Correct 77 ms 32988 KB Output is correct
18 Correct 1485 ms 33080 KB Output is correct
19 Correct 1233 ms 33056 KB Output is correct
20 Correct 681 ms 33144 KB Output is correct
21 Execution timed out 2025 ms 33116 KB Time limit exceeded
22 Halted 0 ms 0 KB -