Submission #1031110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031110		vjudge1	Paths (BOI18_paths)	C++17	100 / 100	444 ms	25656 KiB

paths

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << endl
#define all(x) x.begin(),x.end()

int n,m,k;
int c[300010];
vector<int> adj[300010];
vector<int> perm;
bool used[6],vis[300010];
ll dp[300010];
ll ans;

void solve()
{
	memset(dp,0,sizeof(dp));
	memset(vis,0,sizeof(vis));
	queue<pii> q;
	for(int i=1;i<=n;i++) if(c[i]==perm[0])
	{
		q.push({i,0});
		dp[i]=1;
	}
	while(!q.empty())
	{
		int u=q.front().fi,idx=q.front().se;
		q.pop();
		if(idx+1==perm.size()) continue;
		for(auto i : adj[u])
		{
			if(c[i]==perm[idx+1])
			{
				dp[i]+=dp[u];
				if(!vis[i]) q.push({i,idx+1});
				vis[i]=1;
			}
		}
		// debug(u);
		// for(int i=1;i<=4;i++) cout<<dp[i]<<' ';cout<<'\n';
	}
	for(int i=1;i<=n;i++) if(c[i]==perm.back())
	{
		ans+=dp[i];
	}
}

void genPerm(int sz)
{
	if(perm.size()==sz)
	{
		// for(auto i : perm) cout<<i<<' ';cout<<'\n';
		solve();
		// debug(ans);
		return;
	}
	for(int i=1;i<=k;i++)
	{
		if(!used[i])
		{
			used[i]=1;
			perm.pb(i);
			genPerm(sz);
			perm.pop_back();
			used[i]=0;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=m;i++) 
	{
		int u,v;cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(int sz=2;sz<=k;sz++) genPerm(sz);
	cout<<ans;
	return 0;
}

Compilation message (stderr)

paths.cpp: In function 'void solve()':
paths.cpp:37:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   if(idx+1==perm.size()) continue;
      |      ~~~~~^~~~~~~~~~~~~
paths.cpp: In function 'void genPerm(int)':
paths.cpp:58:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |  if(perm.size()==sz)
      |     ~~~~~~~~~~~^~~~

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