Submission #790840

#	Time	Username	Problem	Language	Result	Execution time	Memory
790840		Amylopectin	Simurgh (IOI17_simurgh)	C++14	51 / 100	100 ms	6032 KiB

simurgh

#include "simurgh.h"
#include <vector>
#include <algorithm>
using namespace std;
const int mxn = 100010;
struct patt
{
	int to,num;
};
vector<struct patt> pat[mxn] = {};
vector<int> cf,ans;
int np,mp,up[mxn] = {},upa[mxn] = {},par[mxn] = {},papat[mxn] = {},lli[mxn] = {}
,yor[mxn] = {},cru = 0,dep[mxn] = {},he,cli[mxn] = {},cva[mxn] = {};
int fimi(int l,int r)
{
	if(l < r)
	{
		return l;
	}
	return r;
}
int fima(int l,int r)
{
	if(l > r)
	{
		return l;
	}
	return r;
}
int re(int cn,int be)
{
	int i,j,fn,cnu;
	up[cn] = 1;
	for(i=0; i<pat[cn].size(); i++)
	{
		fn = pat[cn][i].to;
		cnu = pat[cn][i].num;
		if(fn == be || up[fn] == 1)
		{
			continue;
		}
		upa[cnu] = 1;
		par[fn] = cn;
		papat[fn] = cnu;
		lli[cru] = cnu;
		dep[fn] = dep[cn] + 1;
		cru ++;
		re(fn,cn);
	}
	return 0;
}
int cal(int ccu,int cad)
{
	int i,j;
	vector<int> ccal;
	for(i=0; i<np-1; i++)
	{
		if(lli[i] != ccu)
		{
			ccal.push_back(lli[i]);
		}
	}
	if(cad != -1)
	{
		ccal.push_back(cad);
	}
	return count_common_roads(ccal);
}
std::vector<int> find_roads(int nn, std::vector<int> uc, std::vector<int> vc) 
{
	int i,j,cn,cm,fn,fm,bva,cl,cr,of,cba,fva,cmi,cma;
	np = nn;
	mp = uc.size();
	for(i=mp-1; i>=0; i--)
	{
		pat[uc[i]].push_back({vc[i],i});
		pat[vc[i]].push_back({uc[i],i});
	}
	he = np/2;
	cru = 0;
	dep[he] = 0;
	par[he] = -1;
	re(he,-1);
	bva = cal(-1,-1);
	for(i=0; i<mp; i++)
	{
		if(upa[i] == 0)
		{
			cl = uc[i];
			cr = vc[i];
			cru = 0;
			if(dep[cl] < dep[cr])
			{
				cn = cl;
				cl = cr;
				cr = cn;
			}
			while(dep[cl] > dep[cr])
			{
				cli[cru] = papat[cl];
				cru ++;
				cl = par[cl];
			}
			while(cl != cr)
			{
				cli[cru] = papat[cl];
				cru ++;
				cl = par[cl];
				cli[cru] = papat[cr];
				cru ++;
				cr = par[cr];
			}
			of = 0;
			cma = bva;
			for(j=0; j<cru; j++)
			{
				if(yor[cli[j]] == 0)
				{
					cva[j] = cal(cli[j],i);
					// if(cmi == -1)
					// {
					// 	cmi = cva[j];
					// }
					// else 
					// {
						cma = fima(cma,cva[j]);
					// }
				}
				else if(yor[cli[j]] != 0 && of == 0)
				{
					cba = cal(cli[j],i);
					fva = yor[cli[j]];
					if(fva == 1)
					{
						cba ++;
					}
					of = 1;
				}
			}
			if(of == 0)
			{
				for(j=0; j<cru; j++)
				{
					if(cva[j] == cma)
					{
						yor[cli[j]] = -1;
					}
					else 
					{
						yor[cli[j]] = 1;
					}
				}
				if(bva == cma)
				{
					yor[i] = -1;
				}
				else 
				{
					yor[i] = 1;
				}
			}
			else 
			{
				for(j=0; j<cru; j++)
				{
					if(yor[cli[j]] == 0)
					{
						if(cba == cva[j])
						{
							yor[cli[j]] = -1;
						}
						else 
						{
							yor[cli[j]] = 1;
						}
					}
				}
				if(bva == cba)
				{
					yor[i] = -1;
				}
				else 
				{
					yor[i] = 1;
				}
			}
		}
	}
	for(i=0; i<mp; i++)
	{
		if(yor[i] == 0 || yor[i] == 1)
		{
			ans.push_back(i);
		}
	}
	return ans;
	// std::vector<int> r(n - 1);
	// for(int i = 0; i < n - 1; i++)
	// 	r[i] = i;
	// int common = count_common_roads(r);
	// if(common == n - 1)
	// 	return r;
	// r[0] = n - 1;
	// return r;
}

Compilation message (stderr)

simurgh.cpp: In function 'int re(int, int)':
simurgh.cpp:34:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<patt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(i=0; i<pat[cn].size(); i++)
      |           ~^~~~~~~~~~~~~~~
simurgh.cpp:32:8: warning: unused variable 'j' [-Wunused-variable]
   32 |  int i,j,fn,cnu;
      |        ^
simurgh.cpp: In function 'int cal(int, int)':
simurgh.cpp:54:8: warning: unused variable 'j' [-Wunused-variable]
   54 |  int i,j;
      |        ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:71:13: warning: unused variable 'cm' [-Wunused-variable]
   71 |  int i,j,cn,cm,fn,fm,bva,cl,cr,of,cba,fva,cmi,cma;
      |             ^~
simurgh.cpp:71:16: warning: unused variable 'fn' [-Wunused-variable]
   71 |  int i,j,cn,cm,fn,fm,bva,cl,cr,of,cba,fva,cmi,cma;
      |                ^~
simurgh.cpp:71:19: warning: unused variable 'fm' [-Wunused-variable]
   71 |  int i,j,cn,cm,fn,fm,bva,cl,cr,of,cba,fva,cmi,cma;
      |                   ^~
simurgh.cpp:71:43: warning: unused variable 'cmi' [-Wunused-variable]
   71 |  int i,j,cn,cm,fn,fm,bva,cl,cr,of,cba,fva,cmi,cma;
      |                                           ^~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30