Submission #2706160


Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#define MOD 1000000007LL

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

long long int powmod(long long int a, long long int k, long long int m){ //0<=a<=1e9, 0<k<=1e18, 0<m<=1e9
	if(a==0){
		return 0;
	}
	long long int apow[30], c[30];
	for(int i=0; i<30; i++){
		if(i==0){
			apow[i]=a;
			c[i]=1;
		}else{
			apow[i]=apow[i-1]*apow[i-1]%m;
			c[i]=c[i-1]*2;
		}
	}
	long long int ans=1;
	for(int i=29; i>=0; i--){
		if(k>=c[i]){
			ans=ans*apow[i]%m;
		}
		k=k%c[i];
	}
	return ans;
}
 
ll inv(ll x, ll p){
  return powmod(x, p-2, p);
}

int main()
{
	int n;
  scanf("%d", &n);
  if(n>2010) return 0;
  vector<int> v[2001];
  for(int i=1; i<=n; i++){
    int p1;
    scanf("%d", &p1);
    v[i].push_back(p1);
    v[p1].push_back(i);
  }
  int d[2001];
  fill(d, d+n+1, -1);
  d[0]=0;
  queue<int> que;
  que.push(0);
  while(!que.empty()){
    int x=que.front();
    que.pop();
    for(int i=0; i<v[x].size(); i++){
      if(d[v[x][i]]<0){
        d[v[x][i]]=d[x]+1;
        que.push(v[x][i]);
      }
    }
  }
  vector<P> dist;
  for(int i=0; i<=n; i++){
    dist.push_back(P(d[i], i));
  }
  sort(dist.begin(), dist.end(), greater<P>());
  int dmax=dist[0].first;
  ll p2=1;
  for(int i=0; i<=n; i++){
    p2*=2;
    p2%=MOD;
  }
  ll ans=0;
  for(int t=0; t<=dmax; t++){
    if(t==0){
      ans+=500000004;
      continue;
    }
    ll c[2001]={};
    for(int i=0; i<=n; i++){
      P p=dist[i];
      int x=p.second;
      if(d[x]>t) continue;
      if(d[x]==t){
        c[x]=500000004;
        continue;
      }
      ll sum=0, prod=1;
      for(int i=0; i<v[x].size(); i++){
        int y=v[x][i];
        if(d[y]<d[x]) continue;
        sum+=(c[y]*inv((MOD+1-c[y])%MOD, MOD)%MOD);
        sum%=MOD;
        prod*=(MOD+1-c[y]);
        prod%=MOD;
      }
      c[x]=sum*prod%MOD;
    }
    ans+=c[0];
    ans%=MOD;
  }
  ans*=p2;
  ans%=MOD;
    printf("%lld\n", ans);
	return 0;
}

Submission Info

Submission Time
Task E - Smuggling Marbles
User chocorusk
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2268 Byte
Status WA
Exec Time 1953 ms
Memory 512 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:51:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:56:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p1);
                     ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 0 / 600
Status
AC × 3
AC × 20
AC × 20
WA × 32
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt, s2_01.txt, s2_02.txt, s2_03.txt, s2_04.txt, s2_05.txt, s2_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt, s2_29.txt, s2_30.txt, s2_31.txt, s2_32.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 1 ms 256 KB
s1_01.txt AC 8 ms 384 KB
s1_02.txt AC 6 ms 384 KB
s1_03.txt AC 6 ms 384 KB
s1_04.txt AC 2 ms 384 KB
s1_05.txt AC 5 ms 384 KB
s1_06.txt AC 3 ms 384 KB
s1_07.txt AC 2 ms 384 KB
s1_08.txt AC 1953 ms 384 KB
s1_09.txt AC 145 ms 512 KB
s1_10.txt AC 6 ms 384 KB
s1_11.txt AC 3 ms 384 KB
s1_12.txt AC 5 ms 384 KB
s1_13.txt AC 1 ms 256 KB
s1_14.txt AC 22 ms 384 KB
s1_15.txt AC 32 ms 384 KB
s1_16.txt AC 13 ms 384 KB
s1_17.txt AC 18 ms 384 KB
s2_01.txt WA 1 ms 256 KB
s2_02.txt WA 1 ms 256 KB
s2_03.txt WA 1 ms 256 KB
s2_04.txt WA 1 ms 256 KB
s2_05.txt WA 1 ms 256 KB
s2_06.txt WA 1 ms 256 KB
s2_07.txt WA 1 ms 256 KB
s2_08.txt WA 1 ms 256 KB
s2_09.txt WA 1 ms 256 KB
s2_10.txt WA 1 ms 256 KB
s2_11.txt WA 1 ms 256 KB
s2_12.txt WA 1 ms 256 KB
s2_13.txt WA 1 ms 256 KB
s2_14.txt WA 1 ms 256 KB
s2_15.txt WA 1 ms 256 KB
s2_16.txt WA 1 ms 256 KB
s2_17.txt WA 1 ms 256 KB
s2_18.txt WA 1 ms 256 KB
s2_19.txt WA 1 ms 256 KB
s2_20.txt WA 1 ms 256 KB
s2_21.txt WA 1 ms 256 KB
s2_22.txt WA 1 ms 256 KB
s2_23.txt WA 1 ms 256 KB
s2_24.txt WA 1 ms 256 KB
s2_25.txt WA 1 ms 256 KB
s2_26.txt WA 1 ms 256 KB
s2_27.txt WA 1 ms 256 KB
s2_28.txt WA 1 ms 256 KB
s2_29.txt WA 1 ms 256 KB
s2_30.txt WA 1 ms 256 KB
s2_31.txt WA 1 ms 256 KB
s2_32.txt WA 1 ms 256 KB