oj.uz

Submission #1066948

# Submission time Handle Problem Language Result Execution time Memory
1066948 2024-08-20T09:00:03 Z pcc Beech Tree (IOI23_beechtree) C++17
5 / 100
 190 ms 72364 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 now = (col[w][0] == now?col[w][1]:col[w][0]);
		if(tar == -1)tar = now;
		else if(now != 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;
}

Compilation message

beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:36:30: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |   int now = (col[w][0] == now?col[w][1]:col[w][0]);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19240 KB Output is correct
2 Correct 10 ms 19036 KB Output is correct
3 Correct 8 ms 19240 KB Output is correct
4 Correct 9 ms 19144 KB Output is correct
5 Correct 10 ms 19036 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Correct 190 ms 72364 KB Output is correct
8 Correct 139 ms 68652 KB Output is correct
9 Correct 10 ms 19184 KB Output is correct
10 Correct 10 ms 19036 KB Output is correct
11 Correct 9 ms 19052 KB Output is correct
12 Correct 10 ms 19272 KB Output is correct
13 Correct 14 ms 19544 KB Output is correct
14 Correct 12 ms 19804 KB Output is correct
15 Correct 11 ms 19648 KB Output is correct
16 Correct 11 ms 19732 KB Output is correct
17 Correct 89 ms 61228 KB Output is correct
18 Correct 92 ms 61572 KB Output is correct
19 Correct 146 ms 68296 KB Output is correct
20 Correct 164 ms 70772 KB Output is correct

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 19036 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

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

Subtask #5
0.0 / 14.0

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

Subtask #6
0.0 / 14.0

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

Subtask #7
0.0 / 12.0

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

Subtask #8
0.0 / 17.0

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

Subtask #9
0.0 / 12.0

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