oj.uz

Submission #1066953

# Submission time Handle Problem Language Result Execution time Memory
1066953 2024-08-20T09:01:55 Z pcc Beech Tree (IOI23_beechtree) C++17
13 / 100
 196 ms 74544 KB 
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 2e5+10;

vector<pii> tree[mxn];
pii par[mxn];
int dep[mxn];
vector<int> lvl[3];
set<int> st[mxn];
vector<int> ans;
vector<int> col[mxn];
bitset<mxn> active;
pii eul[mxn];
int ptr = 0;

void dfs(int now){
	eul[now].fs = ++ptr;
	for(auto [nxt,w]:tree[now]){
		dfs(nxt);
		if(!ans[nxt])ans[now] = 0;
		if(st[now].size()<st[nxt].size())st[now].swap(st[nxt]);
		for(auto &i:st[nxt])st[now].insert(i);
		st[now].insert(w);
	}
	eul[now].sc = ptr;
	if(st[now].size() != tree[now].size())ans[now] = 0;
	int tar = -1;
	for(auto [nxt,w]:tree[now]){
		if(col[w].size()<2)continue;
		int tmp = (col[w][0] == now?col[w][1]:col[w][0]);
		if(eul[tmp].sc<eul[now].fs||eul[now].sc<eul[tmp].fs)continue;
		if(tar == -1)tar = tmp;
		else if(tmp != tar)ans[now] = 0;
	}
	return;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C){
	ans = vector<int>(N,1);
	for(int i = 1;i<N;i++){
		int p = P[i];
		tree[p].push_back(pii(i,C[i]));
		par[i] = pii(p,C[i]);
		col[C[i]].push_back(p);
	}
	dfs(0);
	return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19172 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 10 ms 19036 KB Output is correct
8 Correct 8 ms 19236 KB Output is correct
9 Correct 7 ms 19088 KB Output is correct
10 Incorrect 8 ms 19032 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 8 ms 19036 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19172 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 169 ms 74544 KB Output is correct
8 Correct 127 ms 70776 KB Output is correct
9 Correct 8 ms 19036 KB Output is correct
10 Correct 8 ms 19036 KB Output is correct
11 Correct 7 ms 19072 KB Output is correct
12 Correct 8 ms 19244 KB Output is correct
13 Correct 9 ms 19548 KB Output is correct
14 Correct 8 ms 19672 KB Output is correct
15 Correct 9 ms 19804 KB Output is correct
16 Correct 9 ms 19780 KB Output is correct
17 Correct 76 ms 63428 KB Output is correct
18 Correct 83 ms 63684 KB Output is correct
19 Correct 126 ms 70344 KB Output is correct
20 Correct 196 ms 72788 KB Output is correct

Subtask #3
0.0 / 9.0

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

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 10 ms 19036 KB Output is correct
4 Correct 8 ms 19236 KB Output is correct
5 Correct 169 ms 74544 KB Output is correct
6 Correct 127 ms 70776 KB Output is correct
7 Correct 7 ms 19032 KB Output is correct
8 Correct 11 ms 19404 KB Output is correct
9 Correct 9 ms 19548 KB Output is correct
10 Correct 9 ms 19292 KB Output is correct
11 Correct 122 ms 52524 KB Output is correct
12 Correct 117 ms 47536 KB Output is correct

Subtask #5
0.0 / 14.0

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

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 10 ms 19036 KB Output is correct
4 Correct 8 ms 19236 KB Output is correct
5 Correct 7 ms 19088 KB Output is correct
6 Incorrect 8 ms 19032 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 8 ms 19032 KB Output is correct
2 Incorrect 7 ms 19200 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 10 ms 19036 KB Output is correct
4 Correct 8 ms 19236 KB Output is correct
5 Correct 7 ms 19088 KB Output is correct
6 Incorrect 8 ms 19032 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 8 ms 19032 KB Output is correct
2 Incorrect 7 ms 19200 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -