oj.uz

Submission #441467

# Submission time Handle Problem Language Result Execution time Memory
441467 2021-07-05T08:27:59 Z sam571128 Paths (BOI18_paths) C++17
70 / 100
 1269 ms 23112 KB 
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 3e5+5;
vector<int> adj[N];
int col[N], cnt[N], arr[N];
int ans = 0;
int n,m,k;

void solve(int kk){
    for(int u = 1;u <= n;u++){
        if(col[u]==arr[0]) cnt[u] = 1;
        else cnt[u] = 0;
    }

    for(int i = 0;i < kk-1;i++){
        for(int u = 1;u <= n;u++){
            if(col[u]!=arr[i]) continue;
            for(auto v : adj[u]){
                if(col[v]==arr[i+1]) cnt[v] += cnt[u];
            }
        }
    }


    for(int u = 1;u <= n;u++){
        if(col[u]==arr[kk-1]) ans += cnt[u];
    }
}

signed main(){
    fastio
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i++){
        cin >> col[i];
    }
    for(int i = 0;i < m;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int a = 1;a <= k;a++){ 
        arr[0] = a;
        for(int b = 1;b <= k;b++){
            if(a==b) continue;
            arr[1] = b;
            solve(2);
            for(int c = 1;c <= k;c++){
                if(a==c||b==c) continue;
                arr[2] = c;
                solve(3);
                for(int d = 1;d <= k;d++){
                    if(a==d||b==d||c==d) continue;
                    arr[3] = d;
                    solve(4);
                    for(int e = 1; e <= k;e++){
                        if(a==e||b==e||c==e||d==e) continue;
                        arr[4] = d;
                        solve(5);
                    }
                }
            }
        }
    }
    

    cout << ans << "\n";

}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7288 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 6 ms 7280 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 6 ms 7320 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 6 ms 7244 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 14756 KB Output is correct
2 Correct 83 ms 14500 KB Output is correct
3 Correct 428 ms 22536 KB Output is correct
4 Correct 129 ms 15868 KB Output is correct
5 Correct 135 ms 15668 KB Output is correct
6 Correct 314 ms 19340 KB Output is correct
7 Correct 468 ms 22464 KB Output is correct
8 Correct 449 ms 23012 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7288 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 6 ms 7280 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 6 ms 7320 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 6 ms 7244 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct
11 Correct 129 ms 14756 KB Output is correct
12 Correct 83 ms 14500 KB Output is correct
13 Correct 428 ms 22536 KB Output is correct
14 Correct 129 ms 15868 KB Output is correct
15 Correct 135 ms 15668 KB Output is correct
16 Correct 314 ms 19340 KB Output is correct
17 Correct 468 ms 22464 KB Output is correct
18 Correct 449 ms 23012 KB Output is correct
19 Correct 103 ms 14648 KB Output is correct
20 Correct 86 ms 14412 KB Output is correct
21 Correct 434 ms 22568 KB Output is correct
22 Correct 117 ms 15940 KB Output is correct
23 Correct 125 ms 15780 KB Output is correct
24 Correct 309 ms 19324 KB Output is correct
25 Correct 461 ms 22596 KB Output is correct
26 Correct 426 ms 23112 KB Output is correct
27 Correct 157 ms 14484 KB Output is correct
28 Correct 212 ms 16032 KB Output is correct
29 Correct 1261 ms 22572 KB Output is correct
30 Correct 773 ms 18360 KB Output is correct
31 Correct 724 ms 18612 KB Output is correct
32 Correct 1269 ms 22592 KB Output is correct
33 Correct 5 ms 7372 KB Output is correct
34 Correct 5 ms 7372 KB Output is correct
35 Correct 5 ms 7372 KB Output is correct
36 Correct 5 ms 7372 KB Output is correct
37 Correct 5 ms 7244 KB Output is correct
38 Correct 5 ms 7372 KB Output is correct
39 Correct 6 ms 7336 KB Output is correct
40 Correct 7 ms 7372 KB Output is correct
41 Correct 5 ms 7372 KB Output is correct
42 Correct 5 ms 7372 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Incorrect 172 ms 9556 KB Output isn't correct
3 Halted 0 ms 0 KB -