Submission #1058258

#TimeUsernameProblemLanguageResultExecution timeMemory
1058258TheQuantiXBeech Tree (IOI23_beechtree)C++17
9 / 100
2093 ms24592 KiB
#include <bits/stdc++.h> #include "beechtree.h" using namespace std; using ll = long long; ll n, m, q, k, x, y, a, b, l; vector<ll> G[200000]; vector<int> p, c; bool check(vector<int> &v) { map<ll, ll> mp; vector<ll> v1(n); for (int i = 1; i < v.size(); i++) { v1[i] = mp[c[v[i]]]; mp[c[v[i]]]++; // cout << p[v[i]] << ' ' << v1[i] << ' ' << v[v1[i]] << '\n'; if (p[v[i]] != v[v1[i]]) { return 0; } } return 1; } vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) { n = N; m = M; p = P; c = C; for (int i = 1; i < n; i++) { G[P[i]].push_back(i); } if (n <= 8) { vector<int> ans(n); vector< vector<int> > has(n); for (int i = n - 1; i >= 0; i--) { // cout << i << '\n'; has[i].push_back(i); for (int j : G[i]) { for (int k : has[j]) { has[i].push_back(k); } } sort(has[i].begin(), has[i].end()); bool fl = 0; do { // cout << has[i].size() << endl; if (has[i][0] != i) { break; } fl |= check(has[i]); if (fl) { break; } } while (next_permutation(has[i].begin(), has[i].end())); ans[i] = fl; } return ans; } }

Compilation message (stderr)

beechtree.cpp: In function 'bool check(std::vector<int>&)':
beechtree.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 1; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...