Submission #441475

#	Time	Username	Problem	Language	Result	Execution time	Memory
441475		sam571128	Paths (BOI18_paths)	C++17	100 / 100	1339 ms	23212 KiB

paths

#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;
        if(k>=2)
            for(int b = 1;b <= k;b++){
                if(a==b) continue;
                arr[1] = b;
                solve(2);
                if(k>=3)
                    for(int c = 1;c <= k;c++){
                        if(a==c||b==c) continue;
                        arr[2] = c;
                        solve(3);
                        if(k>=4)
                            for(int d = 1;d <= k;d++){
                                if(a==d||b==d||c==d) continue;
                                arr[3] = d;
                                solve(4);
                                if(k>=5)
                                    for(int e = 1; e <= k;e++){
                                        if(a==e||b==e||c==e||d==e) continue;
                                        arr[4] = e;
                                        solve(5);
                                    }
                            }
                    }
            }
    }
    

    cout << ans << "\n";

}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30