Submission #843121

#	Time	Username	Problem	Language	Result	Execution time	Memory
843121		b6e1	참나무 (IOI23_beechtree)	C++17	0 / 100	46 ms	98132 KiB

beechtree

#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 (stderr)

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
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12