//#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];
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;
}
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]);
tail = tail ^ edges[pid[tail]].first ^ edges[pid[tail]].second;
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++) {
if(ask[i] == -1) {
unite(edges[on_path[i]].first, edges[on_path[i]].second);
}
}
} 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
unite(edges[bid].first, edges[bid].second);
}
}
}
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;
while(live_edges() >= n) {
for(int i = 0; i < edges.size(); i++) {
if(ok[i] and !col[edges[i].first][edges[i].second] and find(edges[i].first) == find(edges[i].second)) {
delete_edge(i);
}
}
round();
}
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:117:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < on_path.size(); i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:127:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < on_path.size(); i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:139:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < on_path.size(); i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:145: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:157: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:164:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < U.size(); i++) {
~~^~~~~~~~~~
simurgh.cpp:174:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < U.size(); i++)
~~^~~~~~~~~~
simurgh.cpp:178:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < edges.size(); i++) {
~~^~~~~~~~~~~~~~
simurgh.cpp:187: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 |
Incorrect |
5 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
560 KB |
correct |
| 3 |
Execution timed out |
3049 ms |
10876 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
