Submission #1160040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160040		jer033	Village (BOI20_village)	C++20	100 / 100	193 ms	31516 KiB

Village

#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
using ll = long long;
const ll INF = 1000000;

ll permutation[11];

void nextpermu(ll n)
{
	ll swapa = n-1;
	while (permutation[swapa]>permutation[swapa+1])
	{
		swapa--;
	}
	ll swapb=swapa+1;
	for (ll i=swapa+1; i<=n; i++)
	{
		if (permutation[i]>permutation[swapa])
		{
			swapb=i;
		}
	}
	ll swapper = permutation[swapa];
	permutation[swapa]=permutation[swapb];
	permutation[swapb]=swapper;
	sort(permutation+swapa+1, permutation+n+1);
}

ll distanc[11][11];
ll visited[100005];
ll visitlist[100005];

void bfs(ll root, vector< vector<ll> > edgelist)
{
	ll currindex = 0;
	ll totalvisited = 1;
	for (ll i=0; i<=11; i++)
	{
		visited[i]=0;
		visitlist[i]=0;
	}
	visited[root]=1;
	visitlist[1]=root;
	while (currindex<totalvisited)
	{
		currindex++;
		ll currnode = visitlist[currindex];
		for (ll neigh: edgelist[currnode])
		{
			if (visited[neigh]==0)
			{
				totalvisited++;
				visitlist[totalvisited]=neigh;
				visited[neigh]=visited[currnode]+1;
				distanc[root][neigh]=visited[currnode];
			}
		}
	}
}

ll hipermu[11];
ll lopermu[11];
void solvesubtask1(ll n, vector< vector<ll> > edgelist)
{
	hipermu[0]=0;
	lopermu[0]=INF;
	for (ll i=1; i<=n; i++)
	{
		bfs(i, edgelist);
	}
	while (permutation[1]>=1)
	{
		bool derangement = 1;
		for (ll i=1; i<=n; i++)
		{
			if (permutation[i]==i)
				derangement = 0;
		}
		if (derangement)
		{
			ll score = 0;
			for (ll i=1; i<=n; i++)
			{
				score = score + distanc[i][permutation[i]];
			}
			if (score<lopermu[0])
			{
				lopermu[0]=score;
				for (ll i=1; i<=n; i++)
				{
					lopermu[i]=permutation[i];
				}
			}
			if (score>hipermu[0])
			{
				hipermu[0]=score;
				for (ll i=1; i<=n; i++)
				{
					hipermu[i]=permutation[i];
				}
			}
		}
		nextpermu(n);
	}
}

ll parent[100005];
ll subtreesize[100005];
ll centroidfinder(ll n, ll root, vector< vector<ll> > edgelist)
{
	//copy of bfs
	ll currindex = 0;
	ll totalvisited = 1;
	visited[root]=1;
	visitlist[1]=root;
	parent[root]=0;
	while (currindex<totalvisited)
	{
		currindex++;
		ll currnode = visitlist[currindex];
		for (ll neigh: edgelist[currnode])
		{
			if (visited[neigh]==0)
			{
				totalvisited++;
				visitlist[totalvisited]=neigh;
				visited[neigh]=visited[currnode]+1;
				parent[neigh]=currnode;
			}
		}
	}
	for (ll i=n; i>=1; i--)
	{
		ll currnode = visitlist[i];
		subtreesize[currnode]++;
		if ((2*subtreesize[currnode])>=n)
			return currnode;
		ll myparent = parent[currnode];
		subtreesize[myparent]+=subtreesize[currnode];
	}
	return -1;//should not happen
}

