oj.uz

답안 #1111705

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1111705 2024-11-12T17:20:29 Z mariaclara Paths (BOI18_paths) C++17
100 / 100
 310 ms 24380 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 3e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair 
#define pb push_back 
#define fr first 
#define sc second

int n, m, k, c[MAXN];
ll qtd[10];
vector<int> edges[MAXN], color[10];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++)
        cin >> c[i], color[c[i]].pb(i);

    while(m--) {
        int a, b;
        cin >> a >> b;
        edges[a].pb(b);
        edges[b].pb(a);
    }

    vector<int> ord;
    for(int i = 1; i <= k; i++) ord.pb(i);

    do {
        vector<ll> dp(n+1);

        for(int i = 0; i < k; i++) {

            for(auto x : color[ord[i]]) {
                if(!i) { dp[x] = 1; qtd[i]++; continue; }

                for(auto viz : edges[x])
                    if(c[viz] == ord[i-1]) dp[x] += dp[viz];

                qtd[i] += dp[x];
            }

        }
    } while(next_permutation(all(ord)));

    ll ans = 0;

    for(int i = k, fat = 1; i > 1; i--, fat *= (k-i)) 
        ans += qtd[i-1] / fat;

    cout << ans << "\n";
}

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7504 KB Output is correct
2 Correct 2 ms 7504 KB Output is correct
3 Correct 3 ms 7504 KB Output is correct
4 Correct 2 ms 7504 KB Output is correct
5 Correct 4 ms 7504 KB Output is correct
6 Correct 2 ms 7504 KB Output is correct
7 Correct 3 ms 7504 KB Output is correct
8 Correct 6 ms 7504 KB Output is correct
9 Correct 5 ms 7504 KB Output is correct
10 Correct 5 ms 7504 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 11080 KB Output is correct
2 Correct 45 ms 11796 KB Output is correct
3 Correct 121 ms 20408 KB Output is correct
4 Correct 66 ms 13620 KB Output is correct
5 Correct 65 ms 12372 KB Output is correct
6 Correct 101 ms 18400 KB Output is correct
7 Correct 127 ms 24080 KB Output is correct
8 Correct 122 ms 21436 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7504 KB Output is correct
2 Correct 2 ms 7504 KB Output is correct
3 Correct 3 ms 7504 KB Output is correct
4 Correct 2 ms 7504 KB Output is correct
5 Correct 4 ms 7504 KB Output is correct
6 Correct 2 ms 7504 KB Output is correct
7 Correct 3 ms 7504 KB Output is correct
8 Correct 6 ms 7504 KB Output is correct
9 Correct 5 ms 7504 KB Output is correct
10 Correct 5 ms 7504 KB Output is correct
11 Correct 52 ms 11080 KB Output is correct
12 Correct 45 ms 11796 KB Output is correct
13 Correct 121 ms 20408 KB Output is correct
14 Correct 66 ms 13620 KB Output is correct
15 Correct 65 ms 12372 KB Output is correct
16 Correct 101 ms 18400 KB Output is correct
17 Correct 127 ms 24080 KB Output is correct
18 Correct 122 ms 21436 KB Output is correct
19 Correct 58 ms 13644 KB Output is correct
20 Correct 52 ms 12012 KB Output is correct
21 Correct 172 ms 20392 KB Output is correct
22 Correct 65 ms 12872 KB Output is correct
23 Correct 63 ms 12264 KB Output is correct
24 Correct 110 ms 17656 KB Output is correct
25 Correct 174 ms 20536 KB Output is correct
26 Correct 190 ms 24380 KB Output is correct
27 Correct 82 ms 11704 KB Output is correct
28 Correct 82 ms 12160 KB Output is correct
29 Correct 310 ms 23220 KB Output is correct
30 Correct 180 ms 18700 KB Output is correct
31 Correct 171 ms 16320 KB Output is correct
32 Correct 308 ms 21996 KB Output is correct
33 Correct 3 ms 7504 KB Output is correct
34 Correct 2 ms 7504 KB Output is correct
35 Correct 3 ms 7504 KB Output is correct
36 Correct 2 ms 7504 KB Output is correct
37 Correct 2 ms 7504 KB Output is correct
38 Correct 2 ms 7504 KB Output is correct
39 Correct 3 ms 7504 KB Output is correct
40 Correct 2 ms 7504 KB Output is correct
41 Correct 3 ms 7504 KB Output is correct
42 Correct 2 ms 7504 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7504 KB Output is correct
2 Correct 71 ms 9296 KB Output is correct
3 Correct 15 ms 9296 KB Output is correct
4 Correct 37 ms 11728 KB Output is correct
5 Correct 29 ms 13900 KB Output is correct
6 Correct 237 ms 12928 KB Output is correct
7 Correct 24 ms 9296 KB Output is correct
8 Correct 70 ms 11856 KB Output is correct
9 Correct 47 ms 12604 KB Output is correct
10 Correct 48 ms 13792 KB Output is correct
11 Correct 137 ms 10188 KB Output is correct
12 Correct 114 ms 12632 KB Output is correct
13 Correct 147 ms 10944 KB Output is correct
14 Correct 235 ms 13128 KB Output is correct
15 Correct 225 ms 13416 KB Output is correct
16 Correct 3 ms 7504 KB Output is correct
17 Correct 2 ms 7504 KB Output is correct
18 Correct 2 ms 7504 KB Output is correct
19 Correct 3 ms 7504 KB Output is correct
20 Correct 3 ms 7504 KB Output is correct
21 Correct 3 ms 7504 KB Output is correct
22 Correct 2 ms 7504 KB Output is correct
23 Correct 4 ms 7676 KB Output is correct
24 Correct 3 ms 7504 KB Output is correct
25 Correct 3 ms 7504 KB Output is correct