Submission #790999

#	Time	Username	Problem	Language	Result	Execution time	Memory
790999		NothingXD	Simurgh (IOI17_simurgh)	C++17	0 / 100	557 ms	1048576 KiB

simurgh

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

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 500 + 10;

int n, m, h[maxn], par[maxn], dsu[maxn*maxn], edge[maxn*maxn][2];
vector<int> g[maxn], t[maxn];
vector<int> badedge;
vector<int> ans;
bool vis[maxn], mark[maxn];

int getpar(int v){
	//debug(v, dsu[v]);
	return (dsu[v] == -1? v: dsu[v] = getpar(dsu[v]));
}

void merge(int u, int v){
	//debug("merge", u, v);
	if ((u = getpar(u)) == (v = getpar(v))) return;
	//debug(u, v);
	if (u < v) swap(u, v);
	dsu[v] = u;
}

void predfs(int v){
	vis[v] = true;
	for (auto x: g[v]){
		int u = edge[x][0] ^ edge[x][1] ^ v;
		if (!vis[u]){
			t[v].push_back(x);
			t[u].push_back(x);
			ans.push_back(x);
		//	debug("add", x);
			h[u] = h[v] + 1;
			predfs(u);
		}
		else if (h[u] > h[v]){
			badedge.push_back(x);
		}
	}
}

void dfs(int v, int p = -1){
	//debug(v, p, h[v]);
	par[v] = p;
	for (auto x: t[v]){
		//debug(x);
		if (x == p) continue;
		int u = edge[x][0] ^ edge[x][1] ^ v;
		//debug(edge[x][0], edge[x][1], u);
		h[u] = h[v] + 1;
		dfs(u, x);		
	}
}

std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
	memset(dsu, -1, sizeof dsu);
	n = _n;
	m = u.size();
	for (int i = 0; i < m; i++){
		edge[i][0] = u[i];
		edge[i][1] = v[i];
		g[v[i]].push_back(i);
		g[u[i]].push_back(i);
	}
	predfs(0);
	//debug(ans.size(), badedge.size());
	int res = count_common_roads(ans);
	//debug(res);
	//assert(ans.size() == n-1);
	for (auto x: badedge){
		//debug(x);
		assert(getpar(m) != getpar(m+1));
		dfs(0);
		int v = edge[x][0], u = edge[x][1];
		if (h[v] < h[u]) swap(u, v);
		bool flg = false;
	//	debug(v, u);
		while(v != u && getpar(x) < m){
			int e = par[v];
	//		debug(e, x);
			if (getpar(e) != getpar(x)){
	//			debug(0);
				ans.erase(find(all(ans), e));
				ans.push_back(x);
				int tmp = count_common_roads(ans);
				ans.pop_back();
				ans.push_back(e);
				if (tmp == res){
	//				debug(1);
					merge(e, x);
				}
				else if (tmp < res){
	//				debug(2);
					merge(e, m);
					merge(x, m+1);
				}
				else{
	//				debug(3);
	//				debug("readd", e, x);
					res = tmp;
					merge(e, m+1);
					ans.pop_back();
					t[edge[e][0]].erase(find(all(t[edge[e][0]]), e));
					t[edge[e][1]].erase(find(all(t[edge[e][1]]), e));
					merge(x, m);
				}
			}
			v = edge[e][0] ^ edge[e][1] ^ v;
		}
	//	debug(x, getpar(x));
		if (getpar(x) == m){
			ans.push_back(x);
			t[edge[x][0]].push_back(x);
			t[edge[x][1]].push_back(x);
		}
		else{
			merge(x, m+1);
		}
	}
	//for (auto x: ans) debug(x);
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:99:8: warning: unused variable 'flg' [-Wunused-variable]
   99 |   bool flg = false;
      |        ^~~

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