oj.uz

Submission #261888

# Submission time Handle Problem Language Result Execution time Memory
261888 2020-08-12T07:21:25 Z patrikpavic2 Mergers (JOI19_mergers) C++17
0 / 100
 109 ms 34284 KB 
#include <cstdio>
#include <vector>

#define PB push_back

using namespace std;

const int N = 5e5 + 500;

vector < int > v[N];
vector < int > koji[N];

int A[N], kol[N], siz[N], sol, bio[N], bla, n;

void dfs(int x, int lst){
	koji[x].PB(A[x]); siz[x] = 1;
	for(int y : v[x]){ 
		if(y == lst) continue;
		dfs(y, x); siz[x] += siz[y];
		if(koji[y].size() > koji[x].size())
			swap(koji[x], koji[y]);
		for(int k : koji[y])
			koji[x].PB(k);
	}
	int ja = 0;
	for(int k : koji[x])
		if(!bio[k])
			bio[k] = 1, ja += kol[k];
	for(int k : koji[x])
		bio[k] = 0;
	sol += (ja == siz[x]);
}

int main(){
	scanf("%d%d", &n, &bla);
	for(int i = 1;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	for(int i = 1;i <= n;i++)
		scanf("%d", A + i), kol[A[i]]++;
	dfs(1, 1);
	printf("%d\n", sol - 1);
	return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &bla);
  ~~~~~^~~~~~~~~~~~~~~~~~
mergers.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:41:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i), kol[A[i]]++;
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 33132 KB Output is correct
2 Incorrect 104 ms 34284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -