oj.uz

답안 #863365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
863365 2023-10-20T05:54:04 Z maks007 Paths (BOI18_paths) C++14
23 / 100
 3000 ms 26960 KB 
// 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -