Submission #50924

#	Time	Username	Problem	Language	Result	Execution time	Memory
50924		Mamnoon_Siam	Simurgh (IOI17_simurgh)	C++17	30 / 100	3056 ms	14684 KiB

simurgh

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

#define debug(s) cerr<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

struct edge {
	int v, id;
	edge() {v = 0, id = 0;};
	edge(int v, int id) {
		this -> v = v;
		this -> id = id;
	}
	bool operator < (const edge &tmp) const {
		return ii(v, id) < ii(tmp.v, tmp.id);
	}
};

const int maxn = 505;

int n, m;
set<edge> g[505];
vector<ii> edges;
int pid[maxn];
bool vis[maxn], ok[maxn * maxn];
int edge_id[maxn][maxn];
bool flag = 0;
int head, tail;
bool col[maxn][maxn];
set<int> rem;

int par[maxn], sz[maxn];
int find(int u) {
	return par[u] == u ? u : par[u] = find(par[u]);
}
void unite(int u, int v) {
	col[u][v] = col[v][u] = 1;

	u = find(u), v = find(v);
	if(u == v) return ;
	if(sz[u] > sz[v]) swap(u, v);
	par[u] = v, sz[v] += sz[u];
}

void delete_edge(int id) {
	int u = edges[id].first, v = edges[id].second;
	g[u].erase(edge(v, id));
	g[v].erase(edge(u, id));
	ok[id] = 0;
	rem.erase(id);
}

void dfs(int u, int pe) {
	vis[u] = 1;
	pid[u] = pe;
	for(edge v : g[u]) {
		if(v.id == pe) continue;
		if(!vis[v.v]) {
			dfs(v.v, v.id);
		} else if(!flag) {
			flag = 1;
			tail = u, head = v.v;
		}
	}
}

void round() {
	MEMSET(vis, 0);
	flag = 0;

	// do dfs, head, tail
	dfs(0, -1);

	// extract tree edges
	vector<int> tree_edges;
	for(int i = 1; i < n; i++) {
		tree_edges.push_back(pid[i]);
	}

	// extract all edges which are cycle and tree edges
	vector<int> on_path;
	int temp_tail = tail;
	while(true) {
		on_path.push_back(pid[tail]);
		int u = edges[pid[tail]].first, v = edges[pid[tail]].second;
		tail ^= u ^ v;
		if(tail == head) break;
	} tail = temp_tail;

	// the back edge
	int bid = edge_id[head][tail];

	// extract differences
	vector<int> ask(on_path.size());
	int prev = count_common_roads(tree_edges);
	for(int i = 0; i < on_path.size(); i++) {
		vector<int> temp = tree_edges;
		temp.erase(find(all(temp), on_path[i]));
		temp.push_back(bid);
		int now = count_common_roads(temp);
		ask[i] = now - prev;
	}

	// identify the colours
	int allz = 1, mode_val;
	for(int i = 0; i < on_path.size(); i++) {
		if(ask[i] != 0) allz = 0, mode_val = ask[i];
	}
	if(allz) {
		for(int b : on_path) {
			delete_edge(b);
		} delete_edge(bid);
		// all are white
	} else {
		if(mode_val == -1) {
			delete_edge(bid);
			// which on_path are -1, they are black
			for(int i = 0; i < on_path.size(); i++) {
				int u = edges[on_path[i]].first, v = edges[on_path[i]].second;
				if(ask[i] == -1) {
					unite(u, v);
				}
			}
		} else {
			for(int i = 0; i < on_path.size(); i++) {
				if(ask[i] == +1) {
					delete_edge(on_path[i]);
				} // those who are +1 are white
			} // bid is black
			int u = edges[bid].first, v = edges[bid].second;
			unite(u, v);
		}
	}
}

int live_edges() {
	int ret = 0;
	for(int i = 0; i < edges.size(); i++) {
		ret += ok[i];
	} return ret;
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	n = N;
	for(int i = 0; i < U.size(); i++) {
		g[U[i]].insert(edge(V[i], i));
		g[V[i]].insert(edge(U[i], i));
		edges.push_back(ii(U[i], V[i]));
		edge_id[U[i]][V[i]] = i;
		edge_id[V[i]][U[i]] = i;
	}
	for(int i = 0; i < n; i++) {
		par[i] = i, sz[i] = 1;
	}
	for(int i = 0; i < U.size(); i++)
		ok[i] = 1, rem.insert(i);

	while(live_edges() >= n) {
		round();
		for(int i : rem) {
			int u = edges[i].first, v = edges[i].second;
			if(ok[i] and !col[u][v] and find(u) == find(v)) {
				delete_edge(i);
			}
		}
	}

	vector<int> ret;
	for(int i = 0; i < edges.size(); i++) {
		if(ok[i]) ret.push_back(i);
	} return ret;
}

Compilation message (stderr)

simurgh.cpp: In function 'int myrand(int, int)':
simurgh.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
simurgh.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
simurgh.cpp: In function 'void round()':
simurgh.cpp:120:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < on_path.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~
simurgh.cpp:130:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < on_path.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~
simurgh.cpp:142:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < on_path.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~
simurgh.cpp:149:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < on_path.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~
simurgh.cpp: In function 'int live_edges()':
simurgh.cpp:162:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:169:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < U.size(); i++) {
                 ~~^~~~~~~~~~
simurgh.cpp:179:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < U.size(); i++)
                 ~~^~~~~~~~~~
simurgh.cpp:193:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~

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