Submission #833975

#	Time	Username	Problem	Language	Result	Execution time	Memory
833975		caganyanmaz	Simurgh (IOI17_simurgh)	C++17	51 / 100	85 ms	3444 KiB

simurgh

#include <bits/stdc++.h>
#define pb push_back
#include "simurgh.h"
using namespace std;

#ifdef DEBUGGING

#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 500;
constexpr static int MXM = MXN * MXN;
bitset<MXN> visited;
bitset<MXM> bridge;
bitset<MXM> royal;
int bec[MXN]; // back edge count
int height[MXN];
int mheight[MXN];
int head[MXN];
vector<int> component[MXN];
vector<array<int, 2>> g[MXN];

void dfs(int node, int h, int edge_id)
{
	visited[node] = true;
	height[node] = h;
	mheight[node] = h;
	for (auto [c, ee] : g[node])
	{
		if (ee == edge_id)
			continue;
		if (visited[c])
		{	
			if (node == 1)
				debug(c, height[c]);
			mheight[node] = min(mheight[node], height[c]);
			continue;
		}
		dfs(c, h+1, ee);
		mheight[node] = min(mheight[node], mheight[c]);
		if (node == 1)
			debug(node, mheight[c]);
	}
	debug(node, mheight[node], height[node], edge_id);
	if (mheight[node] == height[node] && edge_id != -1)
		bridge[edge_id] = true;
}

void dfs2(int node, int com)
{
	visited[node] = true;
	head[node] = com;
	component[com].pb(node);
	for (auto [c, ee] : g[node])
		if (!visited[c] && !bridge[ee])
			dfs2(c, com);
}
vector<int> r;

void find_st(int node, int ex)
{
	visited[node] = true;
	for (auto [c, ee] : g[node])
	{
		if (c == ex)
			continue;
		if (!visited[c])
		{
			r.pb(ee);
			find_st(c, ex);
		}
	}
}

void process(int node)
{
	// Creating rest of the tree
	visited.reset();
	r.clear();
	bool first = true;
	for (auto [c, ee] : g[node])
	{
		if (bridge[ee])
		{
			find_st(c, node);
			r.pb(ee);
		}
		if (first && !bridge[ee])
			find_st(c, node);
		if (!bridge[ee])
			first = false;

	}
	debug(node, r);
	// Trying the edges one by one
	
	int smaller = -1;
	vector<int> counts(g[node].size(), -1);
	bool ntp = false;
	int smallest = MXN;
	for (int i = 0; i < g[node].size(); i++)
	{
		auto [c, ee] = g[node][i];
		if (bridge[ee])
			continue;
		if (c < node)
		{
			smaller = ee;
			continue;
		}
		r.pb(ee);
		counts[i] = count_common_roads(r);
		smallest = min(smallest, counts[i]);
		ntp = true;
		r.pop_back();
	}
	if (!ntp)
		return;
	if (smaller != -1)
	{
		r.pb(smaller);
		int rcount = count_common_roads(r);
		r.pop_back();
		if (!royal[smaller])
			rcount++;
		for (int i = 0; i < g[node].size(); i++)
		{
			auto [c, ee] = g[node][i];
			if (counts[i] == -1)
				continue;
			royal[ee] = counts[i] == rcount;
		}
	}
	else
	{
		bool has_bigger = false;
		for (int i = 0; i < g[node].size(); i++)
			if (counts[i] > smallest)
				has_bigger = true;
		if (!has_bigger)
		{
			for (int i = 0; i < g[node].size(); i++)
				if (counts[i] != -1)
					royal[g[node][i][1]] = true;
		}
		else
		{
			for (int i = 0; i < g[node].size(); i++)
				if (counts[i] != -1)
					royal[g[node][i][1]] = counts[i] != smallest;
		}
	}


}

vector<int> find_roads(int n, vector<int> u, vector<int> v) 
{
	int m = u.size();
	for (int i = 0; i < m; i++)
	{
		g[u[i]].pb({v[i], i});
		g[v[i]].pb({u[i], i});
	}
	dfs(0, 0, -1);
	visited.reset();
	int current = 1;
	for (int i = 0; i < n; i++)
		if (!head[i])
			dfs2(i, current++);
	for (int i = 0; i < m; i++)
		royal[i] = bridge[i];

	for (int i = 0; i < n; i++)
		process(i);
	debug(royal.count());
	assert(royal.count() == n-1);
	vector<int> res;
	for (int i = 0; i < m; i++)
		if (royal[i])
			res.pb(i);
	debug(res);
	return res;

}

Compilation message (stderr)

simurgh.cpp: In function 'void process(int)':
simurgh.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for (int i = 0; i < g[node].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~
simurgh.cpp:128:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   for (int i = 0; i < g[node].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~
simurgh.cpp:139:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   for (int i = 0; i < g[node].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~
simurgh.cpp:144:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |    for (int i = 0; i < g[node].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~
simurgh.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |    for (int i = 0; i < g[node].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:1:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:179:23: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  179 |  assert(royal.count() == n-1);
      |         ~~~~~~~~~~~~~~^~~~~~

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