Submission #790930

#	Time	Username	Problem	Language	Result	Execution time	Memory
790930		ymm	Simurgh (IOI17_simurgh)	C++17	0 / 100	13 ms	3412 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 242;
vector<pii> A[N], Ar[N];
int Am[N][N];
bitset<N> Abs[N], nvis;
int n;

namespace dsu {
	int par[N];
	void init() { memset(par, -1, sizeof(par)); }
	int rt(int v) { return par[v] == -1? v : (par[v] = rt(par[v])); }
	void unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		assert(v != u);
		if (A[v].size() + Ar[v].size() < A[u].size() + Ar[u].size())
			swap(v, u);
		A[v].insert(A[v].end(), A[u].begin(), A[u].end());
		Ar[v].insert(Ar[v].end(), Ar[u].begin(), Ar[u].end());
		for (auto [x, e] : A[u]) {
			Abs[v][x] = 1;
			Am[v][x] = e;
		}
		for (auto [x, e] : Ar[u]) {
			Abs[v][x] = 1;
			Am[v][x] = e;
		}
		par[u] = v;
	}
}
using dsu::rt;

vector<int> gold;
vector<int> cur;

int par[N];
int pare[N];
bool rem[N*N];
vector<int> cyc, cyce;
void make_cyc(int v, int u, int e) {
	cyc.clear();
	cyce.clear();
	for (int x = v; x != u; x = par[x]) {
		cyc.push_back(x);
		cyce.push_back(pare[x]);
	}
	cyc.push_back(u);
	cyce.push_back(e);
}
bool dfscyc(int v, int p, int pe) {
	par[v] = p;
	pare[v] = pe;
	Loop (i,0,A[v].size()) {
		auto [u, e] = A[v][i];
		if (e == pe)
			continue;
		u = rt(u);
		if (rem[e] || u == v) {
			rem[e] = 1;
			swap(A[v].back(), A[v][i]);
			Ar[v].push_back(A[v].back());
			A[v].pop_back();
			--i;
			continue;
		}
		if (par[u] != -1) {
			make_cyc(v, u, e);
			return 1;
		}
		if (dfscyc(u, v, e))
			return 1;
	}
	return 0;
}

void dfs_tr(int v)
{
	nvis[v] = 0;
	int i = -1;
	for (;;) {
		int u = (nvis & Abs[v])._Find_next(i);
		i = u;
		if (u >= n)
			break;
		int e = Am[v][u];
		if (rem[e])
			continue;
		int r = rt(u);
		nvis[u] = 0;
		if (u != r && !nvis[r])
			continue;
		u = r;
		nvis[u] = 0;
		cur.push_back(e);
		dfs_tr(u);
	}
}

void test_cyc()
{
	nvis.set();
	for (int v : cyc)
		nvis[v] = 0;
	cur.clear();
	for (int v : cyc)
		dfs_tr(v);
	vector<int> vec;
	vec.insert(vec.end(), cyce.begin()+1, cyce.end());
	vec.insert(vec.end(), gold.begin(), gold.end());
	vec.insert(vec.end(), cur.begin(), cur.end());
	//cout << cyce[0] << ' ';
	//for (int x : vec)
	//	cout << x << ' ';
	//cout << '\n';
	vector<int> res;
	Loop (i,0,cyc.size()) {
		res.push_back(count_common_roads(vec));
		if (i+1 < cyc.size())
			vec[i] = cyce[i];
	}
	//for (int x : res)
	//	cout << x << ' ';
	//cout << '\n';
	int mn = res[0], mx = res[0];
	for (int x : res) {
		mn = min(mn, x);
		mx = max(mx, x);
	}
	if (mn == mx) {
		for (int e : cyce)
			rem[e] = 1;
		return;
	}
	Loop (i,0,cyc.size()) {
		if (res[i] < mx) {
			gold.push_back(cyce[i]);
			dsu::unite(cyc[i], cyc[i+1 == cyc.size()? 0: i+1]);
		} else {
			rem[cyce[i]] = 1;
		}
	}
}

std::vector<int> find_roads(int n, std::vector<int> V, std::vector<int> U)
{
	::n = n;
	dsu::init();
	Loop (i,0,V.size()) {
		int v = V[i], u = U[i];
		A[v].push_back({u,i});
		A[u].push_back({v,i});
		Abs[v][u] = 1;
		Abs[u][v] = 1;
		Am[v][u] = i;
		Am[u][v] = i;
	}
	for (;;) {
		memset(par, -1, sizeof(par));
		if (!dfscyc(rt(0), -2, -2))
			break;
		test_cyc();
	}
	Loop (i,0,V.size()) {
		int v = V[i], u = U[i];
		if (rem[i] || rt(v) == rt(u))
			continue;
		gold.push_back(i);
	}
	return gold;
}

Compilation message (stderr)

simurgh.cpp: In function 'bool dfscyc(int, int, int)':
simurgh.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
simurgh.cpp:60:2: note: in expansion of macro 'Loop'
   60 |  Loop (i,0,A[v].size()) {
      |  ^~~~
simurgh.cpp: In function 'void test_cyc()':
simurgh.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
simurgh.cpp:123:2: note: in expansion of macro 'Loop'
  123 |  Loop (i,0,cyc.size()) {
      |  ^~~~
simurgh.cpp:125:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   if (i+1 < cyc.size())
      |       ~~~~^~~~~~~~~~~~
simurgh.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
simurgh.cpp:141:2: note: in expansion of macro 'Loop'
  141 |  Loop (i,0,cyc.size()) {
      |  ^~~~
simurgh.cpp:144:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |    dsu::unite(cyc[i], cyc[i+1 == cyc.size()? 0: i+1]);
      |                           ~~~~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
simurgh.cpp:155:2: note: in expansion of macro 'Loop'
  155 |  Loop (i,0,V.size()) {
      |  ^~~~
simurgh.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
simurgh.cpp:170:2: note: in expansion of macro 'Loop'
  170 |  Loop (i,0,V.size()) {
      |  ^~~~

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