oj.uz

Submission #444160

# Submission time Handle Problem Language Result Execution time Memory
444160 2021-07-13T07:49:53 Z prvocislo Kangaroo (CEOI16_kangaroo) C++17
0 / 100
 1 ms 204 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll mod = 1e9 + 7;
int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return (a * 1ll * b) % mod; }
void upd(int &a, int b) { a = (a + b) % mod; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, s, f;
    cin >> n >> s >> f; 
    vector<vector<int> > dp(n+1, vector<int>(n+1, 0)); // dp[number of vertices][number of components]
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
    {
        if (i == s || i == f)
        {
            upd(dp[i][j], dp[i-1][j-1]); // bud pridame jeden novy komponent
            int c = (j - (s < i) - (f < i));
            if (i == n) c++;
            upd(dp[i][j], mul(dp[i-1][j], c)); // alebo sa napojime na nejaky predosly
        }
        else 
        {
            upd(dp[i][j], dp[i-1][j-1]); // bud pridame jeden novy komponent
            // ideme spojit dva ine komponenty. s a f mozeme (dokonca musime) spojit len ak i == n.
            if (i == n)
            {
                upd(dp[i][j], dp[i-1][j+1]);
            }
            else
            {
                int c1 = (s < i) + (f < i), c2 = j - c1;
                int val = (c2 * (c2 - 1)) * 2 + c1 * c2 * 2;
                upd(dp[i][j], mul(dp[i-1][j+1], val));
            }
        }
    }
    cout << dp[n][1] << "\n";
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct