Task: | Planeetat |
Sender: | kluopaja |
Submission time: | 2020-09-27 18:54:19 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 49 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 24 |
#2 | ACCEPTED | 25 |
#3 | RUNTIME ERROR | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 2, 3 | details |
#12 | ACCEPTED | 0.02 s | 2, 3 | details |
#13 | ACCEPTED | 0.11 s | 2, 3 | details |
#14 | RUNTIME ERROR | 0.01 s | 3 | details |
#15 | RUNTIME ERROR | 0.01 s | 3 | details |
#16 | RUNTIME ERROR | 0.01 s | 3 | details |
#17 | RUNTIME ERROR | 0.01 s | 3 | details |
#18 | RUNTIME ERROR | 0.01 s | 3 | details |
#19 | RUNTIME ERROR | 0.01 s | 3 | details |
#20 | RUNTIME ERROR | 0.01 s | 3 | details |
#21 | RUNTIME ERROR | 0.01 s | 3 | details |
#22 | RUNTIME ERROR | 0.01 s | 3 | details |
#23 | RUNTIME ERROR | 0.01 s | 3 | details |
#24 | RUNTIME ERROR | 0.01 s | 3 | details |
#25 | RUNTIME ERROR | 0.01 s | 3 | details |
Compiler report
input/code.cpp: In function 'void generateGraphs(int, int, int, std::vector<int>&, std::vector<std::vector<int> >&)': input/code.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if(v.size() == tot_nodes) { ~~~~~~~~~^~~~~~~~~~~~ input/code.cpp: In function 'int solve(int, int)': input/code.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i = 0; i < v.size(); ++i) { ~~^~~~~~~~~~ input/code.cpp: In function 'int main()': input/code.cpp:174:9: warning: unused variable 'comp_1' [-Wunused-variable] int comp_1 = 0; ^~~~~~
Code
#include <iostream>#include <cstring>#include <iomanip>#include <vector>#include <algorithm>using namespace std;typedef long long ll;const int N_MAX = 5005;const ll MOD = 1e9+7;ll fact[N_MAX];ll pow(ll a, ll b) {ll res = 1;for(; b; b/=2) {if(b&1) {res = res * a % MOD;;}a = a * a % MOD;}return res;}ll nCk(ll n, ll k) {if(k > n) return 0;ll tmp = fact[k] * fact[n-k] % MOD;return fact[n] * pow(tmp, MOD-2) % MOD;}int find(int a, vector<int>& du) {if(du[a] == a) return a;return du[a] = find(du[a], du);}void merge(int a, int b, vector<int>& du) {du[find(a, du)] = find(b, du);}bool is_tree(vector<int> v) {vector<int> du(v.size());for(size_t i = 0; i < v.size(); ++i) du[i] = i;for(size_t i = 0; i < v.size(); ++i) {merge(i, v[i], du);}int mi = 1e9;int ma = -1e9;for(size_t i = 0; i < v.size(); ++i) {int x = find(v[i], du);mi = min(mi, x);ma = max(ma, x);}return mi == ma;}int countComponents(vector<int> v) {vector<int> du(v.size());for(size_t i = 0; i < v.size(); ++i) du[i] = i;for(size_t i = 0; i < v.size(); ++i) {if(v[i] == -1) continue;merge(i, v[i], du);}for(size_t i = 0; i < v.size(); ++i) {find(i, du);}sort(du.begin(), du.end());du.erase(unique(du.begin(), du.end()), du.end());return du.size();}void generateGraphs(int tot_nodes, int tot_edges, int n_edges, vector<int>& v, vector<vector<int> >& out) {if(v.size() == tot_nodes) {if(n_edges == tot_edges) {out.push_back(v);}return;}v.push_back(-1);generateGraphs(tot_nodes, tot_edges, n_edges, v, out);v.pop_back();for(int i = 0; i < tot_nodes; ++i) {v.push_back(i);generateGraphs(tot_nodes, tot_edges, n_edges+1, v, out);v.pop_back();}}int solve(int n, int k) {vector<int> tmp;vector<vector<int> > v;generateGraphs(n, n, 0, tmp, v);int ans = 0;for(int i = 0; i < v.size(); ++i) {if(countComponents(v[i]) == k) ++ans;}return ans;}ll g_dp[101][101];ll g(ll n, ll r) {if(g_dp[n][r] != -1) return g_dp[n][r];if(n == 0) return 1;ll sum = 0;for(int i = 1; i <= n; ++i) {ll i_trees = pow(i, i-1);// always take the smallestll i_select = nCk(n-1, i-1);sum += r*g(n-i, r)%MOD * i_trees%MOD * i_select%MOD;}return g_dp[n][r] = sum%MOD;}ll lt_dp2[101][101];ll loopTrees(int n, int r) {if(lt_dp2[n][r] != -1) return lt_dp2[n][r];ll tmp = nCk(n, r)*fact[r-1]%MOD;return lt_dp2[n][r] = tmp*g(n-r, r)%MOD;}ll lt_dp[101];ll loopTrees(int n) {if(lt_dp[n] != -1) return lt_dp[n];ll sum = 0;for(int i = 1; i <= n; ++i) {sum += loopTrees(n, i);}return lt_dp[n] = sum%MOD;}ll dp[101][101];void solve2(int n) {for(int i = 0; i <= n; ++i) {for(int j = 0; j <= n; ++j) {dp[i][j] = 0;}}dp[0][0] = 1;for(int i = 1; i <= n; ++i) {for(int j = 1; j <= i; ++j) {for(int k = 1; k <= i; ++k) {dp[i][j] += dp[i-k][j-1] * nCk(i-1, k-1) % MOD * loopTrees(k) % MOD;}dp[i][j] %= MOD;}}for(int i = 1; i <= n; ++i) {cout<<dp[n][i]<<'\n';}}int main() {memset(lt_dp, -1, sizeof(lt_dp));memset(lt_dp2, -1, sizeof(lt_dp2));memset(g_dp, -1, sizeof(g_dp));fact[0] = 1;for(int i = 1; i < N_MAX; ++i) {fact[i] = fact[i-1] * i % MOD;}//cout<<loopTrees(3, 1)<<endl;//return 0;int n;cin>>n;solve2(n);return 0;for(int i = 1; i < 7; ++i) {for(int j = 1; j <= i; ++j) {cout<<setw(10)<<solve(i, j);}cout<<endl;}for(int i = 1; i < 7; ++i) {/*cout<<"i: " <<i<<endl;for(int j = 1; j <= i; ++j) {cout<<loopTrees(i, j)<<' ';}cout<<endl;*/cout<<i<<' '<<loopTrees(i)<<endl;}return 0;for(int n = 1; n < 10; ++n) {vector<int> tmp;vector<vector<int> > v;generateGraphs(n, n, 0, tmp, v);vector<vector<int> > v2;generateGraphs(n, n-1, 0, tmp, v2);int n_trees = 0;int comp_1 = 0;for(size_t i = 0; i < v.size(); ++i) {int components = countComponents(v[i]);n_trees += (components == 2);}int n_trees_2 = 0;for(size_t i = 0; i < v2.size(); ++i) {int components = countComponents(v2[i]);n_trees_2 += (components == 1);}cout<<n<<' '<<n_trees<<' '<<n_trees_2<<endl;}}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2 |
correct output |
---|
3 1 |
user output |
---|
3 1 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 |
correct output |
---|
17 9 1 |
user output |
---|
17 9 1 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
4 |
correct output |
---|
142 95 18 1 |
user output |
---|
142 95 18 1 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 |
correct output |
---|
1569 1220 305 30 1 |
user output |
---|
1569 1220 305 30 1 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
6 |
correct output |
---|
21576 18694 5595 745 45 ... |
user output |
---|
21576 18694 5595 745 45 ... |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
7 |
correct output |
---|
355081 334369 113974 18515 1540 ... |
user output |
---|
355081 334369 113974 18515 1540 ... |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
8 |
correct output |
---|
6805296 6852460 2581964 484729 49840 ... |
user output |
---|
6805296 6852460 2581964 484729 49840 ... |
Test 9
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
9 |
correct output |
---|
148869153 158479488 64727522 13591116 1632099 ... |
user output |
---|
148869153 158479488 64727522 13591116 1632099 ... |
Test 10
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 |
correct output |
---|
660215659 85349908 783995053 409987640 55545735 ... |
user output |
---|
660215659 85349908 783995053 409987640 55545735 ... |
Test 11
Group: 2, 3
Verdict: ACCEPTED
input |
---|
20 |
correct output |
---|
8033007 474885151 998010619 720259168 345757330 ... |
user output |
---|
8033007 474885151 998010619 720259168 345757330 ... Truncated |
Test 12
Group: 2, 3
Verdict: ACCEPTED
input |
---|
50 |
correct output |
---|
637699856 613177596 194234103 50828885 988168359 ... |
user output |
---|
637699856 613177596 194234103 50828885 988168359 ... Truncated |
Test 13
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 |
correct output |
---|
894456323 406549429 962038245 430640330 61348310 ... |
user output |
---|
894456323 406549429 962038245 430640330 61348310 ... Truncated |
Test 14
Group: 3
Verdict: RUNTIME ERROR
input |
---|
666 |
correct output |
---|
189730587 968711879 553374698 53051125 139917248 ... |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: RUNTIME ERROR
input |
---|
3333 |
correct output |
---|
79235821 455292218 627100211 591681254 695866885 ... |
user output |
---|
(empty) |
Test 16
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4991 |
correct output |
---|
482116496 245260697 151422537 180441123 318466624 ... |
user output |
---|
(empty) |
Test 17
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4992 |
correct output |
---|
141010647 787351178 684701591 872974815 631476284 ... |
user output |
---|
(empty) |
Test 18
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4993 |
correct output |
---|
504034249 588971460 281533415 928250892 416697844 ... |
user output |
---|
(empty) |
Test 19
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4994 |
correct output |
---|
266134603 90079109 544661648 812099750 17249410 ... |
user output |
---|
(empty) |
Test 20
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4995 |
correct output |
---|
833898560 663839791 109127071 321675160 86285359 ... |
user output |
---|
(empty) |
Test 21
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4996 |
correct output |
---|
721158645 167929822 115103278 491345159 114397872 ... |
user output |
---|
(empty) |
Test 22
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4997 |
correct output |
---|
691405606 436947443 82656395 514529009 783319673 ... |
user output |
---|
(empty) |
Test 23
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4998 |
correct output |
---|
829675470 688714502 189351950 956110193 20883331 ... |
user output |
---|
(empty) |
Test 24
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4999 |
correct output |
---|
343936737 47032567 190931571 827280581 160866637 ... |
user output |
---|
(empty) |
Test 25
Group: 3
Verdict: RUNTIME ERROR
input |
---|
5000 |
correct output |
---|
364064601 633559852 352848841 666954216 428009512 ... |
user output |
---|
(empty) |