oj.uz

Submission #790840

# Submission time Handle Problem Language Result Execution time Memory
790840 2023-07-23T08:55:10 Z Amylopectin Simurgh (IOI17_simurgh) C++14
51 / 100
 100 ms 6032 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB correct
2 Correct 1 ms 2688 KB correct
3 Correct 2 ms 2644 KB correct
4 Correct 1 ms 2644 KB correct
5 Correct 2 ms 2644 KB correct
6 Correct 1 ms 2640 KB correct
7 Correct 1 ms 2644 KB correct
8 Correct 2 ms 2644 KB correct
9 Correct 1 ms 2644 KB correct
10 Correct 1 ms 2644 KB correct
11 Correct 1 ms 2644 KB correct
12 Correct 1 ms 2644 KB correct
13 Correct 1 ms 2644 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB correct
2 Correct 1 ms 2688 KB correct
3 Correct 2 ms 2644 KB correct
4 Correct 1 ms 2644 KB correct
5 Correct 2 ms 2644 KB correct
6 Correct 1 ms 2640 KB correct
7 Correct 1 ms 2644 KB correct
8 Correct 2 ms 2644 KB correct
9 Correct 1 ms 2644 KB correct
10 Correct 1 ms 2644 KB correct
11 Correct 1 ms 2644 KB correct
12 Correct 1 ms 2644 KB correct
13 Correct 1 ms 2644 KB correct
14 Correct 3 ms 2644 KB correct
15 Correct 3 ms 2660 KB correct
16 Correct 4 ms 2644 KB correct
17 Correct 3 ms 2648 KB correct
18 Correct 2 ms 2644 KB correct
19 Correct 2 ms 2644 KB correct
20 Correct 2 ms 2644 KB correct
21 Correct 3 ms 2644 KB correct
22 Correct 2 ms 2644 KB correct
23 Correct 2 ms 2644 KB correct
24 Correct 2 ms 2644 KB correct
25 Correct 2 ms 2648 KB correct
26 Correct 2 ms 2636 KB correct
27 Correct 2 ms 2644 KB correct
28 Correct 2 ms 2644 KB correct
29 Correct 2 ms 2644 KB correct
30 Correct 2 ms 2716 KB correct
31 Correct 2 ms 2644 KB correct
32 Correct 2 ms 2644 KB correct
33 Correct 2 ms 2644 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB correct
2 Correct 1 ms 2688 KB correct
3 Correct 2 ms 2644 KB correct
4 Correct 1 ms 2644 KB correct
5 Correct 2 ms 2644 KB correct
6 Correct 1 ms 2640 KB correct
7 Correct 1 ms 2644 KB correct
8 Correct 2 ms 2644 KB correct
9 Correct 1 ms 2644 KB correct
10 Correct 1 ms 2644 KB correct
11 Correct 1 ms 2644 KB correct
12 Correct 1 ms 2644 KB correct
13 Correct 1 ms 2644 KB correct
14 Correct 3 ms 2644 KB correct
15 Correct 3 ms 2660 KB correct
16 Correct 4 ms 2644 KB correct
17 Correct 3 ms 2648 KB correct
18 Correct 2 ms 2644 KB correct
19 Correct 2 ms 2644 KB correct
20 Correct 2 ms 2644 KB correct
21 Correct 3 ms 2644 KB correct
22 Correct 2 ms 2644 KB correct
23 Correct 2 ms 2644 KB correct
24 Correct 2 ms 2644 KB correct
25 Correct 2 ms 2648 KB correct
26 Correct 2 ms 2636 KB correct
27 Correct 2 ms 2644 KB correct
28 Correct 2 ms 2644 KB correct
29 Correct 2 ms 2644 KB correct
30 Correct 2 ms 2716 KB correct
31 Correct 2 ms 2644 KB correct
32 Correct 2 ms 2644 KB correct
33 Correct 2 ms 2644 KB correct
34 Correct 87 ms 3952 KB correct
35 Correct 92 ms 3972 KB correct
36 Correct 83 ms 3768 KB correct
37 Correct 5 ms 2772 KB correct
38 Correct 100 ms 3976 KB correct
39 Correct 94 ms 3916 KB correct
40 Correct 58 ms 3780 KB correct
41 Correct 89 ms 3956 KB correct
42 Correct 88 ms 3964 KB correct
43 Correct 56 ms 3548 KB correct
44 Correct 44 ms 3316 KB correct
45 Correct 43 ms 3284 KB correct
46 Correct 32 ms 3156 KB correct
47 Correct 19 ms 2900 KB correct
48 Correct 3 ms 2644 KB correct
49 Correct 5 ms 2780 KB correct
50 Correct 18 ms 2984 KB correct
51 Correct 43 ms 3404 KB correct
52 Correct 47 ms 3284 KB correct
53 Correct 41 ms 3156 KB correct
54 Correct 45 ms 3652 KB correct
55 Correct 43 ms 3396 KB correct
56 Correct 45 ms 3376 KB correct
57 Correct 43 ms 3384 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB correct
2 Correct 2 ms 2644 KB correct
3 Incorrect 69 ms 6032 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB correct
2 Correct 1 ms 2688 KB correct
3 Correct 2 ms 2644 KB correct
4 Correct 1 ms 2644 KB correct
5 Correct 2 ms 2644 KB correct
6 Correct 1 ms 2640 KB correct
7 Correct 1 ms 2644 KB correct
8 Correct 2 ms 2644 KB correct
9 Correct 1 ms 2644 KB correct
10 Correct 1 ms 2644 KB correct
11 Correct 1 ms 2644 KB correct
12 Correct 1 ms 2644 KB correct
13 Correct 1 ms 2644 KB correct
14 Correct 3 ms 2644 KB correct
15 Correct 3 ms 2660 KB correct
16 Correct 4 ms 2644 KB correct
17 Correct 3 ms 2648 KB correct
18 Correct 2 ms 2644 KB correct
19 Correct 2 ms 2644 KB correct
20 Correct 2 ms 2644 KB correct
21 Correct 3 ms 2644 KB correct
22 Correct 2 ms 2644 KB correct
23 Correct 2 ms 2644 KB correct
24 Correct 2 ms 2644 KB correct
25 Correct 2 ms 2648 KB correct
26 Correct 2 ms 2636 KB correct
27 Correct 2 ms 2644 KB correct
28 Correct 2 ms 2644 KB correct
29 Correct 2 ms 2644 KB correct
30 Correct 2 ms 2716 KB correct
31 Correct 2 ms 2644 KB correct
32 Correct 2 ms 2644 KB correct
33 Correct 2 ms 2644 KB correct
34 Correct 87 ms 3952 KB correct
35 Correct 92 ms 3972 KB correct
36 Correct 83 ms 3768 KB correct
37 Correct 5 ms 2772 KB correct
38 Correct 100 ms 3976 KB correct
39 Correct 94 ms 3916 KB correct
40 Correct 58 ms 3780 KB correct
41 Correct 89 ms 3956 KB correct
42 Correct 88 ms 3964 KB correct
43 Correct 56 ms 3548 KB correct
44 Correct 44 ms 3316 KB correct
45 Correct 43 ms 3284 KB correct
46 Correct 32 ms 3156 KB correct
47 Correct 19 ms 2900 KB correct
48 Correct 3 ms 2644 KB correct
49 Correct 5 ms 2780 KB correct
50 Correct 18 ms 2984 KB correct
51 Correct 43 ms 3404 KB correct
52 Correct 47 ms 3284 KB correct
53 Correct 41 ms 3156 KB correct
54 Correct 45 ms 3652 KB correct
55 Correct 43 ms 3396 KB correct
56 Correct 45 ms 3376 KB correct
57 Correct 43 ms 3384 KB correct
58 Correct 2 ms 2648 KB correct
59 Correct 2 ms 2644 KB correct
60 Incorrect 69 ms 6032 KB WA in grader: NO
61 Halted 0 ms 0 KB -