oj.uz

Submission #261897

# Submission time Handle Problem Language Result Execution time Memory
261897 2020-08-12T07:31:21 Z patrikpavic2 Mergers (JOI19_mergers) C++17
0 / 100
 115 ms 32496 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;

int dfs(int x, int lst){
	koji[x].PB(A[x]); siz[x] = 1;
	int dolje = 0;
	for(int y : v[x]){ 
		if(y == lst) continue;
		dolje += 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;
	if(ja == siz[x]){
		sol += (dolje - (x != lst) + 1) / 2;
		dolje = 1;
	}
	return dolje;
}

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);
	return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:40: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:42: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:46: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 Correct 16 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 15 ms 23808 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct
12 Incorrect 16 ms 23936 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 15 ms 23808 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct
12 Incorrect 16 ms 23936 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 15 ms 23808 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct
12 Incorrect 16 ms 23936 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 31760 KB Output is correct
2 Correct 115 ms 32496 KB Output is correct
3 Incorrect 18 ms 24192 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 15 ms 23808 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct
12 Incorrect 16 ms 23936 KB Output isn't correct
13 Halted 0 ms 0 KB -