#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define pii pair<int,int>
const int N = 300000;
vector<int>graph[N],tree[N];
map<char,int>mp;
vector<pii>vcase1;
map<pii,bool>block;
int n;
int mark[N],subtree[N];
int vis[N];
int baki;
int attheke,itheke,ijabe,atjabe;
void make_it_tree(int at){
vis[at] = true;
for(auto i: graph[at]){
if(vis[i])continue;
tree[at].push_back(i);
tree[i].push_back(at);
make_it_tree(i);
}
}
void subtree_count(int at,int par){
subtree[at] = 1;
for(auto i: tree[at]){
if(i == par)continue;
subtree_count(i,at);
subtree[at] += subtree[i];
}
}
void case1(int at,int par,int a){
if(!vcase1.empty())return;
for(auto i: tree[at]){
if(i == par)continue;
// printf("edge %d---%d and sizes are (%d,%d) where a = %d\n",at,i,n-subtree[i],subtree[i],a);
if(subtree[i] > a and n-subtree[i] > a){
vcase1.push_back({at,i});
return;
}
case1(i,at,a);
}
}
void case01(int at){
if(atjabe == 0)return;
atjabe--;
vis[at] = true;
mark[at] = attheke;
for(auto i: tree[at]){
if(vis[i] or block[{at,i}])continue;
case01(i);
}
}
void case11(int at){
if(ijabe == 0)return;
ijabe--;
vis[at] = true;
mark[at] = itheke;
for(auto i: tree[at]){
if(vis[i] or block[{at,i}])continue;
case11(i);
}
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int>tempabc;
tempabc.push_back(a);
tempabc.push_back(b);
tempabc.push_back(c);
sort(tempabc.begin(),tempabc.end());
for(int i = 0; i < (int)tempabc.size();i++){
if(tempabc[i] == a){
mp['a'] = i+1;
tempabc[i] = 1000000000;
break;
}
}
for(int i = 0; i < (int)tempabc.size();i++){
if(tempabc[i] == b){
mp['b'] = i+1;
tempabc[i] = 1000000000;
break;
}
}
for(int i = 0; i < (int)tempabc.size();i++){
if(tempabc[i] == c){
mp['c'] = i+1;
tempabc[i] = 1000000000;
break;
}
}
n = nn;
vector<int> res;
for(int i = 0; i < (int)p.size();i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
make_it_tree(0);
subtree_count(0,-1);
// for(int i = 0; i < n;i++){
// printf("%d = %d\n",i,subtree[i]);
// }
case1(0,-1,min(a,min(b,c)));
// cout << "kere mama ke khobor\n";
if(!vcase1.empty()){
block[{vcase1[0].first,vcase1[0].second}] = true;
if(subtree[vcase1[0].second] >= n-subtree[vcase1[0].second]){
// it means child's subtree is greater
itheke = 2;
ijabe = b;
attheke = 1;
atjabe = a;
}
else {
// it means parent's subtree is greater
itheke = 1;
ijabe = a;
attheke = 2;
atjabe = b;
}
memset(vis,false,sizeof vis);
case01(vcase1[0].first);
case11(vcase1[0].second);
for(int i = 0; i < n;i++){
if(!mark[i])mark[i] = 3;
}
for(int i = 0; i < n;i++){
if(mark[i] == 1)res.push_back(mp['a']);
if(mark[i] == 2)res.push_back(mp['b']);
if(mark[i] == 3)res.push_back(mp['c']);
}
return res;
}
// case 1 completed. There is another fucking case and I have to write more than 100 lines for case 2
// how fucckig amazing -_-
for(int i = 0; i < n;i++)res.push_back(0);
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14456 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14460 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
15608 KB |
invalid split: #1=1, #2=2, #3=2 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
15608 KB |
invalid split: #1=2, #2=4, #3=3 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14456 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
