Submission #59614

#	Time	Username	Problem	Language	Result	Execution time	Memory
59614		IvanC	Paths (BOI18_paths)	C++17	100 / 100	2212 ms	109436 KiB

paths

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 3*1e5 + 10;

int N,M,K,cor[MAXN];
vector<int> grafo[MAXN];
ll tot,valor[MAXN];

void processa(vector<int> ordem){
	if(ordem.size() == 1) return;
	for(int i = 1;i<=N;i++){
		valor[i] = 0;
		if(cor[i] == ordem[0]) valor[i] = 1;
	}
	for(int i = 1;i<ordem.size()-1;i++){
		for(int v = 1;v<=N;v++){
			if(cor[v] != ordem[i]) continue;
			for(int u : grafo[v]){
				if(cor[u] == ordem[i-1]) valor[v] += valor[u];
			}
		}
	}
	for(int i = 1;i<=N;i++){
		if(cor[i] != ordem.back()) continue;
		for(int u : grafo[i]){
			if(cor[u] == ordem[ordem.size()-2]) tot += valor[u];
		}
	}
}

int main(){
	scanf("%d %d %d",&N,&M,&K);
	for(int i = 1;i<=N;i++){
		scanf("%d",&cor[i]);
		cor[i]--;
	}
	for(int i =1;i<=M;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}
	for(int bitmask = 1;bitmask < (1 << K);bitmask++){
		vector<int> temp;
		for(int i = 0;i<K;i++){
			if(bitmask & (1 << i)) temp.push_back(i);
		}
		do{
			processa(temp);
		}while(next_permutation(temp.begin(),temp.end()));
	}
	printf("%lld\n",tot);
	return 0;
}

Compilation message (stderr)

paths.cpp: In function 'void processa(std::vector<int>)':
paths.cpp:17:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1;i<ordem.size()-1;i++){
                ~^~~~~~~~~~~~~~~
paths.cpp: In function 'int main()':
paths.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&M,&K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
paths.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&cor[i]);
   ~~~~~^~~~~~~~~~~~~~
paths.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~

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