oj.uz

Submission #51003

# Submission time Handle Problem Language Result Execution time Memory
51003 2018-06-15T14:38:01 Z Mamnoon_Siam Simurgh (IOI17_simurgh) C++17
30 / 100
 1085 ms 14952 KB 
#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];
int mx;
int head, tail;
bool col[maxn][maxn], Col[maxn * maxn];
int lvl[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;
	Col[edge_id[u][v]] = 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, int l) {
	lvl[u] = l;
	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, l+1);
		} else if(mx < lvl[u] - lvl[v.v]) {
			mx = lvl[u] - lvl[v.v];
			tail = u, head = v.v;
		}
	}
}

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

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

	// 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];

	vector<int> ask(on_path.size());

	if(Col[bid]) {
		int prev = count_common_roads(tree_edges);
		for(int i = 0; i < on_path.size(); i++) {
			int now;
			if(Col[on_path[i]]) {
				now = prev;
			} else {
				vector<int> temp = tree_edges;
				temp.erase(find(all(temp), on_path[i]));
				temp.push_back(bid);
				now = count_common_roads(temp);
			}
			ask[i] = now - prev;
		}
	} else {
		int id = -1;
		for(int i = 0; i < on_path.size(); i++) {
			if(Col[on_path[i]]) id = i;
		}
		if(id == -1) {
			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;
			}
		} else {
			int prev = count_common_roads(tree_edges);
			{
				vector<int> temp = tree_edges;
				temp.erase(find(all(temp), on_path[id]));
				temp.push_back(bid);
				Col[bid] = count_common_roads(temp) - prev;
				if(Col[bid] == 0) { // bid is black
					for(int i = 0; i < on_path.size(); i++) {
						int now;
						if(Col[on_path[i]]) {
							now = prev;
						} else {
							vector<int> temp = tree_edges;
							temp.erase(find(all(temp), on_path[i]));
							temp.push_back(bid);
							now = count_common_roads(temp);
						}
						ask[i] = now - prev;
					}
				} else { // bid is white
					for(int i = 0; i < on_path.size(); i++) {
						int now;
						if(Col[on_path[i]]) {
							now = prev - 1;
						} else {
							vector<int> temp = tree_edges;
							temp.erase(find(all(temp), on_path[i]));
							temp.push_back(bid);
							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

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:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < on_path.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~
simurgh.cpp:138:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < on_path.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~
simurgh.cpp:143:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < on_path.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~
simurgh.cpp:158:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i < on_path.size(); i++) {
                     ~~^~~~~~~~~~~~~~~~
simurgh.cpp:171:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i < on_path.size(); i++) {
                     ~~^~~~~~~~~~~~~~~~
simurgh.cpp:190:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < on_path.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~
simurgh.cpp:202:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < on_path.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~
simurgh.cpp:209: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:222: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:229:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < U.size(); i++) {
                 ~~^~~~~~~~~~
simurgh.cpp:239:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < U.size(); i++)
                 ~~^~~~~~~~~~
simurgh.cpp:253:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < edges.size(); i++) {
                 ~~^~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 488 KB correct
3 Correct 3 ms 564 KB correct
4 Correct 2 ms 564 KB correct
5 Correct 2 ms 564 KB correct
6 Correct 2 ms 596 KB correct
7 Correct 2 ms 596 KB correct
8 Correct 3 ms 596 KB correct
9 Correct 2 ms 600 KB correct
10 Correct 3 ms 600 KB correct
11 Correct 2 ms 600 KB correct
12 Correct 2 ms 624 KB correct
13 Correct 2 ms 624 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 488 KB correct
3 Correct 3 ms 564 KB correct
4 Correct 2 ms 564 KB correct
5 Correct 2 ms 564 KB correct
6 Correct 2 ms 596 KB correct
7 Correct 2 ms 596 KB correct
8 Correct 3 ms 596 KB correct
9 Correct 2 ms 600 KB correct
10 Correct 3 ms 600 KB correct
11 Correct 2 ms 600 KB correct
12 Correct 2 ms 624 KB correct
13 Correct 2 ms 624 KB correct
14 Correct 19 ms 968 KB correct
15 Correct 27 ms 988 KB correct
16 Correct 41 ms 988 KB correct
17 Correct 14 ms 988 KB correct
18 Correct 4 ms 988 KB correct
19 Correct 16 ms 988 KB correct
20 Correct 9 ms 988 KB correct
21 Correct 14 ms 988 KB correct
22 Correct 11 ms 988 KB correct
23 Correct 9 ms 988 KB correct
24 Correct 7 ms 988 KB correct
25 Correct 3 ms 988 KB correct
26 Correct 6 ms 988 KB correct
27 Correct 9 ms 1008 KB correct
28 Correct 5 ms 1008 KB correct
29 Correct 2 ms 1008 KB correct
30 Correct 7 ms 1008 KB correct
31 Correct 9 ms 1008 KB correct
32 Correct 7 ms 1008 KB correct
33 Correct 8 ms 1008 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 488 KB correct
3 Correct 3 ms 564 KB correct
4 Correct 2 ms 564 KB correct
5 Correct 2 ms 564 KB correct
6 Correct 2 ms 596 KB correct
7 Correct 2 ms 596 KB correct
8 Correct 3 ms 596 KB correct
9 Correct 2 ms 600 KB correct
10 Correct 3 ms 600 KB correct
11 Correct 2 ms 600 KB correct
12 Correct 2 ms 624 KB correct
13 Correct 2 ms 624 KB correct
14 Correct 19 ms 968 KB correct
15 Correct 27 ms 988 KB correct
16 Correct 41 ms 988 KB correct
17 Correct 14 ms 988 KB correct
18 Correct 4 ms 988 KB correct
19 Correct 16 ms 988 KB correct
20 Correct 9 ms 988 KB correct
21 Correct 14 ms 988 KB correct
22 Correct 11 ms 988 KB correct
23 Correct 9 ms 988 KB correct
24 Correct 7 ms 988 KB correct
25 Correct 3 ms 988 KB correct
26 Correct 6 ms 988 KB correct
27 Correct 9 ms 1008 KB correct
28 Correct 5 ms 1008 KB correct
29 Correct 2 ms 1008 KB correct
30 Correct 7 ms 1008 KB correct
31 Correct 9 ms 1008 KB correct
32 Correct 7 ms 1008 KB correct
33 Correct 8 ms 1008 KB correct
34 Incorrect 1070 ms 6080 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6080 KB correct
2 Correct 2 ms 6080 KB correct
3 Incorrect 1085 ms 14952 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 488 KB correct
3 Correct 3 ms 564 KB correct
4 Correct 2 ms 564 KB correct
5 Correct 2 ms 564 KB correct
6 Correct 2 ms 596 KB correct
7 Correct 2 ms 596 KB correct
8 Correct 3 ms 596 KB correct
9 Correct 2 ms 600 KB correct
10 Correct 3 ms 600 KB correct
11 Correct 2 ms 600 KB correct
12 Correct 2 ms 624 KB correct
13 Correct 2 ms 624 KB correct
14 Correct 19 ms 968 KB correct
15 Correct 27 ms 988 KB correct
16 Correct 41 ms 988 KB correct
17 Correct 14 ms 988 KB correct
18 Correct 4 ms 988 KB correct
19 Correct 16 ms 988 KB correct
20 Correct 9 ms 988 KB correct
21 Correct 14 ms 988 KB correct
22 Correct 11 ms 988 KB correct
23 Correct 9 ms 988 KB correct
24 Correct 7 ms 988 KB correct
25 Correct 3 ms 988 KB correct
26 Correct 6 ms 988 KB correct
27 Correct 9 ms 1008 KB correct
28 Correct 5 ms 1008 KB correct
29 Correct 2 ms 1008 KB correct
30 Correct 7 ms 1008 KB correct
31 Correct 9 ms 1008 KB correct
32 Correct 7 ms 1008 KB correct
33 Correct 8 ms 1008 KB correct
34 Incorrect 1070 ms 6080 KB WA in grader: NO
35 Halted 0 ms 0 KB -