Submission #58822

#	Time	Username	Problem	Language	Result	Execution time	Memory
58822		reality	Simurgh (IOI17_simurgh)	C++17	100 / 100	1379 ms	30164 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 w[N][N];
int s[N][N];
int f[N];
vi g[N];
int p[N];
int get(int k) {
	return k == p[k] ? k : p[k] = get(p[k]);
} 
int was[N * N];
vi E;
vi find_roads(int n,vi u,vi v) {
	if (n == 2) {
		return vi{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;
	vi answer;	
	vi ee;
	for (int l = 0;l < n;++l)
		p[l] = l;
	for (int i = 0;i < m;++i)
		if (get(u[i]) != get(v[i])) {
			g[u[i]].pb(v[i]);
			g[v[i]].pb(u[i]);
			ee.pb(i);
			was[i] = 1;
			p[get(u[i])] = get(v[i]);
		}
	for (int i = 0;i < m;++i) 
		if (!was[i]) {
			queue < int > Q;
			Q.push(u[i]);
			for (int j = 0;j < n;++j)
				f[j] = -1;
			f[u[i]] = u[i];
			while (!Q.empty() && f[v[i]] == -1) {
				int node = Q.front();
				Q.pop();
				for (auto it : g[node])
					if (f[it] == -1)
						f[it] = node,Q.push(it);
			}
			vi E;
			for (int j = v[i];j != u[i];j = f[j])
				E.pb(w[j][f[j]]);
			int ok = 0;
			vi ed;
			for (auto it : ee)
				ed.pb(it);
			ed.pb(i);
			for (auto it : E)
				ok |= was[it] == 1;
			if (ok) {
				E.pb(i);
				int index = -1;
				for (int i = 0;i < E.size();++i)
					if (was[E[i]] == 3)
						index = E[i];
				int ind = -1;
				for (int i = 0;i < E.size();++i)
					if (was[E[i]] == 2)
						ind = E[i];
				vector < pii > rs;
				if (index != -1) {
					vi e;
					for (auto it : ed)
						if (it != index)
							e.pb(it);
					rs.pb(mp(count_common_roads(e),index));
				}
				if (ind != -1) {
					vi e;
					for (auto it : ed)
						if (it != ind)
							e.pb(it);
					rs.pb(mp(count_common_roads(e),ind));
				}
				for (auto a : E) 
					if (was[a] <= 1) {
						vi e;
						for (auto it : ed)
							if (it != a)
								e.pb(it);
						rs.pb(mp(count_common_roads(e),a));
					}
				int mn = min_element(all(rs))->fi;
				int mx = max_element(all(rs))->fi;
				if (mn == mx) {
					for (auto it : rs)
						if (was[it.se] == 1)
							was[it.se] = 3;
				} else {
					for (auto it : rs)
						if (was[it.se] == 1 && it.fi == mn)
							was[it.se] = 2;
						else
						if (was[it.se] == 1 && it.fi != mn)
							was[it.se] = 3;
				}
			}
		}
	for (auto it : ee)
		s[u[it]][v[it]] = s[v[it]][u[it]] = (was[it] != 3) ? 1 : 0;
	for (int i = 0;i < n;++i) {
		int deg = 0;
		vi e;
		int cnt1 = 0;
		for (int l = 0;l < n;++l)
			p[l] = l;
		for (int j = 0;j < n;++j)
			if (i != j && w[i][j] != -1)
				e.pb(w[i][j]),cnt1 += s[i][j] == 1,p[get(i)] = get(j);
		for (auto it : ee)
			if (get(u[it]) != get(v[it])) {
				p[get(u[it])] = get(v[it]);
				cnt1 += s[u[it]][v[it]] == 1;
				e.pb(it);
			}
		int cnt2 = count_common_roads(e);
		deg = cnt2 - cnt1;
		vi mk;
		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;
					int cnt1 = 0;
					for (int j = 0;j < t + d;++j)
						if (j != i && w[i][j] != -1)
							e.pb(w[i][j]),cnt1 += s[i][j] == 1,p[get(j)] = get(i);
					for (auto it : ee)
						if (get(u[it]) != get(v[it])) {
							cnt1 += s[u[it]][v[it]] == 1;
							p[get(u[it])] = get(v[it]);
							e.pb(it);
						}
					int cnt2 = count_common_roads(e);
					if (cnt2 - cnt1 < k)
						t += d;
				}
			mk.pb(t);
		}
		for (auto it : mk)
			s[it][i] = s[i][it] = 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:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i < E.size();++i)
                    ~~^~~~~~~~~~
simurgh.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i < E.size();++i)
                    ~~^~~~~~~~~~

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