Submission #505948

#	Time	Username	Problem	Language	Result	Execution time	Memory
505948		MurotY	Paths (BOI18_paths)	C++14	23 / 100	3083 ms	12868 KiB

paths

#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 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30