Submission #845896

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
845896	2023-09-06 18:09:03	sebinkim	Beech Tree (IOI23_beechtree)	C++17	100 / 100	752 ms	222668 KiB

beechtree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
using pii = pair<int, int>;
using piii = tuple<int, int, int>;
vector<int> T[202020], C;
priority_queue<piii> Q;
int S[202020], I[202020];
set<pii> P1[202020];
set<piii> P2[202020];
int n, m;
bool dfs(int u, vector<int> &A) {
  bool f = 1;
  P1[u].emplace(I[u], u);
  for (int &v: T[u]) {
    auto it = P2[u].emplace(C[v], I[v], u).first;
    if (it != P2[u].begin() && get<0>(*prev(it)) == C[v]) f = 0;
    if (next(it) != P2[u].end() && get<0>(*next(it)) == C[v]) f = 0;
  }
  for (int &v: T[u]) {
    f &= dfs(v, A);
    if (P1[u].size() < P1[v].size()) {
      swap(P1[u], P1[v]); swap(P2[u], P2[v]);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

beechtree.cpp: In function 'bool dfs(int, std::vector<int>&)':
beechtree.cpp:45:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    if (next(it1) != P1[u].end() && c != T[next(it1)->second].size()) f = 0;
      |                                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beechtree.cpp:49:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   49 |  return A[u] = f;

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 12 / 12
• Subtask 8: 17 / 17
• Subtask 9: 12 / 12