#include <bits/stdc++.h>
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
using namespace std;
int sz[100005], vis[100005], ss, rs, piv = -1, vistime = 0, rem;
bool hasBackEdge[100005], keep[100005], okvis[100005];
vector<pair<int, int>> t;
vector<int> sgive, tadj[100005], adj[100005], ans;
pair<int, int> se[100005];
/*
9 4 2 3 10
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
*/
int dfs(int i){
if(vis[i]==1) return 0;
se[i].first = vistime++;
vis[i] = sz[i] = 1;
bool found = false;
for(int j: adj[i]){
if(vis[j]==0) tadj[i].push_back(j);
sz[i]+=dfs(j);
if(sz[j]>=t[0].first) found = true;
}
if(sz[i]>=t[0].first && !found) piv = i;
se[i].second = vistime++;
return sz[i];
}
bool dfs1(int i){
if(!(se[i].first > se[piv].first && se[i].second < se[piv].second)) return true;
if(vis[i]==1) return false;
vis[i] = 1;
for(int j: adj[i]) hasBackEdge[i] = dfs1(j) || hasBackEdge[i];
return hasBackEdge[i];
}
void dfs2(int i){
if(((ss - sz[i]) >= t[0].first) && hasBackEdge[i]){
keep[i] = false;
ss-=sz[i];
rs+=sz[i];
sgive.push_back(i);
return;
}
for(int j: tadj[i]) dfs2(j);
}
void dfs3(int i, int lbl){ //assign from the remaining pile
if(vis[i]==1 || !okvis[i] || rem==0) return;
vis[i] = 1;
ans[i] = lbl;
rem--;
for(int j: adj[i]) dfs3(j, lbl);
}
void dfs4(int i, int lbl){
if(rem==0 || !keep[i]) return;
ans[i] = lbl;
okvis[i] = false;
rem--;
for(int j: tadj[i]) dfs4(j, lbl);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
t = {{a, 1}, {b, 2}, {c, 3}};
sort(t.begin(), t.end());
for(int i = 0;i<p.size();i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
for(int i =0 ;i<n;i++){
vis[i] = 0;
hasBackEdge[i] = false;
okvis[i] = true;
ans.push_back(0);
keep[i] = true;
}
dfs(0);
for(int i =0 ;i<n;i++){
vis[i] = 0;
}
dfs1(piv);
ss = sz[piv];
rs = n - sz[piv];
dfs2(piv);
if(rs<t[0].first || ss<t[0].first) return ans;
int lblr, lbls, szr, szs;
sgive.push_back(0);
if(rs>=t[1].first){
lblr = t[1].second;
szr = t[1].first;
lbls = t[0].second;
szs = t[0].first;
}
else{
lblr = t[0].second;
szr = t[0].first;
lbls = t[1].second;
szs = t[1].first;
}
rem = szs;
dfs4(piv, lbls);
for(int i =0 ;i<n;i++){
vis[i] = 0;
}
rem = szr;
dfs3(0, lblr);
for(int i = 0;i<n;i++){
if(ans[i]==0) ans[i] = t[2].second;
}
return ans;
}
/*signed main(){
int n, a, b, c, m;
cin>>n>>a>>b>>c>>m;
vector<int> p, q;
for(int i = 0;i<m;i++){
int u, v;
cin>>u>>v;
p.push_back(u);
q.push_back(v);
}
vector<int> ans = find_split(n, a, b, c, p, q);
for(int j: ans) cout<<j<<" ";
cout<<endl;
}*/
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<p.size();i++){
~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
4992 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
4992 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
4992 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
5120 KB |
ok, correct split |
| 2 |
Correct |
8 ms |
5120 KB |
ok, no valid answer |
| 3 |
Incorrect |
7 ms |
4992 KB |
jury found a solution, contestant did not |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
4992 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
