oj.uz

Submission #208457

# Submission time Handle Problem Language Result Execution time Memory
208457 2020-03-11T08:56:24 Z Siberian Unique Cities (JOI19_ho_t5) C++14
0 / 100
 72 ms 5368 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}

const int MAXN = 1e5 + 10;
int n, m;
vector<int> g[MAXN];
int c[MAXN];

void read() {
	cin >> n >> m;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 0; i < m; i++) {
		cin >> c[i];
	}
}

int col[MAXN];

void dfs(int v, int p, int len) {
	if (col[len] == -1) {
		col[len] = c[v];
	}
	else {
		col[len] = -2;
	}
	for (auto i : g[v]) {
		if (i == p) continue;
		dfs(i, v, len + 1);
	}
}

int calc(int v) {
	for (int i = 0; i < n; i++)
		col[i] = -1;
	dfs(v, -1, 0);
	set<int> have;
	for (int i = 1; i < n; i++) {
		have.insert(col[i]);
	}
	have.erase(-1);
	have.erase(-2);
	return have.size();
}

vector<int> ans;

void run() {
	for (int i = 0; i < n; i++) {
		ans.push_back(calc(i));
	}
}

void write() {
	for (auto i : ans) {
		cout << i << "\n";
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	run();
	write();
	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2684 KB Output is correct
2 Incorrect 72 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 5368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2684 KB Output is correct
2 Incorrect 72 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -