Submission #73350

#	Time	Username	Problem	Language	Result	Execution time	Memory
73350		Navick	Simurgh (IOI17_simurgh)	C++17	30 / 100	170 ms	3436 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int maxN = 510, maxE = maxN * maxN / 2;

int cmp[maxN], from[maxE], to[maxE], r, n;
bool mark[maxN], good[maxE];
bool flag[maxN];

vector <int> adj[maxN], ans, tree;
vector <int> edge[maxN];

void DFS(int v, int id)
{
	mark[v] = true;
	cmp[v] = id;

	for (auto i : adj[v])
	{
		int u = from[i] + to[i] - v;
		if(u == r || mark[u]) continue ;
		tree.pb(i);
		DFS(u, id);
	}
}

void solve(int v)
{
	memset(mark, 0, sizeof mark);
	r = v; 
	int sz = 0;
	tree.clear();
	
	for (int i=0; i<n; i++)
	{
		if(i == v || mark[i]) continue ;
		DFS(i, sz);
		sz ++;
	}
	
	memset(flag, 0, sizeof flag);

	for (auto i : adj[v])
	{
		int u = from[i] + to[i] - v;
		if(good[i] && !flag[cmp[u]]) edge[cmp[u]].pb(i), flag[cmp[u]] = true;
		else if(!good[i]) edge[cmp[u]].pb(i);
	}


	//cout << " FIRST " << v << " --> " << sz << endl;
	//for (auto x : tree) cout << x << ' '; cout << endl;

	for (int i=0; i<sz; i++)
		tree.pb(edge[i][0]);
	
	int last_ans = -1;
	for (int i=0; i<sz; i++)
	{
		int td = edge[i].size(), mx = -1;
		vector <int> tmp;

		if(last_ans != -1) tmp.pb(last_ans), mx = last_ans;
		else
		{
			int r = count_common_roads(tree);
			tmp.pb(r);
			mx = r;
			last_ans = r;
		}

		for (int j=1; j<td; j++)
		{
			tree[n - sz - 1 + i] = edge[i][j];
			int r = count_common_roads(tree);
			tmp.pb(r);
			mx = max(mx, r);
			last_ans = r;
		}
		for (int j=0; j<td; j++) {
			if(tmp[j] == mx) ans.pb(edge[i][j]), good[edge[i][j]] = true;
		}
	}

	//cout << ans.size() << endl;

	for (int i=0; i<sz; i++) edge[i].clear();

}

std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
	int m = u.size(); n = _n;
	for (int i=0; i<m; i++)
	{
		from[i] = u[i];
		to[i] = v[i];
		adj[u[i]].pb(i);
		adj[v[i]].pb(i);
	}

	for (int i=0; i<n; i++) solve(i);

	sort(ans.begin(), ans.end());
	ans.resize(unique(ans.begin(), ans.end()) - ans.begin());
	
	return ans;
}

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