Submission #147230

#	Time	Username	Problem	Language	Result	Execution time	Memory
147230		Nucleist	Split the Attractions (IOI19_split)	C++14	7 / 100	1045 ms	1048576 KiB

split

#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];
  	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 (stderr)

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)
                  ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36