Submission #58792

#	Time	Username	Problem	Language	Result	Execution time	Memory
58792		reality	Simurgh (IOI17_simurgh)	C++17	0 / 100	3098 ms	8800 KiB

simurgh

#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1024;
int was[N * N];
int w[N][N];
int s[N][N];
int f[N];
vi g[N];
pii dfs(int node) {
	for (auto it : g[node])
		if (f[it] == -1 && !was[w[node][it]]) {
			f[it] = node;
			auto cnt = dfs(it);
			if (cnt != mp(-1,-1))
				return cnt;
		}
		else
		if (f[node] != it && f[it] != -1 && !was[w[node][it]])
			return mp(node,it);
	return mp(-1,-1);
}
int p[N];
int Ws[N * N];
int get(int k) {
	return k == p[k] ? k : p[k] = get(p[k]);
} 
vi find_roads(int n,vi u,vi v) {
	int called = 0;
	int m = u.size();
	memset(w,-1,sizeof(w));
	memset(s,-1,sizeof(s));
	for (int i = 0;i < m;++i)
		w[u[i]][v[i]] = w[v[i]][u[i]] = i,g[u[i]].pb(v[i]),g[v[i]].pb(u[i]);
	vi answer;	
	if (m != n * (n - 1) / 2) {
	 	for (int i = 0;i < n;++i)
			p[i] = i;
		vi ee;
		for (int i = 0;i < m;++i)
			if (get(u[i]) != get(v[i])) {
				ee.pb(i);
				p[get(u[i])] = get(v[i]);
			}
		do {
			vi cycle;
			for (int i = 0;i < n;++i)
				f[i] = -1;
			f[0] = 0;
			auto cnt = dfs(0);
			if (cnt != mp(-1,-1)) {
				cycle.pb(w[cnt.fi][cnt.se]);
				for (int i = cnt.fi;i != cnt.se;i = f[i])
					cycle.pb(w[i][f[i]]);
			} else {
				int ok = 1;
				for (int i = 0;i < m;++i)
					if (Ws[i])
						ok &= !was[i];
				if (ok)
					break;
				else {
					for (int i = 0;i < m;++i)
						if (Ws[i])
							was[i] = 0;
				}
			}
			for (auto it : cycle)
				was[it] = 1;
			vector < pii > rs;
			int shit = 0;
			for (int i = 0;i < cycle.size();++i) {
					if (Ws[cycle[i]]) {
						++shit;
						if (shit > 1)
							continue;
					}
					for (int j = 0;j < n;++j)
						p[j] = j;
					vi e;
					for (int j = 0;j < cycle.size();++j)
						if (i != j) {
							p[get(u[cycle[j]])] = get(v[cycle[j]]);
							e.pb(cycle[j]);
						}
					for (auto it : ee)
						if (get(u[it]) != get(v[it])) {
							e.pb(it);
							p[get(u[it])] = get(v[it]);
						}
					rs.pb(mp(count_common_roads(e),cycle[i]));
				}
			int mn = min_element(all(rs))->fi;
			int mx = max_element(all(rs))->fi;
			if (mn != mx) {
				for (auto it : rs)
					if (it.fi == mn)
						Ws[it.se] = 1;
			}
		} while (1);
		for (int i = 0;i < m;++i)
			if (Ws[i] || (!Ws[i] && !was[i]))
				answer.pb(i);
	} else {
		vi ee;
		for (int i = 0;i + 1 < n;++i)
			ee.pb(w[i][i + 1]);
		for (int i = 0;i + 1 < n;++i) {
			vi e1,e2,e3;
			int nxt = 0;
			while (nxt == i || nxt == i + 1)
				(++nxt) %= n;
			for (int j = 0;j < n;++j)
				if (j != i && j != i + 1 && j != nxt)
					e1.pb(w[j][(j + 1) % n]);
			e3 = e2 = e1;
			e1.pb(w[nxt][i]);
			e1.pb(w[i][i + 1]);
			e2.pb(w[i][i + 1]);
			e2.pb(w[i + 1][nxt]);
			e3.pb(w[i + 1][nxt]);
			e3.pb(w[nxt][i]);
			int cnt1 = count_common_roads(e1);
			int cnt2 = count_common_roads(e2);
			int cnt3 = count_common_roads(e3);
			if (min({cnt1,cnt2,cnt3}) != max({cnt1,cnt2,cnt3})) {
				if (cnt3 <= cnt1 && cnt3 <= cnt2)
					s[i][i + 1] = s[i + 1][i] = 1;
				else
					s[i][i + 1] = s[i + 1][i] = 0;
			} else 
				s[i][i + 1] = s[i + 1][i] = 0;
		}
		for (int i = 0;i < n;++i) {
			int deg = 0;
			vi e;
			for (int j = 0;j < n;++j)
				if (i != j)
					e.pb(w[i][j]);
			deg = count_common_roads(e);
			for (int k = 1;k <= deg;++k) {
				int t = 0;
				for (int d = 1 << 9;d;d /= 2)
					if (t + d < n) {
						vi e;
						for (int l = 0;l < n;++l)
							p[l] = l;
						for (int j = 0;j < t + d;++j)
							if (j != i)
								e.pb(w[i][j]),p[get(j)] = get(i);
						int cnt1 = 0;
						for (auto it : ee)
							if (get(u[it]) != get(v[it])) {
								cnt1 += s[u[it]][v[it]];
								p[get(u[it])] = get(v[it]);
								e.pb(it);
							}
						int cnt2 = count_common_roads(e);
						if (cnt2 - cnt1 < k)
							t += d;
					}
				s[i][t] = 1;
			}
		}
		for (int i = 0;i < n;++i)
			for (int j = 0;j < i;++j)
				if (s[i][j] == 1)
					answer.pb(w[i][j]);
	}
	return answer;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:85:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0;i < cycle.size();++i) {
                   ~~^~~~~~~~~~~~~~
simurgh.cpp:94:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int j = 0;j < cycle.size();++j)
                     ~~^~~~~~~~~~~~~~
simurgh.cpp:42:6: warning: unused variable 'called' [-Wunused-variable]
  int called = 0;
      ^~~~~~

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