#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define pb push_back
struct greateri
{
template<class T>
bool operator()(T const &a, T const &b) const { return a > b; }
};
int n;
int depths[100001];
int firsti[100001];
int seconi[100001];
int subtree[100001];
vector<int>tree[100001];
vector<int>euler;
int dfs(int node,int depth,int p)
{
int ans=1;
depths[node]=depth;
euler.pb(node);
firsti[node]=euler.size()-1;
for (int i = 0; i < tree[node].size(); ++i)
{
int next = tree[node][i];
if(next!=p)
ans+=dfs(next,depth+1,node);
}
euler.pb(node);
seconi[node]=euler.size()-1;
return subtree[node]=ans;
}
set<pair<int,int>>kali;
set<pair<int,int>>included;
int mini,maxi;
int a,b,c;
int yo,go;
bool ansi;
int color1,color2,color3;
void dfs1(int node,int p)
{
kali.erase({subtree[node],node});
included.insert({subtree[node],node});
if(subtree[node]==a)
{
auto hey = included.lower_bound({b+subtree[node],-INF});
auto dey = (*hey).first;
if(dey==b+subtree[node]&& hey!=included.end()){color1=1;color2=2;yo=node;go=(*hey).second;ansi=true;}
auto hey1 = kali.lower_bound({b,-INF});
auto dey1 = (*hey1).first;
if(dey1==b&& hey1!=kali.end()){color1=1;color2=2;yo=node;go=(*hey1).second;ansi=true;}
hey = included.lower_bound({c+subtree[node],-INF});
dey = (*hey).first;
if(dey==c+subtree[node]&& hey!=included.end()){color1=1;color2=3;yo=node;go=(*hey).second;ansi=true;}
hey1 = kali.lower_bound({c,-INF});
dey1 = (*hey1).first;
if(dey1==c&& hey1!=kali.end()){color1=1;color2=3;yo=node;go=(*hey1).second;ansi=true;}
}
if(subtree[node]==b)
{
auto hey = included.lower_bound({a+subtree[node],-INF});
auto dey = (*hey).first;
if(dey==a+subtree[node]&& hey!=included.end()){color1=2;color2=1;yo=node;go=(*hey).second;ansi=true;}
auto hey1 = kali.lower_bound({a,-INF});
auto dey1 = (*hey1).first;
if(dey1==a&& hey1!=kali.end()){color1=2;color2=1;yo=node;go=(*hey1).second;ansi=true;}
hey = included.lower_bound({c+subtree[node],-INF});
dey = (*hey).first;
if(dey==c+subtree[node]&& hey!=included.end()){color1=2;color2=3;yo=node;go=(*hey).second;ansi=true;}
hey1 = kali.lower_bound({c,-INF});
dey1 = (*hey1).first;
if(dey1==c&& hey1!=kali.end()){color1=2;color2=3;yo=node;go=(*hey1).second;ansi=true;}
}
if(subtree[node]==c)
{
auto hey = included.lower_bound({a+subtree[node],-INF});
auto dey = (*hey).first;
if(dey==a+subtree[node] && hey!=included.end()){color1=3;color2=1;yo=node;go=(*hey).second;ansi=true;}
auto hey1 = kali.lower_bound({a,-INF});
auto dey1 = (*hey1).first;
if(dey1==a&& hey1!=kali.end()){color1=3;color2=1;yo=node;go=(*hey1).second;ansi=true;}
hey = included.lower_bound({b+subtree[node],-INF});
dey = (*hey).first;
if(dey==b+subtree[node] && hey!=included.end()){color1=3;color2=2;yo=node;go=(*hey).second;ansi=true;}
hey1 = kali.lower_bound({b,-INF});
dey1 = (*hey1).first;
if(dey1==b && hey1!=kali.end()){color1=3;color2=2;yo=node;go=(*hey1).second;ansi=true;}
}
for (int i = 0; i < tree[node].size(); ++i)
{
int next = tree[node][i];
if(next!=p)
dfs1(next,node);
}
kali.insert({subtree[node],node});
included.erase({subtree[node],node});
}
bool ka,ka1;
int ans[1000001];
void dfs2(int node,int p)
{
if(node==yo)ka=true;
if(node==go)ka1=true;
if(ka)ans[node]=color1;
else if(ka1)ans[node]=color2;
else ans[node]=color3;
for (int i = 0; i < tree[node].size(); ++i)
{
int next = tree[node][i];
if(next!=p)
dfs2(next,node);
}
if(node==yo)ka=false;
if(node==go)ka1=false;
}
vector<int> find_split(int n1,int a1,int b1,int c1,vector<int> p,vector<int>q)
{
//flash;
n=n1;
a=a1;
b=b1;
c=c1;
for (int i = 0; i < n-1; ++i)
{
int x = p[i];
int y = q[i];
x--,y--;
tree[x].pb(y);
tree[y].pb(x);
}
dfs(0,0,-1);
vector<int>depi;
for (int i = 0; i < n; ++i)
{
kali.insert({subtree[i],i});
}
dfs1(0,-1);
set<int>color;
color.insert(1);
color.insert(2);
color.insert(3);
color.erase(color1);
color.erase(color2);
color3=(*color.begin());
if(ansi==1)
dfs2(0,-1);
vector<int>ans1;
for (int i = 0; i < n; ++i)
{
ans1.pb(ans[i]);
}
return ans1;
}
//code the AC sol !
// BS/queue/map
Compilation message
split.cpp: In function 'int dfs(int, int, int)':
split.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tree[node].size(); ++i)
~~^~~~~~~~~~~~~~~~~~~
split.cpp: In function 'void dfs1(int, int)':
split.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tree[node].size(); ++i)
~~^~~~~~~~~~~~~~~~~~~
split.cpp: In function 'void dfs2(int, int)':
split.cpp:117:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tree[node].size(); ++i)
~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
answer contains both zero and positive values |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
answer contains both zero and positive values |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1050 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
