#include "simurgh.h"
#include <stdlib.h>
#include <string.h>
using namespace std;
const int N = 500;
typedef vector<int> vi;
int ds[N], n;
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
int join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
int ii[M], jj[M];
int *eh[N], eo[N];
void append(int i, int h) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
eh[i][o] = h;
}
char cc[M], marked[M];
int dfs(int p, int i, int t) {
int o;
if (i == t)
return 1;
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
if (j != p && dfs(i, j, t)) {
marked[h] = 1;
return 1;
}
}
return 0;
}
vi hh, hh_;
int k_;
int count(int i, int m) {
int g, m_, k;
memset(ds, -1, n * sizeof *ds);
m_ = 0;
for (g = 0; g < m; g++) {
int h = eh[i][g];
join(ii[h], jj[h]);
hh_[m_++] = h;
}
k = 0;
for (g = 0; g < n - 1; g++)
if (join(ii[hh[g]], jj[hh[g]]))
hh_[m_++] = hh[g];
else if (cc[hh[g]])
k++;
return count_common_roads(hh_) - k_ + k;
}
void solve(int i, int l, int r, int a, int b) {
int m, c;
if (a == b)
return;
if (r - l == 1) {
cc[eh[i][l]] = 1;
return;
}
m = (l + r) / 2;
c = count(i, m);
solve(i, l, m, a, c), solve(i, m, r, c, b);
}
vi find_roads(int n_, vi ii_, vi jj_) {
int m = ii_.size(), m_, g, h, i;
n = n_;
for (h = 0; h < m; h++)
ii[h] = ii_[h], jj[h] = jj_[h];
hh.resize(n - 1), hh_.resize(n - 1);
memset(ds, -1, n * sizeof *ds);
for (i = 0; i < n; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
m_ = 0;
for (h = 0; h < m; h++)
if (join(ii[h], jj[h])) {
hh[m_++] = h, cc[h] = -1;
append(ii[h], h), append(jj[h], h);
} else
cc[h] = -2;
k_ = count_common_roads(hh);
for (h = 0; h < m; h++) {
int upd, c, tmp, k;
if (cc[h] != -2)
continue;
for (g = 0; g < n - 1; g++)
marked[hh[g]] = 0;
dfs(-1, ii[h], jj[h]);
upd = 0;
for (g = 0; g < n - 1; g++)
if (marked[hh[g]] && cc[hh[g]] == -1) {
upd = 1;
break;
}
if (!upd)
continue;
c = -1;
for (g = 0; g < n - 1; g++)
if (marked[hh[g]] && cc[hh[g]] != -1) {
tmp = hh[g], hh[g] = h, k = count_common_roads(hh), hh[g] = tmp;
c = cc[hh[g]] ^ (k == k_ ? 0 : 1);
break;
}
for (g = 0; g < n - 1; g++)
if (marked[hh[g]] && cc[hh[g]] == -1) {
tmp = hh[g], hh[g] = h, k = count_common_roads(hh), hh[g] = tmp;
if (k == k_ + 1)
c = 1;
else if (k == k_ - 1)
c = 0;
if (c != -1)
cc[hh[g]] = c ^ (k == k_ ? 0 : 1);
}
if (c == -1)
c = 0;
for (g = 0; g < n - 1; g++)
if (marked[hh[g]] && cc[hh[g]] == -1)
cc[hh[g]] = c;
}
for (h = 0; h < m; h++)
if (cc[h] == -1)
cc[h] = 1;
else if (cc[h] == -2)
append(ii[h], h), append(jj[h], h);
for (i = 0; i < n; i++) {
int o, o_;
for (o = 0, o_ = 0; o < eo[i]; o++) {
h = eh[i][o];
if (cc[h] == -2)
cc[h] = 0, eh[i][o_++] = h;
}
eo[i] = o_;
solve(i, 0, eo[i], 0, count(i, eo[i]));
}
m_ = 0;
for (h = 0; h < m; h++)
if (cc[h] == 1)
hh[m_++] = h;
return hh;
}
Compilation message
simurgh.cpp:32:8: error: 'M' was not declared in this scope
32 | int ii[M], jj[M];
| ^
simurgh.cpp:32:15: error: 'M' was not declared in this scope
32 | int ii[M], jj[M];
| ^
simurgh.cpp: In function 'void append(int, int)':
simurgh.cpp:38:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
38 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
simurgh.cpp: At global scope:
simurgh.cpp:43:9: error: 'M' was not declared in this scope
43 | char cc[M], marked[M];
| ^
simurgh.cpp:43:20: error: 'M' was not declared in this scope
43 | char cc[M], marked[M];
| ^
simurgh.cpp: In function 'int dfs(int, int, int)':
simurgh.cpp:51:29: error: 'ii' was not declared in this scope; did you mean 'i'?
51 | int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
| ^~
| i
simurgh.cpp:51:37: error: 'jj' was not declared in this scope; did you mean 'j'?
51 | int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
| ^~
| j
simurgh.cpp:54:4: error: 'marked' was not declared in this scope
54 | marked[h] = 1;
| ^~~~~~
simurgh.cpp: In function 'int count(int, int)':
simurgh.cpp:72:8: error: 'ii' was not declared in this scope; did you mean 'i'?
72 | join(ii[h], jj[h]);
| ^~
| i
simurgh.cpp:72:15: error: 'jj' was not declared in this scope
72 | join(ii[h], jj[h]);
| ^~
simurgh.cpp:77:12: error: 'ii' was not declared in this scope; did you mean 'i'?
77 | if (join(ii[hh[g]], jj[hh[g]]))
| ^~
| i
simurgh.cpp:77:23: error: 'jj' was not declared in this scope
77 | if (join(ii[hh[g]], jj[hh[g]]))
| ^~
simurgh.cpp:79:12: error: 'cc' was not declared in this scope
79 | else if (cc[hh[g]])
| ^~
simurgh.cpp: In function 'void solve(int, int, int, int, int)':
simurgh.cpp:90:3: error: 'cc' was not declared in this scope; did you mean 'c'?
90 | cc[eh[i][l]] = 1;
| ^~
| c
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:103:3: error: 'ii' was not declared in this scope; did you mean 'i'?
103 | ii[h] = ii_[h], jj[h] = jj_[h];
| ^~
| i
simurgh.cpp:103:19: error: 'jj' was not declared in this scope; did you mean 'jj_'?
103 | ii[h] = ii_[h], jj[h] = jj_[h];
| ^~
| jj_
simurgh.cpp:110:12: error: 'ii' was not declared in this scope; did you mean 'i'?
110 | if (join(ii[h], jj[h])) {
| ^~
| i
simurgh.cpp:110:19: error: 'jj' was not declared in this scope; did you mean 'jj_'?
110 | if (join(ii[h], jj[h])) {
| ^~
| jj_
simurgh.cpp:111:18: error: 'cc' was not declared in this scope
111 | hh[m_++] = h, cc[h] = -1;
| ^~
simurgh.cpp:114:4: error: 'cc' was not declared in this scope
114 | cc[h] = -2;
| ^~
simurgh.cpp:119:7: error: 'cc' was not declared in this scope; did you mean 'c'?
119 | if (cc[h] != -2)
| ^~
| c
simurgh.cpp:122:4: error: 'marked' was not declared in this scope
122 | marked[hh[g]] = 0;
| ^~~~~~
simurgh.cpp:123:11: error: 'ii' was not declared in this scope; did you mean 'i'?
123 | dfs(-1, ii[h], jj[h]);
| ^~
| i
simurgh.cpp:123:18: error: 'jj' was not declared in this scope; did you mean 'jj_'?
123 | dfs(-1, ii[h], jj[h]);
| ^~
| jj_
simurgh.cpp:126:8: error: 'marked' was not declared in this scope
126 | if (marked[hh[g]] && cc[hh[g]] == -1) {
| ^~~~~~
simurgh.cpp:126:25: error: 'cc' was not declared in this scope; did you mean 'c'?
126 | if (marked[hh[g]] && cc[hh[g]] == -1) {
| ^~
| c
simurgh.cpp:134:8: error: 'marked' was not declared in this scope
134 | if (marked[hh[g]] && cc[hh[g]] != -1) {
| ^~~~~~
simurgh.cpp:134:25: error: 'cc' was not declared in this scope; did you mean 'c'?
134 | if (marked[hh[g]] && cc[hh[g]] != -1) {
| ^~
| c
simurgh.cpp:140:8: error: 'marked' was not declared in this scope
140 | if (marked[hh[g]] && cc[hh[g]] == -1) {
| ^~~~~~
simurgh.cpp:140:25: error: 'cc' was not declared in this scope; did you mean 'c'?
140 | if (marked[hh[g]] && cc[hh[g]] == -1) {
| ^~
| c
simurgh.cpp:152:8: error: 'marked' was not declared in this scope
152 | if (marked[hh[g]] && cc[hh[g]] == -1)
| ^~~~~~
simurgh.cpp:152:25: error: 'cc' was not declared in this scope; did you mean 'c'?
152 | if (marked[hh[g]] && cc[hh[g]] == -1)
| ^~
| c
simurgh.cpp:156:7: error: 'cc' was not declared in this scope
156 | if (cc[h] == -1)
| ^~
simurgh.cpp:159:11: error: 'ii' was not declared in this scope; did you mean 'i'?
159 | append(ii[h], h), append(jj[h], h);
| ^~
| i
simurgh.cpp:159:29: error: 'jj' was not declared in this scope; did you mean 'jj_'?
159 | append(ii[h], h), append(jj[h], h);
| ^~
| jj_
simurgh.cpp:165:8: error: 'cc' was not declared in this scope
165 | if (cc[h] == -2)
| ^~
simurgh.cpp:173:7: error: 'cc' was not declared in this scope
173 | if (cc[h] == 1)
| ^~
