Submission #446576

#	Time	Username	Problem	Language	Result	Execution time	Memory
446576		keta_tsimakuridze	Paths (BOI18_paths)	C++14	100 / 100	733 ms	79840 KiB

paths

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int N=3e5+5,mod=1e9+7;
int t,n,m,k,cnt[N],col[N];
vector<pair<int,ll> > en[34];
vector<int> V[N][6];
 main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>col[i];
		col[i]--;
		V[0][col[i]].push_back(i);
	}
	for(int i=1;i<=m;i++) {
		int u,v;
		cin>>u>>v;
		V[u][col[v]].push_back(v);
		V[v][col[u]].push_back(u);
	}
	en[0].push_back({0,1});
	ll ans = -n;
	for(int i = 1; i<(1<<k); i++) {
		for(int j=1;j<=n;j++) cnt[j] = 0;
		for(int j=0;j<k;j++) {
			if(!((1<<j) & i)) continue;
			int b = i ^ (1<<j);
			for(int k=0; k<en[b].size(); k++){
				int u = en[b][k].f;
				for(int p=0; p<V[u][j].size(); p++) {
					cnt[V[u][j][p]] += en[b][k].s;
				}
			}
		}
		for(int j=1;j<=n;j++) {
			if(cnt[j]) en[i].push_back({j,cnt[j]}), ans += cnt[j];
		}
	}
	cout<<ans;
}

Compilation message (stderr)

paths.cpp:10:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 |  main(){
      |  ^~~~
paths.cpp: In function 'int main()':
paths.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    for(int k=0; k<en[b].size(); k++){
      |                 ~^~~~~~~~~~~~~
paths.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int p=0; p<V[u][j].size(); p++) {
      |                  ~^~~~~~~~~~~~~~~

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