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 |
|
|
|
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 |