제출 #720324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720324		Yell0	Paths (BOI18_paths)	C++17	100 / 100	481 ms	30812 KiB

paths

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MN=3e5+2;
int N,M,K,c[MN],perm[6];
ll dp[6][MN],ans=0;
vector<int> gr[MN];

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>N>>M>>K;
  for(int i=1;i<=N;++i) cin>>c[i];
  for(int i=1,u,v;i<=M;++i) {
    cin>>u>>v;
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  iota(perm+1,perm+1+K,1);
  do {
    for(int u=1;u<=N;++u) dp[1][u]=c[u]==perm[1];
    for(int k=2;k<=K;++k) {
      for(int u=1;u<=N;++u) {
        dp[k][u]=0;
        if(c[u]!=perm[k]) continue;
        for(int v:gr[u]) dp[k][u]+=dp[k-1][v];
      }
      if(is_sorted(perm+1+k,perm+1+K))
        for(int u=1;u<=N;++u) ans+=dp[k][u];
    }
  } while(next_permutation(perm+1,perm+1+K));
  cout<<ans<<'\n';
  return 0;
}

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