Submission #1202656

#TimeUsernameProblemLanguageResultExecution timeMemory
1202656just9월 (APIO24_september)C++17
0 / 100
0 ms324 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define vec vector #define add push_back #define all(x) (x).begin(), (x).end() int solve(int n, int m, vec<int> tree, vec<vec<int>> data) { vec<int> deg(n, 0); // number of children for(int i = 0; i < n; i++) { if (tree[i] != -1) deg[tree[i]]++; } set<int> leaves, unused; for(int i = 0; i < n; i++) if (!deg[i]) leaves.insert(i); for(auto &arr: data) reverse(all(arr)); int ans = 0; int cur = 0; int rem = 0; multiset<int> unmatched; while (cur < m) { for(const auto &arr: data) { int x = arr[cur]; unmatched.insert(x); if ((int)unmatched.count(x) == m) { // remove x from unmatched probably; rem += m; if (leaves.count(x)) { leaves.erase(leaves.find(x)); int parent = tree[x]; if (parent != -1) { deg[parent]--; if (deg[parent] == 0) { if (unused.count(parent)) unused.erase(unused.find(parent)); else leaves.insert(parent); } } } else { unused.insert(x); } } } if (unused.size() == 0 && (int)unmatched.size() == rem) { ans++; } cur++; } return ans + 1; }
#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...