oj.uz

Submission #1081274

# Submission time Handle Problem Language Result Execution time Memory
1081274 2024-08-29T20:47:18 Z AmirAli_H1 Beech Tree (IOI23_beechtree) C++17
5 / 100
 156 ms 84736 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;

typedef			long long				ll;
typedef			pair<int, int>			pii;
typedef			pair<ll, ll>			pll;

#define			F						first
#define			S						second
#define			endl					'\n'
#define			sep						' '
#define			pb						push_back
#define			Mp						make_pair
#define			all(x)					(x).begin(),(x).end()
#define			len(x)					((ll) (x).size())

const int maxn = 2e5 + 4;

int n, m;
int par[maxn], col[maxn];
vector<pii> adj[maxn], lsx[maxn];
int sz[maxn], val[maxn];
vector<int> ls[maxn], ans;
int arr[maxn]; set<pii> st[maxn];

bool cmp(int i, int j) {
	return (lsx[i] < lsx[j]);
}

void calx(int v) {
	for (auto f : adj[v]) {
		int c = f.F, u = f.S;
		lsx[v].pb(Mp(c, val[u]));
	}
}

int GIx(int v, int c) {
	int j = lower_bound(all(adj[v]), Mp(c, -1)) - adj[v].begin();
	if (j < len(adj[v]) && adj[v][j].F == c) return j;
	else return -1;
}

bool ok(int v1, int v2) {
	if (val[v1] == val[v2]) return 1;
	else if (val[v1] > val[v2] || len(adj[v1]) > len(adj[v2])) return 0;
	for (auto f : adj[v1]) {
		int c = f.F, u1 = f.S;
		int j = GIx(v2, c);
		if (j == -1) return 0;
		int u2 = adj[v2][j].S;
		if (val[u1] > val[u2]) return 0;
	}
	return 1;
}

bool addx(int v, int x) {
	st[v].insert(Mp(val[x], x));
	auto it = st[v].find(Mp(val[x], x));
	if (it != st[v].begin()) {
		auto itx = it; itx--;
		if (!ok((*itx).S, (*it).S)) return 0;
	}
	auto ity = it; ity++;
	if (ity != st[v].end()) {
		if (!ok((*it).S, (*ity).S)) return 0;
	}
	return 1;
}

void pre_dfs(int v) {
	sz[v] = 1;
	for (auto f : adj[v]) {
		int c = f.F, u = f.S;
		pre_dfs(u);
		sz[v] += sz[u];
	}
}

void res_dfs(int v) {
	ans[v] = 1;
	for (auto f : adj[v]) {
		int c = f.F, u = f.S;
		res_dfs(u);
	}
	for (auto f : adj[v]) {
		int c = f.F, u = f.S;
		if (ans[u] == 0) {
			ans[v] = 0; st[v].clear();
			return ;
		}
	}
	
	addx(v, v);
	for (auto f : adj[v]) {
		int c = f.F, u = f.S;
		if (len(st[u]) > len(st[v])) st[v].swap(st[u]);
		for (auto g : st[u]) {
			if (!addx(v, g.S)) {
				ans[v] = 0; st[v].clear();
				return ;
			}
		}
		st[u].clear();
	}
}

vector<int> beechtree(int Nx, int Mx, vector<int> Px, vector<int> Cx) {
	n = Nx; m = Mx;
	for (int i = 0; i < n; i++) Cx[i]--;
	for (int i = 0; i < n; i++) {
		par[i] = Px[i]; col[i] = Cx[i];
	}
	for (int i = 1; i < n; i++) {
		adj[par[i]].pb(Mp(col[i], i));
	}
	for (int i = 0; i < n; i++) sort(all(adj[i]));
	
	pre_dfs(0);
	for (int v = 0; v < n; v++) ls[sz[v]].pb(v);
	
	int x = 0;
	for (int R = 1; R <= n; R++) {
		int j = 0;
		for (int v : ls[R]) {
			calx(v);
			arr[j++] = v;
		}
		sort(arr, arr + j, cmp);
		
		for (int i = 0; i < j; i++) {
			if (i - 1 >= 0) {
				int u1 = arr[i - 1], u2 = arr[i];
				if (lsx[u1] != lsx[u2]) x++;
			}
			int v = arr[i];
			val[v] = x;
		}
		x++;
	}
	
	ans.resize(n);
	res_dfs(0);
	
	return ans;
}

Compilation message

beechtree.cpp: In function 'void pre_dfs(int)':
beechtree.cpp:76:7: warning: unused variable 'c' [-Wunused-variable]
   76 |   int c = f.F, u = f.S;
      |       ^
beechtree.cpp: In function 'void res_dfs(int)':
beechtree.cpp:85:7: warning: unused variable 'c' [-Wunused-variable]
   85 |   int c = f.F, u = f.S;
      |       ^
beechtree.cpp:89:7: warning: unused variable 'c' [-Wunused-variable]
   89 |   int c = f.F, u = f.S;
      |       ^
beechtree.cpp:98:7: warning: unused variable 'c' [-Wunused-variable]
   98 |   int c = f.F, u = f.S;
      |       ^

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 4 ms 27280 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 5 ms 27224 KB Output is correct
6 Correct 5 ms 27484 KB Output is correct
7 Correct 87 ms 75604 KB Output is correct
8 Correct 102 ms 75524 KB Output is correct
9 Correct 4 ms 27224 KB Output is correct
10 Correct 4 ms 27228 KB Output is correct
11 Correct 4 ms 27224 KB Output is correct
12 Correct 4 ms 27228 KB Output is correct
13 Correct 5 ms 27736 KB Output is correct
14 Correct 6 ms 27740 KB Output is correct
15 Correct 7 ms 27676 KB Output is correct
16 Correct 5 ms 27528 KB Output is correct
17 Correct 156 ms 84736 KB Output is correct
18 Correct 136 ms 80884 KB Output is correct
19 Correct 106 ms 76624 KB Output is correct
20 Correct 91 ms 75684 KB Output is correct

Subtask #3
0.0 / 9.0

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

Subtask #4
0.0 / 8.0

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

Subtask #5
0.0 / 14.0

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

Subtask #6
0.0 / 14.0

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

Subtask #7
0.0 / 12.0

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

Subtask #8
0.0 / 17.0

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

Subtask #9
0.0 / 12.0

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