제출 #1274676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274676		Davdav1232	Paths (BOI18_paths)	C++20	100 / 100	355 ms	21204 KiB

paths

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>> vii;
vector<int> G[300000];
ll dp[300000];
int color[300000];
vector<vector<bool>> check_perm;
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k; cin>>n>>m>>k;
    ll ans=0;
 
    vector<vector<int>> color_sets(k);
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        color[i]=a-1;
        color_sets[a-1].push_back(i);
    }
    for(int i=0; i<m; i++){
        int a, b;
        cin>>a>>b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }
    //graph achieved
    vector<int> thing (k);
    for(int i=0; i<k; i++) thing[i]=i;
    int num;
    if(k==5) num=120;
    if(k==4) num=24;
    if(k==3) num=6;
    if(k==2) num=2;
    if(k==1){
        cout<<0;
        return 0;
    }
    vector<bool> paths_3;
    vector<bool> paths_2;
    if(k==5){
        paths_3.resize(125);
        paths_2.resize(25);
    }
    if(k==4){
        paths_2.resize(16);
    }
    while(num--){
        for(int i=0; i<n; i++){
            if(color[i]==thing[0]) dp[i]=1;
            else dp[i]=0;
        }
        for(int step=1; step<k; step++){
            for(int node : color_sets[thing[step-1]]){
                for(int neighbor : G[node]){
                    if(color[neighbor]==thing[step]){
                        dp[neighbor]+=dp[node];
                    }
                }
            }
        }
        //we found the answers for stuff.
        for(int node : color_sets[thing[k-1]]){
            ans+=dp[node];
        }
        for(int node : color_sets[thing[k-2]]){
            if(k==2) break;
            ans+=dp[node];
        }
        if(k==4){
            //need to add 2_paths
            int t=thing[0]*4+thing[1];
            if(!paths_2[t]){
                paths_2[t]=1;
                for(int node : color_sets[thing[1]]){
                    ans+=dp[node];
                }
            }
        }
        if(k==5){
            int t=thing[0]*5+thing[1];
            if(!paths_2[t]){
                paths_2[t]=1;
                for(int node : color_sets[thing[1]]){
                    ans+=dp[node];
                }
            }
            t=thing[0]*25+thing[1]*5+thing[2];
            if(!paths_3[t]){
                paths_3[t]=1;
                for(int node : color_sets[thing[2]]){
                    ans+=dp[node];
                }
            }
        }
        next_permutation(thing.begin(), thing.end());
    }
    cout<<ans;
    return 0;
}

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