Submission #748454

#	Time	Username	Problem	Language	Result	Execution time	Memory
748454		mariowong	Paths (BOI18_paths)	C++14	100 / 100	2418 ms	221228 KiB

paths

#include <bits/stdc++.h>
using namespace std;
 
int n,m,colour[300005],u,v,k,ct,len;
vector <int> ans[300005];
long long anss;
vector <int> edge[300005],now;
string pattern[335],r;
unordered_map <string,int> indx;
bool cmp(string a1,string a2){
	return (a1.length() < a2.length() || (a1.length() == a2.length() && a1 < a2));
}
int main() {
	ios::sync_with_stdio(false); 
	cin >> n >> m >> k;
	indx.reserve(500);
	for (int i=1;i<=n;i++){
		cin >> colour[i];
	} 
	for (int i=1;i<=m;i++){
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	for (int i=1;i<(1<<k);i++){
		now.clear();
		for (int j=0;j<k;j++){
			if ((i&(1<<j)) > 0)
			now.push_back(j+1);
		}
		do{
			ct++;
			for (int i=0;i<now.size();i++){
				pattern[ct]+=char(now[i]+'0');
			}
		}while (next_permutation(now.begin(),now.end()));
	}
	sort(pattern+1,pattern+1+ct,cmp);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=ct+1;j++){
			ans[i].push_back(0);
		}
	}
	for (int i=1;i<=ct;i++){
		indx[pattern[i]]=i;
		for (int j=1;j<=n;j++){
			if (pattern[i].length() == 1 && colour[j] == pattern[i][0]-'0')
			ans[j][i]=1;
			else
			if (colour[j] == pattern[i][0]-'0'){
				r.clear(); len=pattern[i].length();
				for (int k=1;k<len;k++){
					r+=pattern[i][k];
				}
				for (int k=0;k<edge[j].size();k++){
					ans[j][i]+=ans[edge[j][k]][indx[r]];
				}	
			}
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=ct;j++){
			anss+=ans[i][j];
		}
	}
	cout << anss-n << "\n";
	return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for (int i=0;i<now.size();i++){
      |                 ~^~~~~~~~~~~
paths.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int k=0;k<edge[j].size();k++){
      |                  ~^~~~~~~~~~~~~~~

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