oj.uz

Submission #843121

# Submission time Handle Problem Language Result Execution time Memory
843121 2023-09-03T17:30:00 Z b6e1 Beech Tree (IOI23_beechtree) C++17
0 / 100
 46 ms 98132 KB 
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair <int, int> > g[300005];
int n, m, ans[300005], p[300005], c[300005], tin[300005], sz[300005], cnt;
vector<int> t[300005];
map<int, int> vis[300005], dp[300005];
bool check (int v, int u) {
	if (vis[v][u]) return dp[v][u];
	vis[v][u] = 1;
	for (int i = 0, j = 0; i < g[u].size(); i++) {
		while (j < g[v].size() && g[v][j].first != g[u][i].first) j++;
		if (j == g[v].size()) return dp[v][u] = 0;
		if (!check (g[v][j].second, g[u][i].second)) return dp[v][u] = 0;
	}
	return dp[v][u] = 1;
}
void dfs (int v) {
	tin[v] = cnt ++;
	sz[v] = 1;
	ans[v] = 1;
	vector<int> a;
	for (int i = 0; i + 1 < g[v].size(); i++) ans[v] &= (g[v][i].first != g[v][i + 1].first);
	for (auto it : g[v]) {
		int to = it.second;
		a.push_back (to);
		dfs (to);
		sz[v] += sz[to];
		ans[v] &= ans[to];
		ans[v] &= check (v, to);
	}
	sort (a.begin(), a.end(), [] (int i, int j) {return sz[i] > sz[j];});
	for (int i = 0; i < a.size() - 1; i++) ans[v] &= check (a[i], a[i + 1]);
}
vector<int> beechtree (int N, int M, vector<int> P, vector<int> C) {
	n = N;
	for (int i = 0; i < n; i++) {
		g[i].clear();
		p[i] = P[i];
		c[i] = C[i];
		ans[i] = 0;
		vis[i].clear();
		dp[i].clear();
	}
	for (int i = 1; i < n; i++) g[p[i]].push_back ({c[i], i});
	for (int i = 0; i < n; i++)	sort (g[i].begin(), g[i].end());
	dfs (0);
	return vector<int> (ans, ans + n);
}

Compilation message

beechtree.cpp: In function 'bool check(int, int)':
beechtree.cpp:11:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for (int i = 0, j = 0; i < g[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
beechtree.cpp:12:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   while (j < g[v].size() && g[v][j].first != g[u][i].first) j++;
      |          ~~^~~~~~~~~~~~~
beechtree.cpp:13:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   if (j == g[v].size()) return dp[v][u] = 0;
      |       ~~^~~~~~~~~~~~~~
beechtree.cpp:13:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   13 |   if (j == g[v].size()) return dp[v][u] = 0;
beechtree.cpp:14:64: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   14 |   if (!check (g[v][j].second, g[u][i].second)) return dp[v][u] = 0;
beechtree.cpp:16:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   16 |  return dp[v][u] = 1;
beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:23:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 0; i + 1 < g[v].size(); i++) ans[v] &= (g[v][i].first != g[v][i + 1].first);
      |                  ~~~~~~^~~~~~~~~~~~~
beechtree.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i = 0; i < a.size() - 1; i++) ans[v] &= check (a[i], a[i + 1]);
      |                  ~~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 98128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 98128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 98128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 98132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 98128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 98128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 98128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 98128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 98128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 98128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -