oj.uz

Submission #133157

# Submission time Handle Problem Language Result Execution time Memory
133157 2019-07-20T08:10:36 Z SirCeness Mergers (JOI19_mergers) C++14
0 / 100
 3000 ms 35764 KB 
#include <bits/stdc++.h>

using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l&&r<=sr
#define outside sr<l||r<sl

using ll = long long;

int n, k;
list<int> adj[500005];
int ilk[500005];
int son[500005];
list<int> st[500005];

int dfs(int node, int ata, int state){
	//cout << "dfs(" << node << ", " << ata << ", " << state << ")" << endl;
	int ret = (son[ilk[node]] == state);
	for (int ch: adj[node]){
		if (ch == ata) continue;
		if (dfs(ch, node, state)){
			ret = 1;
			if (son[ilk[node]] > state) son[state] = son[ilk[node]];
		}
	}
	return ret;
}

int main(){
	cin >> n >> k;
	for (int i = 0; i < n-1; i++){
		int u, v;
		cin >> u >> v;
		u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	for (int i = 0; i < n; i++){
		cin >> ilk[i];
		ilk[i]--;
		st[ilk[i]].pb(i);
	}
	
	for (int i = 0 ; i < k; i++) son[i] = i;
	
	for (int i = 0; i < k; i++){
		if (st[i].size() != 0) dfs(*st[i].begin(), -1, i);
	}
	
	int ans = 0;
	vector<int> say(k, 0);
	for (int i = 0; i < n; i++){
		for (int j: adj[i]){
			if (son[ilk[i]] != son[ilk[j]]){
				//cout << "artir" << bas(i) << bas(j) << endl; 
				say[son[ilk[i]]]++;
				//say[son[ilk[j]]]++;
			}
		}
	}
	
	//for (int i = 0; i < n; i++) cout << son[ilk[i]] << " "; cout << endl;
	
	for (int i = 0; i < k; i++) if (say[i] == 1) ans++;
	cout << (ans+1)/2 << endl;
	
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24036 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 24 ms 23852 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 24 ms 23800 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct
11 Incorrect 24 ms 23800 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24036 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 24 ms 23852 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 24 ms 23800 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct
11 Incorrect 24 ms 23800 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24036 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 24 ms 23852 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 24 ms 23800 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct
11 Incorrect 24 ms 23800 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 35048 KB Output is correct
2 Execution timed out 3035 ms 35764 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24036 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 24 ms 23852 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 24 ms 23800 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct
11 Incorrect 24 ms 23800 KB Output isn't correct
12 Halted 0 ms 0 KB -