Submission #42847

#	Time	Username	Problem	Language	Result	Execution time	Memory
42847		alenam0161	Simurgh (IOI17_simurgh)	C++14	100 / 100	352 ms	30356 KiB

simurgh

#include "simurgh.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;
#define DG(x) for(int i=0;i<(x).size();++i)cerr<<x[i]<<", ";
const int N = 1e3 + 7;
int used[N];
struct edge {
	int ham, x;
};
vector<edge> g[N], ham[N],Nor[N];
void pr(vector<edge> Tp) {
	for (edge to : Tp) {
		cout << "h=" << to.ham << "and v=" << to.x << ", ";
	}
	cout << endl;
}
vector<int> V, U;
bool is_it_in_T[N*N],Found[N*N];
int arj[N],Q[N];
int How[N*N];
int di[N];
int n,m;
void get_any(int v, vector<int> &T) {
	used[v] = true;
	for (auto to:g[v]) {
		if (used[to.x])continue;
		di[to.x] = di[v] + 1;
		T.push_back(to.ham);
		is_it_in_T[to.ham] = true;
		get_any(to.x, T);
	}
}
int par[N];
int find_par(int v) {
	return (v == par[v] ? v : par[v] = find_par(par[v]));
}
void Merge(int v, int u) {
	v = find_par(v);
	u = find_par(u);
	if (u != v) {
		if (rand() & 1)par[v] = u;
		else par[u] = v;
	}
}
int Newspantree(vector<int> &cur,vector<int> &T) {
	for (int i = 0; i < n; ++i)par[i] = i;
	for (int i = 0; i < cur.size(); ++i)Merge(V[cur[i]], U[cur[i]]);
	int hw = 0;
	for (int i = 0; i < T.size(); ++i) {
		if (find_par(V[T[i]]) == find_par(U[T[i]]))continue;
		Merge(V[T[i]], U[T[i]]);
		cur.push_back(T[i]);
		hw+=Found[T[i]];
	}
	assert(cur.size() == n - 1);
	return hw;
}
vector<int> Cikl;
int curpar[N];
bool gta;
void find_cik(int v,int G,int p) {
	if (gta == false) {
		used[v] = 1;
		for (edge to : g[v]) {
			if (to.x == p)continue;
			if (gta)return;
			if (used[to.x] == 2)continue;
			if (is_it_in_T[to.ham] == false)continue;
			if (used[to.x] == 0) {
				curpar[to.x] = v;
				Cikl.push_back(to.ham);
				find_cik(to.x, G,v);
				if (gta)return;
				Cikl.pop_back();
			}
			else if (used[to.x] == 1 && to.x == G) {
				Cikl.push_back(to.ham);
				gta = true; return;
			}
		}
		if (gta)return;
		for (edge to : g[v]) {
			if (to.x == p)continue;
			if (used[to.x] == 2)continue;
			if (gta)return;
			if (is_it_in_T[to.ham] == true)continue;
			if (used[to.x] == 0) {
				curpar[to.x] = v;
				Cikl.push_back(to.ham);
				find_cik(to.x, G,v);
				if (gta)return;
				Cikl.pop_back();
			}
			else if (used[to.x] == 1 && to.x == G) {
				Cikl.push_back(to.ham);
				gta = true;return;
			}
		}
		used[v] = 2;
	}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	::n = n; ::m = u.size();
	U = u; V = v;
	for (int i = 0; i < u.size(); ++i) {
		g[u[i]].push_back({ i,v[i] });
		g[v[i]].push_back({ i,u[i] });
	}
	vector<int> ans;
	vector<int> T;
	vector<int> val;
	memset(used, 0, sizeof(used));
	get_any(0, T);
	int ct = count_common_roads(T);
	for (int i = 0; i < u.size(); ++i) {
		if (is_it_in_T[i] == true) {
			if (How[i])continue;
			How[i] = true;
			memset(used, 0, sizeof(used));
			Cikl.clear();
			gta = false;
			Cikl.push_back(i);
			used[(di[u[i]] <= di[v[i]] ? u[i] : v[i])] =1;
			find_cik((di[u[i]] >= di[v[i]] ? u[i] : v[i]),( di[u[i]] <= di[v[i]] ? u[i] : v[i]), (di[u[i]] <= di[v[i]] ? u[i] : v[i]));
			val.resize(Cikl.size(), 0);
			for (int ii = 0; ii < Cikl.size(); ++ii) {
				vector<int> cur;
				for (int j = 0; j < Cikl.size(); ++j) {
					if (ii != j)cur.push_back(Cikl[j]);
				}
				Newspantree(cur, T);
				val[ii] = count_common_roads(cur);
			}
			int mx = -1e9;int mn = 1e9;
			for (int ii = 0; ii < Cikl.size(); ++ii) {
				mx = max(mx, val[ii]);
				mn = min(mn, val[ii]);
				How[Cikl[ii]] = true;
			}
			if (mx == mn) {
				for (int ii = 0; ii < Cikl.size(); ++ii) {
					Found[Cikl[ii]] = Cikl.size()<3;
				}
			}
			else {
				for (int ii = 0; ii < Cikl.size(); ++ii) {
					if(mn==val[ii])
					Found[Cikl[ii]] = 1;
					else 
					Found[Cikl[ii]] = 0;
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		vector<int> e;
		for (auto to : g[i])e.push_back(to.ham);
		int k=Newspantree(e, T);
		int gt = count_common_roads(e);
		arj[i] = gt - k;
		Q[i] = gt - k;
	}
	for (int i = 0; i < m; ++i) {
		if (Found[i] == 1) {
			Q[v[i]]--;
			arj[u[i]]--;
			Q[u[i]]--;
			arj[v[i]]--;
		}
	}
	memset(used, 0, sizeof(used));
	for (int i = 0; i < n; ++i) {
		int ps = -1;
		for (int j = 0; j < n; ++j) {
			if (arj[j] == 1 && used[j] == 0) {
				ps = j; break;
			}
		}
		if (ps == -1)break;
		used[ps] = true;
		int hw = 0;
	//	cerr <<"vertex number:"<<i<<" is "<< ps << endl;
		int q = 0;
		for(edge to:g[ps]){
			if (How[to.ham] == true) {
				hw += Found[to.ham];
			}
			else {
				q++;
			}
		}
		int l = 0, r = q-1;
		int mid = l;
		int good = l;
		while (l <= r) {
			mid = (l + r) / 2;
			vector<int> el,er;
			int s = 0;
			int ok = 0;
			for (edge to : g[ps]) {
				if (How[to.ham] == true) {
					continue;
				}
				else {
					if (l <= s && s <= mid) {
						el.push_back(to.ham);
					}
					else if(mid+1<=s&&s<=r){
						er.push_back(to.ham);
					}
					s++;
				}
			}
			int x1=Newspantree(el, T);
			if (count_common_roads(el)-x1 == 1) {
				good = mid; r = mid-1;
			}
			else {
				 l = mid + 1;
			}
		}
		int s = 0;
		int ok = 0;
		for (edge to : g[ps]) {
			if (How[to.ham] == true) {
			}
			else {
				if (s==good) {
					arj[to.x]--;
					How[to.ham] = 1;
					Found[to.ham] = 1;
				}
				s++;
			}
		}
	}
	ans.clear();
	for (int i = 0; i < m; ++i) {
		if (Found[i] == 1)ans.push_back(i);
	}
//	DG(ans);
//	cout << endl;
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'int Newspantree(std::vector<int>&, std::vector<int>&)':
simurgh.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cur.size(); ++i)Merge(V[cur[i]], U[cur[i]]);
                    ^
simurgh.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); ++i) {
                    ^
In file included from /usr/include/c++/5/cassert:43:0,
                 from simurgh.cpp:5:
simurgh.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(cur.size() == n - 1);
                    ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < u.size(); ++i) {
                    ^
simurgh.cpp:118:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < u.size(); ++i) {
                    ^
simurgh.cpp:129:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int ii = 0; ii < Cikl.size(); ++ii) {
                        ^
simurgh.cpp:131:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < Cikl.size(); ++j) {
                       ^
simurgh.cpp:138:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int ii = 0; ii < Cikl.size(); ++ii) {
                        ^
simurgh.cpp:144:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii = 0; ii < Cikl.size(); ++ii) {
                         ^
simurgh.cpp:149:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii = 0; ii < Cikl.size(); ++ii) {
                         ^
simurgh.cpp:202:8: warning: unused variable 'ok' [-Wunused-variable]
    int ok = 0;
        ^
simurgh.cpp:226:7: warning: unused variable 'ok' [-Wunused-variable]
   int ok = 0;
       ^
simurgh.cpp:117:6: warning: unused variable 'ct' [-Wunused-variable]
  int ct = count_common_roads(T);
      ^

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