#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define MAX 1010
#define MAXS 10
ll N, M;
ll sp[MAX][MAXS];
ll depth[MAX];
vector<ll> adj[MAX], tree[MAX], back[MAX], ans[MAX];
vector<ll> query;
vector<ll> U, V;
ll vis[MAX];
bool ck[MAX];
ll isroyal[MAX];
ll treeres;
ll leaf[MAX];
ll adj2[MAX][MAX];
vector<ll> leafv;
void dfs(ll x = 0, ll p = -1, ll d = 0) {
sp[x][0] = p;
depth[x] = d;
ll i;
vis[x] = 1;
for (i = 1; i < MAXS; i++) sp[x][i] = sp[sp[x][i - 1]][i - 1];
for (auto v : adj[x]) if (!vis[v]) dfs(v, x, d + 1);
}
//{a, b}={c, d}인지 체크
bool chk(ll a, ll b, ll c, ll d) {
if (a > b) swap(a, b);
if (c > d) swap(c, d);
return a == c && b == d;
}
ll getline(ll u, ll v) {
ll i;
for (i = 0; i < M; i++) if (chk(u, v, U[i], V[i])) return i;
return -1;
}
ll getline(ll i) {
return getline(U[i], V[i]);
}
ll lca(ll u, ll v) {
if (depth[u] != depth[v]) {
if (depth[u] < depth[v]) swap(u, v);
ll i;
for (i = MAXS - 1; i >= 0; i--) if (depth[sp[u][i]] >= depth[v]) u = sp[u][i];
}
if (u == v) return u;
ll i;
for (i = MAXS - 1; i >= 0; i--) if (sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
return sp[v][0];
}
ll dis(ll u, ll v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
void erase(vector<ll>& v, ll a) {
ll i;
for (i = 0; i < v.size(); i++) if (v[i] == a) break;
v.erase((v.begin() + i));
}
void getleaf(ll x = 0, ll p = -1) {
ll c = 0;
for (auto v : tree[x]) {
if (v == p) continue;
c = 1;
getleaf(v, x);
}
if (!c) leaf[x] = 1, leafv.push_back(x);
}
ll p(ll r, ll x) {
if (lca(r, x) == x) {
for (auto v : adj[x]) {
if (lca(v, r) == v && lca(x, v) == x) return v;
}
}
else return sp[x][0];
}
ll a(ll i) {
if (sp[U[i]][0] == V[i]) return U[i];
else return V[i];
}
//v is parent
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N = n, M = u.size();
ll i;
for (i = 0; i < M; i++) adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
dfs();
for (i = 0; i < M; i++) {
if (lca(u[i], v[i]) == u[i]) swap(u[i], v[i]);
if (sp[u[i]][0] == v[i]) tree[u[i]].push_back(v[i]), tree[v[i]].push_back(u[i]);
else back[u[i]].push_back(v[i]), back[v[i]].push_back(u[i]);
}
U = u, V = v;
for (i = 0; i < N; i++) {
for (auto v : tree[i]) {
if (i < v) query.push_back(getline(i, v));
}
}
treeres = count_common_roads(query);
getleaf();
bool c = true;
while (1) {
c = true;
for (i = 1; i < N; i++) {
if (leaf[i]) {
c = false;
if (back[i].empty()) {
leaf[i] = 0;
ll ccc = 1;
for (auto x : tree[sp[i][0]]) if ((x != sp[i][1]) && leaf[x]) ccc = 0;
if (ccc) leaf[sp[i][0]] = 1;
isroyal[i] = 1;
continue;
}
for (auto x : back[i]) {
if (lca(x, i) == x) {
query.push_back(getline(i, x));
map<ll, ll> mp;
for (ll j = i; (j != x); j = sp[j][0]) {
ll e = getline(j, sp[j][0]);
erase(query, e);
ll res = count_common_roads(query) - treeres;
mp[j] = res;
query.push_back(e);
}
erase(query, getline(i, x));
set<ll> st;
for (ll j = i; (j != x); j = sp[j][0]) st.insert(mp[j]);
if (st.size() == 1) {
if (*st.begin()) for (ll j = i; (j != x); j = sp[j][0]) isroyal[j] = 1;
else for (ll j = i; (j != x); j = sp[j][0]) isroyal[j] = 0;
}
else {
if (*st.begin() == -1) for (ll j = i; (j != x); j = sp[j][0]) isroyal[j] = -mp[j];
else for (ll j = i; (j != x); j = sp[j][0]) isroyal[j] = 1 - mp[j];
}
leaf[i] = 0;
ll ccc = 1;
for (auto v : tree[sp[x][0]]) if ((v != sp[x][1]) && leaf[v]) ccc = 0;
if (ccc) leaf[sp[x][0]] = 1;
break;
}
else if (leaf[x]) {
ll l = lca(i, x);
query.push_back(getline(i, x));
map<ll, ll> mp;
for (ll j = i; (j != l); j = sp[j][0]) {
ll e = getline(j, sp[j][0]);
erase(query, e);
ll res = count_common_roads(query) - treeres;
mp[j] = res;
query.push_back(e);
}
for (ll j = x; (j != l); j = sp[j][0]) {
ll e = getline(j, sp[j][0]);
erase(query, e);
ll res = count_common_roads(query) - treeres;
mp[j] = res;
query.push_back(e);
}
erase(query, getline(i, x));
set<ll> st;
for (ll j = i; (j != l); j = sp[j][0]) st.insert(mp[j]);
for (ll j = x; (j != l); j = sp[j][0]) st.insert(mp[j]);
if (st.size() == 1) {
for (ll j = i; (j != x); j = sp[j][0]) isroyal[j] = 0;
for (ll j = x; (j != l); j = sp[j][0]) isroyal[j] = 0;
}
else {
if (*st.begin() == -1) {
for (ll j = i; (j != l); j = sp[j][0]) isroyal[j] = -mp[j];
for (ll j = x; (j != l); j = sp[j][0]) isroyal[j] = -mp[j];
}
else {
for (ll j = i; (j != l); j = sp[j][0]) isroyal[j] = 1 - mp[j];
for (ll j = x; (j != l); j = sp[j][0]) isroyal[j] = 1 - mp[j];
}
}
leaf[i] = leaf[x] = 0;
ll ccc = 1;
for (auto v : tree[sp[l][0]]) if ((v != sp[l][1]) && leaf[v]) ccc = 0;
if (ccc) leaf[sp[l][0]] = 1;
break;
}
}
}
}
if (c) break;
}
vector<ll> ans;
for (i = 0; i < N; i++) {
for (auto x : adj[i]) {
if (p(i, x) == i) continue;
if (adj2[x][i]) continue;
erase(query, getline(x, p(i, x)));
ll e = getline(i, x);
query.push_back(e);
ll res = count_common_roads(query) + isroyal[a(getline(x, p(i, x)))] - treeres;
query.push_back(getline(x, p(i, x)));
erase(query, e);
adj2[i][x] = adj2[x][i] = 1;
if (res == 1) ans.push_back(e);
}
}
for (i = 1; i < N; i++) if (isroyal[i]) ans.push_back(getline(i, sp[i][0]));
return ans;
}
Compilation message
simurgh.cpp: In function 'void erase(std::vector<int>&, ll)':
simurgh.cpp:67:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (i = 0; i < v.size(); i++) if (v[i] == a) break;
| ~~^~~~~~~~~~
simurgh.cpp: In function 'll p(ll, ll)':
simurgh.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
88 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Execution timed out |
3085 ms |
332 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Execution timed out |
3085 ms |
332 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Execution timed out |
3085 ms |
332 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
460 KB |
correct |
| 3 |
Execution timed out |
3087 ms |
4012 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Execution timed out |
3085 ms |
332 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
