Submission #1243049

#TimeUsernameProblemLanguageResultExecution timeMemory
1243049rayan_bdSplit the Attractions (IOI19_split)C++20
0 / 100
2096 ms16320 KiB
#include <bits/stdc++.h> #include "split.h" using namespace std; #define all(x) x.begin(), x.end() const int mxN = 1e5 + 100; vector<int> adj[mxN]; vector<int> curr; bool vis[mxN]; void dfs(int u){ vis[u] = 1; curr.push_back(u); for(auto it : adj[u]){ if(!vis[it]) dfs(it); } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { assert(p.size() == q.size()); assert(a + b + c == n); int m = (int) p.size(), grps = 0; for(int i = 0; i < m; ++i){ adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } vector<int> ans(n, -1); vector<pair<int, int>> ord = {{a, 1}, {b, 2}, {c, 3}}; sort(all(ord)); for(int i = 0; i < n; ++i){ if(!vis[i]){ dfs(i); } while(ord.size() > 0 && curr.size() >= ord[0].first){ set<int> rem; for(int i = 0; i < ord[0].first; ++i){ ans[curr[i]] = ord[0].second; rem.insert(curr[i]); } for(auto it : rem){ curr.erase(find(all(curr), it)); } ord.erase(ord.begin()); } curr.clear(); } for(int i = 0; i < n; ++i){ if(ans[i] == -1){ for(int j = 0; j < n; ++j){ ans[j] = 0; } return ans; } } return ans; } /*int main(){ freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); return 0; }*/
#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...