void centroidbfs(ll n, ll centroid, vector< vector<ll> > edgelist)
{
	ll currindex = 0;
	ll totalvisited = 0;
	for (ll i=1; i<=n; i++)
	{
		visited[i]=0;
		visitlist[i]=0;
		parent[i]=0;
		subtreesize[i]=0;
	}
	visited[centroid]=1;//we dont want it to go to centroid
	parent[centroid]=0;
	//dfs one level then bfs the rest
	for (ll child: edgelist[centroid])
	{
		//each time the loop runs, it starts and ends with currindex = totalvisited
		parent[child]=centroid;
		totalvisited++;
		visited[child]=1;
		visitlist[totalvisited]=child;
		while (currindex<totalvisited)
		{
			currindex++;
			ll currnode = visitlist[currindex];
			for (ll neigh: edgelist[currnode])
			{
				if (visited[neigh]==0)
				{
					totalvisited++;
					visitlist[totalvisited]=neigh;
					visited[neigh]=1;
					parent[neigh]=currnode;
				}
			}
		}
	}
	visitlist[0]=centroid;
	for (ll i=n-1; i>=1; i--)
	{
		ll currnode = visitlist[i];
		subtreesize[currnode]++;
		ll myparent = parent[currnode];
		subtreesize[myparent]+=subtreesize[currnode];
	}
	subtreesize[centroid]=0;//obviously not true but it allows us to skip the centroid later in the calculation
}

long long largest = 0;
ll finalanswer[100005];

void solvelargest(ll n, vector< vector<ll> > edgelist)
{
	ll acentroid = centroidfinder(n, 1, edgelist);
	centroidbfs(n, acentroid, edgelist);
	for (ll i=1; i<=n; i++)
	{
		long long trsize = subtreesize[i];
		largest += trsize;
	}
	largest = largest*2;
	for (ll i=0; i<=n-1; i++)
	{
		ll start = visitlist[i];
		ll endindex = (i+(n/2))%n;
		ll end = visitlist[endindex];
		finalanswer[start]=end;
	}
}

ll dp[100005][2];
//dp[i][0] is the answer for itself
//dp[i][1] is the answer for its children combined
bool carefor[100005];

//INF has been defined as 1M

