#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |