oj.uz

Submission #505948

# Submission time Handle Problem Language Result Execution time Memory
505948 2022-01-11T10:58:13 Z MurotY Paths (BOI18_paths) C++14
23 / 100
 3000 ms 12868 KB 
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long 
#define ff first
#define ss second
using namespace std;
const int N=2*1e5+7;

vector <ll> g[N];
map <ll,ll> mp;
ll c[N];
bool u[N];
ll res=0, ans=0;
int n, m, k;
void dfs(ll v, ll res1=1){
	if (res1 > k) return ;
	u[v]=1;
	if (mp[c[v]] == 0) res++;
	else {
		u[v]=0;
		return ;
	}
	mp[c[v]]++;
	for (auto l:g[v]){
		if (!u[l]){
			dfs(l, res1+1);
		}
	}
	u[v]=0;
	mp[c[v]]=0;
	return;
}
int main()
{
	cin >> n >> m >> k;
	
	for (int i=1;i<=n;i++) cin >> c[i];
	for (int i=1;i<=m;i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i=1;i<=n;i++){
		res=-1;
		mp.clear();
//		fill(u1,u1+n+1, 0);
		dfs(i); 
//		cout << res <<" ";
		ans+=res;
	}
	cout << ans;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 2 ms 5004 KB Output is correct
5 Correct 2 ms 5000 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3009 ms 12868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 2 ms 5004 KB Output is correct
5 Correct 2 ms 5000 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Execution timed out 3009 ms 12868 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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