Submission #300956

#	Time	Username	Problem	Language	Result	Execution time	Memory
300956		pacha2880	Simurgh (IOI17_simurgh)	C++17	30 / 100	248 ms	4872 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define mp				make_pair
#define pb				push_back
#define all(a)			(a).begin(), (a).end()
#define sz(a)			a.size()
#define md(a, b)		((a) % b + b) % b
#define mod(a)			md(a, MOD)
#define srt(a)			sort(all(a))
#define mem(a, h)		memset(a, (h), sizeof(a))
#define f 				first
#define s 				second
#define forn(i, n)			for(int i = 0; i < n; i++)
#define fore(i, b, e)	for(int i = b; i < e; i++)
#define forg(i, b, e, m)	for(int i = b; i < e; i+=m)
//int in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

using namespace std;
//using namespace __gnu_pbds;

typedef long long 		ll;
typedef long double ld;	
typedef unsigned long long 		ull;
typedef pair<int, int>  ii;
typedef vector<int>     vi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//find_by_order kth largest  order_of_key <
const int tam = 550;
const int MOD = 1000000007;
const int MOD1 = 998244353;
const double EPS = 1e-9;
const double PI = acos(-1); 
vector<pair<int, int>> g[tam];
vector<pair<int, int>> ng[tam];
vector<int> r;
int parent[tam * tam];
int color[tam * tam];
bool visited[tam], used[tam * tam], vasited[tam * tam];
int poso[tam * tam];
int con = 0;
int n, m;
void dfs0(int node)
{
	visited[node] = 1;
	fore(i, 0, g[node].size())
	{
		if(!visited[g[node][i].f])
		{
			r.pb(g[node][i].s);
			used[g[node][i].s] = 1;
			poso[g[node][i].s] = r.size() - 1;
			ng[node].pb(g[node][i]);
			ng[g[node][i].f].pb({node, g[node][i].s});
			dfs0(g[node][i].f);
		}
	}
}
int find(int n)
{
	if(parent[n] == -1) return n;
	return parent[n] = find(parent[n]);
}
vector<int> res;
bool cicl(int node, int par)
{
	visited[node] = 1;
	//cout<<node<<'\n';
	for(auto cat : ng[node])
	{
		if(!visited[cat.f])
		{
			if(cicl(cat.f, node))
			{
				//cout<<"++++++  "<<node<<' '<<cat.f<<' '<<cat.s<<'\n';
				res.pb(cat.s);
				return true;
			}
		}
		else if(cat.f != par)
		{
			//cout<<"======  "<<node<<' '<<cat.f<<' '<<cat.s<<'\n';
			res.pb(cat.s);
			return true;
		}
	}
	return false;
}
vector<int> find_roads(int nn, vector<int> u, vector<int> v) {
	n = nn;
	m = u.size();
	fore(i, 0, m)
	{
		g[u[i]].pb({v[i], i});
		g[v[i]].pb({u[i], i});
	}
	dfs0(0);
	int x = count_common_roads(r), y, a, b;
	if(x == n - 1) return r;
	//cout<<r.size()<<' '<<x<<'\n';
	/*fore(i, 0, r.size())
	{
		cout<<r[i]<<','<<poso[r[i]]<<"  ";
	}
	cout<<'\n';*/
	int remp;
	int cont, sel;
	mem(parent, -1);
	bool bon;
	fore(i, 0, m)
	{
		if(!used[i])
		{
			//cout<<i<<' '<<v[i]<<' '<<u[i]<<'\n';
			ng[u[i]].pb({v[i], i});
			ng[v[i]].pb({u[i], i});
			fore(i, 0, n) visited[i] = 0;
			res.clear();
			cicl(u[i], -1);
			ng[u[i]].pop_back();
			ng[v[i]].pop_back();
			vasited[i] = 1;
			cont = 0;
			//cout<<res.size()<<'\n';
			//cout<<"mi ciclo  "<<res[0]<<'\n';
			bon = false;
			fore(j, 1, res.size())
			{
				//cout<<res[j]<<','<<poso[res[j]]<<','<<r[poso[res[j]]]<<' ';
				remp = res[j];
				if(vasited[remp])
					sel = remp;
				else
				{
					r[poso[remp]] = i;
					y = count_common_roads(r);
					if(y == x)
					{
						cont++;
						a = find(i);
						b = find(remp);
						if(a != b)
						{
							if(color[a] == 0)
								color[a] = color[b];
							parent[a] = b;
						}
					}
					else if(y == x + 1)
					{
						bon = true;
						color[find(i)] = 1;
						color[find(remp)] = -1;
					}
					else
					{
						bon = true;
						color[find(i)] = -1;
						color[find(remp)] = 1;
					}
					r[poso[remp]] = remp;
				}
				vasited[remp] = 1;
			}
			//cout<<"\n\n";
			if(cont == res.size() - 1)
				color[find(i)] = -1;
			else if(!bon)
			{
				remp = sel;
				r[poso[remp]] = i;
				y = count_common_roads(r);
				if(y == x)
				{
					a = find(i);
					b = find(remp);
					if(a != b)
					{
						if(color[a] == 0)
							color[a] = color[b];
						parent[a] = b;
					}
				}
				else if(y == x + 1)
				{
					bon = true;
					color[find(i)] = 1;
					color[find(remp)] = -1;
				}
				else
				{
					bon = true;
					color[find(i)] = -1;
					color[find(remp)] = 1;
				}
				r[poso[remp]] = remp;
			}
		}
	}
	//cout<<"hola\n";
	r.clear();
	fore(i, 0, m)
	{
		color[i] = color[find(i)];
		//cout<<u[i]<<'-'<<v[i]<<' '<<i<<" color -> "<<color[i]<<'\n';
		if(color[i] >= 0)
		{
			color[i] = 1;
			//cout<<i<<'\n';
			r.pb(i);
		}
		//cout<<u[i]<<'-'<<v[i]<<' '<<i<<" color -> "<<color[i]<<'\n';
	}
	//cout<<"cocacola\n";
	return r;
}

Compilation message (stderr)

simurgh.cpp: In function 'void dfs0(int)':
simurgh.cpp:16:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define fore(i, b, e) for(int i = b; i < e; i++)
......
   49 |  fore(i, 0, g[node].size())
      |       ~~~~~~~~~~~~~~~~~~~~              
simurgh.cpp:49:2: note: in expansion of macro 'fore'
   49 |  fore(i, 0, g[node].size())
      |  ^~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:16:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define fore(i, b, e) for(int i = b; i < e; i++)
......
  130 |    fore(j, 1, res.size())
      |         ~~~~~~~~~~~~~~~~                
simurgh.cpp:130:4: note: in expansion of macro 'fore'
  130 |    fore(j, 1, res.size())
      |    ^~~~
simurgh.cpp:169:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |    if(cont == res.size() - 1)
      |       ~~~~~^~~~~~~~~~~~~~~~~
simurgh.cpp:64:13: warning: 'sel' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |  if(parent[n] == -1) return n;
      |     ~~~~~~~~^
simurgh.cpp:110:12: note: 'sel' was declared here
  110 |  int cont, sel;
      |            ^~~

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