#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);
}
};
map<vector<int>, int> mp;
int query(vector<int> vec) {
sort(all(vec));
auto it = mp.find(vec);
if(it == mp.end()) return it -> second = count_common_roads(vec);
return it -> second;
}
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 = query(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 = query(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 = query(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 = query(temp);
ask[i] = now - prev;
}
} else {
int prev = query(tree_edges);
{
vector<int> tempo = tree_edges;
tempo.erase(find(all(tempo), on_path[id]));
tempo.push_back(bid);
Col[bid] = query(tempo) - 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 = query(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 = query(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:133:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < on_path.size(); i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:147:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < on_path.size(); i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:152:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < on_path.size(); i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:167:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < on_path.size(); i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:180:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < on_path.size(); i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:199:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < on_path.size(); i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:211:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < on_path.size(); i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:218: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:231: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:238:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < U.size(); i++) {
~~^~~~~~~~~~
simurgh.cpp:248:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < U.size(); i++)
~~^~~~~~~~~~
simurgh.cpp:262:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < edges.size(); i++) {
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
668 KB |
correct |
| 2 |
Runtime error |
3 ms |
708 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
