Submission #863365

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
863365	2023-10-20T05:54:04 Z	maks007	Paths (BOI18_paths)	C++14	23 / 100	3000 ms	26960 KB

paths

// Bismi Allah
#include "bits/stdc++.h"

using namespace std;

#define int long long

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, k, ans = 0, changes = 1;
	cin >> n >> m >> k;
	vector <int> color(n), g[n], used(n), permutation;
	set <int> colorUsed;
	function <void(int, int)> dfs=[&](int v, int cur) {
		if(cur == permutation.size() - 1) {
			ans++;
			return;
		}
		used[v] = 1;
		for(auto u : g[v] ) {
			if(!used[u] && color[u] == permutation[cur+1]) dfs(u, cur + 1);
		}
		used[v]=0;
	};
	
	for(int i = 0; i < n; i ++) cin >> color[i];
	for(int i = 0; i < m; i ++) {
		int u, v;
		cin >> u >> v;
		u --, v --;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cout << "\n";
	for(int K = 2; K <= k;) {
		if(permutation.size() != K) {
			permutation.resize(K);
			for(int i = 0; i < permutation.size(); i ++) permutation[i] = i + 1;
		}else {
			sort(permutation.begin(), permutation.end());
			for(int i = 0; i < permutation.size() - 1; i ++) {
				if(permutation[i] + 1 == permutation[i + 1]) {
					permutation[i] = i + 1;
					continue;
				}
				permutation[i] ++;
				goto end;
			}
			if(permutation.back() == k) {
				 K ++;
				 continue;
			}
			permutation[permutation.size() - 1] ++;
			end:;
		}
		do{
			for(int i = 0; i < n; i ++) {
				if(color[i] == permutation[0]) dfs(i, 0);
			}
		} while(next_permutation(permutation.begin(), permutation.end()));		
	}
	cout << ans;
	return 0;
}

Compilation message

paths.cpp: In lambda function:
paths.cpp:16:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   if(cur == permutation.size() - 1) {
      |      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp: In function 'int main()':
paths.cpp:37:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   37 |   if(permutation.size() != K) {
      |      ~~~~~~~~~~~~~~~~~~~^~~~
paths.cpp:39:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for(int i = 0; i < permutation.size(); i ++) permutation[i] = i + 1;
      |                   ~~^~~~~~~~~~~~~~~~~~~~
paths.cpp:42:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int i = 0; i < permutation.size() - 1; i ++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:11:24: warning: unused variable 'changes' [-Wunused-variable]
   11 |  int n, m, k, ans = 0, changes = 1;
      |                        ^~~~~~~

Subtask #1

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	431 ms	7772 KB	Output is correct
2	Correct	2224 ms	9848 KB	Output is correct
3	Correct	353 ms	26960 KB	Output is correct
4	Correct	94 ms	13020 KB	Output is correct
5	Correct	60 ms	12884 KB	Output is correct
6	Execution timed out	3058 ms	21188 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	431 ms	7772 KB	Output is correct
12	Correct	2224 ms	9848 KB	Output is correct
13	Correct	353 ms	26960 KB	Output is correct
14	Correct	94 ms	13020 KB	Output is correct
15	Correct	60 ms	12884 KB	Output is correct
16	Execution timed out	3058 ms	21188 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Execution timed out	3067 ms	2652 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-