Submission #1083449

#TimeUsernameProblemLanguageResultExecution timeMemory
1083449SamueleVidBeech Tree (IOI23_beechtree)C++17
9 / 100
2074 ms29384 KiB
#include <bits/stdc++.h> using namespace std; constexpr int MAXN = 2e5 + 5; constexpr int MAXM = 500 + 5; vector<int> P, C; vector<int> curr; vector<int> permutato; vector<bool> v; vector<int> adj[MAXN]; int colori_usati[MAXM]; bool sol[MAXN]; void vediamo(int u) { // cout << "vediamo " << u << '\n'; // colori_usati[C[u]] ++; vector<int> to_remove; // cout << "colori_usati : "; // for (int i = 0; i < 4; i ++) cout << colori_usati[i] << " "; // cout << '\n'; // cout << "permutazione da verificare per " << u << " : "; // for (auto x : permutato) cout << x << " "; // cout << '\n'; for (int i = 1; i < permutato.size(); i ++) { int f_i = colori_usati[C[permutato[i]]]; // cout << "permutato[i], f_i : " << permutato[i] << " " << f_i << '\n'; if (P[permutato[i]] != permutato[f_i]) { for (auto x : to_remove) colori_usati[x] --; return; } to_remove.push_back(C[permutato[i]]); colori_usati[C[permutato[i]]] ++; } // cout << "permutazione valida per " << u << " : "; // for (auto x : permutato) cout << x << " "; // cout << '\n'; // cout << "sol[u] = 1 !!" << '\n'; for (auto x : to_remove) colori_usati[x] --; sol[u] = 1; // for (int i = 0; i < 4; i ++) cout << sol[i] << " "; // cout << '\n'; } void generate_permutation(int u, int i) { // cout << "permutazione u : " << u << " i : " << i << '\n'; if (sol[u]) return; if (i == curr.size()) return vediamo(u); for (int j = 0; j < curr.size(); j ++) { if (v[j]) continue; v[j] = 1; permutato.push_back(curr[j]); generate_permutation(u, i + 1); permutato.pop_back(); v[j] = 0; } } void check(int u) { v.assign(curr.size(), 0); permutato.clear(); // cout << "curr_size di " << u << " e " << curr.size() << '\n'; permutato.push_back(u); generate_permutation(u, 0); } void dfs(int u) { // cout << "dfs " << u << '\n'; curr.push_back(u); for (auto x : adj[u]) { if (x == P[u]) continue; dfs(x); } } vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) { ::P = P; ::C = C; for (int i = 1; i < N; i ++) { adj[P[i]].push_back(i); adj[i].push_back(P[i]); } fill(sol, sol + N, 0); for (int i = 0; i < N; i ++) { // cout << "i : " << i << '\n'; curr.clear(); fill(colori_usati, colori_usati + MAXM, 0); for (auto x : adj[i]) { if (x == P[i]) continue; dfs(x); } // cout << "fatto dfs: curr "; // for (auto x : curr) cout << x << " "; // cout << '\n'; // cout << "curr per " << i << " : "; // for (auto x : curr) cout << x << " "; // cout << '\n'; // cout << "ora check" << '\n'; check(i); } vector<int> res(N); for (int i = 0; i < N; i ++) res[i] = sol[i]; return res; }

Compilation message (stderr)

beechtree.cpp: In function 'void vediamo(int)':
beechtree.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 1; i < permutato.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
beechtree.cpp: In function 'void generate_permutation(int, int)':
beechtree.cpp:59:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     if (i == curr.size()) return vediamo(u);
      |         ~~^~~~~~~~~~~~~~
beechtree.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int j = 0; j < curr.size(); j ++) {
      |                     ~~^~~~~~~~~~~~~
#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...