oj.uz

Submission #864397

# Submission time Handle Problem Language Result Execution time Memory
864397 2023-10-22T17:36:21 Z iskhakkutbilim Paths (BOI18_paths) C++17
23 / 100
 3000 ms 61548 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 3e5;
int n, m, col[N+1];
int k;
vector<int> g[N+1][6];
int ans;

int used[N+10], used_c[N+10];
int timer = 1, closed;
void dfs(int v){
	used[v] = timer, used_c[col[v]] = timer;
	ans++;
	if(closed == k){
		used[v] = timer-1, used_c[col[v]] = timer-1, closed--;
		return;
	}
	for(int j = 1;j <= k; j++){
		if(used_c[j] != timer){
			for(int to : g[v][j]){
				if(used[to] != timer){
					closed++;
					dfs(to);
					closed--;
				}
			}
		}
	}
	used[v] = timer-1, used_c[col[v]] = timer-1;
}

main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1;i <= n; i++){
		cin >> col[i];
	}
	for(int i = 0;i < m; i++){
		int a, b; cin >> a >> b;
		g[a][col[b]].push_back(b);
		g[b][col[a]].push_back(a);
	}
	
	
	for(int i = 1;i <= n; i++){
		closed = 1;
		dfs(i);
		ans--;
		timer++;
	}
	
	cout << ans;
	return 0;
}

Compilation message

paths.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main(){
      | ^~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45404 KB Output is correct
2 Correct 9 ms 45404 KB Output is correct
3 Correct 9 ms 45404 KB Output is correct
4 Correct 9 ms 45560 KB Output is correct
5 Correct 10 ms 45404 KB Output is correct
6 Correct 9 ms 45404 KB Output is correct
7 Correct 9 ms 45404 KB Output is correct
8 Correct 9 ms 45492 KB Output is correct
9 Correct 9 ms 45552 KB Output is correct
10 Correct 10 ms 45404 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 53760 KB Output is correct
2 Correct 654 ms 52652 KB Output is correct
3 Correct 299 ms 61548 KB Output is correct
4 Correct 83 ms 53932 KB Output is correct
5 Correct 71 ms 53536 KB Output is correct
6 Execution timed out 3050 ms 58284 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45404 KB Output is correct
2 Correct 9 ms 45404 KB Output is correct
3 Correct 9 ms 45404 KB Output is correct
4 Correct 9 ms 45560 KB Output is correct
5 Correct 10 ms 45404 KB Output is correct
6 Correct 9 ms 45404 KB Output is correct
7 Correct 9 ms 45404 KB Output is correct
8 Correct 9 ms 45492 KB Output is correct
9 Correct 9 ms 45552 KB Output is correct
10 Correct 10 ms 45404 KB Output is correct
11 Correct 186 ms 53760 KB Output is correct
12 Correct 654 ms 52652 KB Output is correct
13 Correct 299 ms 61548 KB Output is correct
14 Correct 83 ms 53932 KB Output is correct
15 Correct 71 ms 53536 KB Output is correct
16 Execution timed out 3050 ms 58284 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45400 KB Output is correct
2 Execution timed out 3027 ms 48220 KB Time limit exceeded
3 Halted 0 ms 0 KB -