ll small[100005];
ll total;
void vertexcover(ll n, ll root, vector< vector<ll> > edgelist)
{
	//copy of bfs
	//cout << "VERTEX COVER STARTED\n";
	for (ll i=1; i<=n; i++)
	{
		visited[i]=0;
		visitlist[i]=0;
		parent[i]=0;
	}
	ll currindex = 0;
	ll totalvisited = 1;
	visited[root]=1;
	visitlist[1]=root;
	parent[root]=0;
	vector< vector<ll> > children;
	children.resize(n+1);
	while (currindex<totalvisited)
	{
		currindex++;
		ll currnode = visitlist[currindex];
		for (ll neigh: edgelist[currnode])
		{
			if (visited[neigh]==0)
			{
				totalvisited++;
				visitlist[totalvisited]=neigh;
				visited[neigh]=visited[currnode]+1;
				parent[neigh]=currnode;
				children[currnode].push_back(neigh);
			}
		}
	}
	
	//cout << "BFS DONE\n";
	
	for (ll i=n; i>=1; i--)
	{
		ll currnode = visitlist[i];
		ll ansa = 0;
		ll ansb = 0;
		ll childrentaken = 0;
		for (ll child: children[currnode])
		{
			ansb+=dp[child][0];
			if (dp[child][0] >= (dp[child][1]+1))
			{
				childrentaken++;
				ansa += (dp[child][1]+1);
			}
			else
			{
				ansa += dp[child][0];
			}
		}
		if (children[currnode].size()==0)
		{
			ansa = INF;
		}
		else if (childrentaken == 0)
		{
			ansa++;
		}
		dp[currnode][0] = ansa;
		dp[currnode][1] = ansb;
		//cout << i << ' ' << currnode << ' ' << ansa << ' ' << ansb << '\n';
	}
	
	//cout << "DP DONE\n";
	
	vector< vector<ll> > newedgelist;
	newedgelist.resize(n+3);
	carefor[root]=1;
	for (ll i=1; i<=n; i++)
	{
		carefor[i]=1;
	}
	for (ll i=1; i<=n; i++)
	{
		ll currnode = visitlist[i];
		//cout << currnode << '\n';
		if (carefor[currnode])
		{
			//cout << "I CARE FOR THIS\n";
			ll edgestaken = 0;
			for (ll child: children[currnode])
			{
				//cout << "I HAVE A CHILD, IT IS " << child << '\n';
				if (dp[child][0] >= (dp[child][1]+1))
				{
					edgestaken++;
					newedgelist[currnode].push_back(child);
					newedgelist[child].push_back(currnode);
					//cout << "EDGE BETWEEN " << currnode << " AND " << child << '\n';
					carefor[child]=0;
				}
			}
			//cout << "YES YES YES\n";
			if (edgestaken==0 and children[currnode].size()>0)
			{
				ll child = children[currnode][0];
				carefor[child]=0;
				//MAYBE THIS IS THE ERROR
				for (ll grandchild: children[child])
				{
					carefor[grandchild]=1;
				}
				newedgelist[currnode].push_back(child);
				newedgelist[child].push_back(currnode);
				//cout << "EDGE BETWEEN " << currnode << " AND " << child << '\n';
			}
			//cout << "THIS IS DONE\n";
		}
		if (children[currnode].size()==0 and newedgelist[currnode].size()==0)
		{
			ll myparent = parent[currnode];
			newedgelist[currnode].push_back(myparent);
			newedgelist[myparent].push_back(currnode);
		}
	}
	
	//cout << "NEWEDGELIST COMPLETE\n";
	
	for (ll i=1; i<=n; i++)
	{
		visited[i]=0;
		visitlist[i]=0;
		parent[i]=0;
	}
	//implement dfs
	total = 2*n;
	ll check = 1;
	while (check<=n)
	{
		if (visited[check]==0)
		{
			total--;
			total--;
			stack< vector<ll> > tovisit;
			ll prev = check;
			ll childcount = newedgelist[check].size();
			vector<ll> childs;
			childs.push_back(childcount);
			for (ll i=0; i<childcount; i++)
			{
				childs.push_back(newedgelist[check][i]);
			}
			visited[check]=1;
			tovisit.push(childs);
			while (not tovisit.empty())
			{
				ll topsize = tovisit.top()[0];
				if (topsize==0)
				{
					tovisit.pop();
				}
				else
				{
					ll nextchild = tovisit.top()[topsize];
					tovisit.top()[0]--;
					if (visited[nextchild]==0)
					{
						visited[nextchild]=1;
						small[prev]=nextchild;
						prev=nextchild;
						ll childcountt = newedgelist[nextchild].size();
						vector<ll> childss;
						childss.push_back(childcountt);
						for (ll i=0; i<childcountt; i++)
						{
							childss.push_back(newedgelist[nextchild][i]);
						}
						tovisit.push(childss);
					}
				}
			}
			small[prev]=check;
		}
		check++;
	}
	//cout << "DFS DONE AND PROCESS DONE\n";
}

int main()
{
	ll n;
	cin >> n;
	vector< vector<ll> > edgelist;
	edgelist.resize(n+1);
	for (ll edge=1; edge<=(n-1); edge++)
	{
		ll a, b;
		cin >> a >> b;
		edgelist[a].push_back(b);
		edgelist[b].push_back(a);
	}
	if (n<=0)
	{
		for (ll i=0; i<=n; i++)
		{
			permutation[i]=i;
		}
		solvesubtask1(n, edgelist);
		cout << lopermu[0] << ' ' << hipermu[0] << '\n';
		for (ll i=1; i<=n; i++)
		{
			cout << lopermu[i];
			if (i==n)
			{
				cout << '\n';
			}
			else
			{
				cout << ' ';
			}
		}
		for (ll i=1; i<=n; i++)
		{
			cout << hipermu[i];
			if (i==n)
			{
				cout << '\n';
			}
			else
			{
				cout << ' ';
			}
		}
	}
	else
	{
		solvelargest(n, edgelist);
		vertexcover(n, 1, edgelist);
		cout << total << ' ' << largest << '\n';
		for (ll i=1; i<=n; i++)
		{
			cout << small[i];
			if (i==n)
			{
				cout << '\n';
			}
			else
			{
				cout << ' ';
			}
		}
		for (ll i=1; i<=n; i++)
		{
			cout << finalanswer[i];
			if (i==n)
			{
				cout << '\n';
			}
			else
			{
				cout << ' ';
			}
		}
	}
}

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50