Submission #1072052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072052		amin	The Ties That Guide Us (CEOI23_incursion)	C++17	30 / 100	276 ms	79444 KiB

incursion

#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
int sz[1000000];
int p[1000000];
int vis[1000000];
vector<int>v[1000000];
int n;
int centroid;
int ans[1000000];
void fin(int in,int col)
{
	vis[in]=1;
	vector<pair<int,int> >k;
	if(p[in]!=in)
	k.push_back({n-sz[in],p[in]});
	//cout<<in<<'  '<<k.size()<<endl;
	for(auto i:v[in])
	{
		if(i==p[in])
		continue;
		k.push_back({sz[i],i});
	}
	sort(k.begin(),k.end());
	int o=k.size()-1;
	if(col==1)
	{
	for(auto i:k)
	{
		if(i.first==k[o].first&&vis[i.second]==0)
		{
			int newcol=visit(i.second);
			fin(i.second,newcol);
			return ;
		}
	}
	int newcol=visit(k[o].second);
	fin(k[o].second,newcol);
	return ;
    }
    if(k.size()==1)
    return ;
    for(auto i:k)
	{
		//cout<<in<<' '<<i.firsti.second<<' '<<k.size()<<endl;
		if(i.first==k[0].first&&vis[i.second]==0)
		{
			int newcol=visit(i.second);
			fin(i.second,newcol);
			return ;
		}
		
	}
    


}

void dfs(int in,int par)
{
	sz[in]=1;
	p[in]=par;
for(auto i:v[in])
{
	if(i==par)
	continue;
	dfs(i,in);
	sz[in]+=sz[i];
}
if(in==par)
{
	ans[in]=0;
	//return ;
}else
{
int h=1;
int j=n-sz[in];
for(auto i:v[in])
{
	if(i==par)
	continue;
	if(sz[i]>j)
	h=0;
}

ans[in]=h;
//cout<<in<<' '<<ans[in]<<endl;
}
}
vector<int> mark(vector<pair<int, int>> f, int safe) {
	n=f.size()+1;
 vector<int>u;
 for(int i=0;i<n-1;i++)
 {
	 v[f[i].first].push_back(f[i].second);
	 v[f[i].second].push_back(f[i].first);
 }
 dfs(safe,safe);
 
 for(int i=1;i<=n;i++)
 {
	 u.push_back(ans[i]);
 }
 return u;
}

void locate(vector<pair<int, int>> f, int curr, int t) {
  n=f.size()+1;
  for(int i=1;i<=n;i++)
  {
	  v[i].clear();
  }
  for(int i=0;i<n-1;i++)
  {
	  v[f[i].first].push_back(f[i].second);
	  v[f[i].second].push_back(f[i].first);
  }
  dfs(curr,curr);
  fin(curr,t);
  return ;
  
}

Compilation message (stderr)

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40