oj.uz

Submission #857397

# Submission time Handle Problem Language Result Execution time Memory
857397 2023-10-06T06:31:39 Z mychecksedad Beech Tree (IOI23_beechtree) C++17
22 / 100
 96 ms 57744 KB 
#include <beechtree.h>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 2e5+100;

int sz[N];
vector<array<int, 2>> g[N];
vector<int> ans;
set<int> C[N];

void dfs(int v){
	ans[v] = 1;
	sz[v] = 1;
	for(auto U: g[v]){
		int u = U[0], c = U[1];

		dfs(u);
		
		sz[v] += sz[u];
		ans[v] &= ans[u];

		if(C[v].find(c) != C[v].end()) ans[v] = 0;
		C[v].insert(c);
	}
	if(ans[v] == 0) return;

	sort(all(g[v]), [&](const array<int, 2> &x, const array<int, 2> &y){
		return sz[x[0]] > sz[y[0]];
	});

	for(int i = 0; i < g[v].size(); ++i){
		int x = (i == 0 ? v : g[v][i - 1][0]), y = g[v][i][0];
		for(auto col: C[y]){
			if(C[x].find(col) == C[x].end()){
				ans[v] = 0;
				break;
			}
		}
	}
}

vector<int> beechtree(int n, int m, vector<int> P, vector<int> C){
	for(int i = 1; i < n; ++i){
		g[P[i]].pb({i, C[i]});
	}
	ans.resize(n);

	dfs(0);

	return ans;
}

Compilation message

beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < g[v].size(); ++i){
      |                 ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Incorrect 3 ms 14936 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14936 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Incorrect 4 ms 14940 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 83 ms 57428 KB Output is correct
8 Correct 84 ms 57428 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 3 ms 14936 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 4 ms 15196 KB Output is correct
14 Correct 3 ms 15196 KB Output is correct
15 Correct 4 ms 15196 KB Output is correct
16 Correct 4 ms 15196 KB Output is correct
17 Correct 87 ms 57500 KB Output is correct
18 Correct 86 ms 57424 KB Output is correct
19 Correct 86 ms 57744 KB Output is correct
20 Correct 85 ms 57428 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14936 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14936 KB Output is correct
15 Correct 53 ms 23380 KB Output is correct
16 Correct 55 ms 22864 KB Output is correct
17 Correct 60 ms 23120 KB Output is correct
18 Correct 53 ms 23120 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 83 ms 57428 KB Output is correct
6 Correct 84 ms 57428 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 4 ms 15060 KB Output is correct
11 Correct 77 ms 32928 KB Output is correct
12 Correct 96 ms 29840 KB Output is correct

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Incorrect 3 ms 14936 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Incorrect 4 ms 14940 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Incorrect 3 ms 14936 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Incorrect 4 ms 14940 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Incorrect 3 ms 14936 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -