Submission #718015

#	Time	Username	Problem	Language	Result	Execution time	Memory
718015		amirhoseinfar1385	Paths (BOI18_paths)	C++17	100 / 100	679 ms	24388 KiB

paths

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int>all,val,unnow;
vector<vector<int>>adj,allv;
long long res=0;

void solve(int mina){
	if(mina>k){
		if((int)unnow.size()<=1){
			return ;
		}
		do{
			for(auto x:unnow){
				for(auto y:allv[x]){
					val[y]=0;
				}
			}
			for(int i=0;i<(int)unnow.size()-1;i++){
				for(auto x:allv[unnow[i]]){
					if(i==0){
						val[x]=1;
					}
					for(auto y:adj[x]){
						if(all[y]==unnow[i+1]){
							val[y]+=val[x];
						}
					}
				}
			}
			for(auto x:allv[unnow.back()]){
				res+=val[x];
			}
		}while(next_permutation(unnow.begin(),unnow.end()));
		return ;
	}
	solve(mina+1);
	unnow.push_back(mina);
	solve(mina+1);
	unnow.pop_back();
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	val.resize(n+1);
	all.resize(n+1);
	adj.resize(n+1);
	allv.resize(k+1);
	for(int i=1;i<=n;i++){
		cin>>all[i];
		allv[all[i]].push_back(i);
	}
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	solve(1);
	cout<<res<<'\n';
}

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