// I hate this
#include "simurgh.h"
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
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;
assert(0);
}
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));
}
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) {
ll cnt = 0;
N = n, M = u.size();
if (M == N - 1) {
ll i;
vector<ll> v;
for (i = 0; i < M; i++) v.push_back(i);
return v;
}
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));
}
}
cnt++;
assert(cnt <= 29998);
treeres = count_common_roads(query);
ll k, m;
for (k = 0; k < N; k++) isroyal[k] = -1;
for (k = 0; k < N; k++) {
for (m = 0; m < back[k].size(); m++) {
ll v1 = k, v2 = back[k][m];
ll l = lca(v1, v2);
ll x = -1;
for (i = v1; i != l; i = sp[i][0]) {
if (isroyal[i] != -1) {
x = i;
break;
}
}
for (i = v2; i != l; i = sp[i][0]) {
if (isroyal[i] != -1) {
x = i;
break;
}
}
if (x != -1) {
query.push_back(getline(v1, v2));
erase(query, getline(x, sp[x][0]));
cnt++;
assert(cnt <= 29998);
ll r0 = treeres - count_common_roads(query) - isroyal[x];
query.push_back(getline(x, sp[x][0]));
for (i = v1; i != l; i = sp[i][0]) {
if (isroyal[i] != -1) continue;
erase(query, getline(i, sp[i][0]));
cnt++;
assert(cnt <= 29998);
ll res = treeres - count_common_roads(query);
if (res != r0) isroyal[i] = 1;
else isroyal[i] = 0;
query.push_back(getline(i, sp[i][0]));
}
for (i = v2; i != l; i = sp[i][0]) {
if (isroyal[i] != -1) continue;
erase(query, getline(i, sp[i][0]));
cnt++;
assert(cnt <= 29998);
ll res = treeres - count_common_roads(query);
if (res != r0) isroyal[i] = 1;
else isroyal[i] = 0;
query.push_back(getline(i, sp[i][0]));
}
erase(query, getline(v1, v2));
}
else {
query.push_back(getline(v1, v2));
map<ll, ll> mp;
for (ll j = v1; (j != l); j = sp[j][0]) {
ll e = getline(j, sp[j][0]);
erase(query, e);
cnt++;
assert(cnt <= 29998);
ll res = count_common_roads(query) - treeres;
mp[j] = res;
query.push_back(e);
}
for (ll j = v2; (j != l); j = sp[j][0]) {
ll e = getline(j, sp[j][0]);
erase(query, e);
cnt++;
assert(cnt <= 29998);
ll res = count_common_roads(query) - treeres;
mp[j] = res;
query.push_back(e);
}
erase(query, getline(v1, v2));
set<ll> st;
for (ll j = v1; (j != l); j = sp[j][0]) st.insert(mp[j]);
for (ll j = v2; (j != l); j = sp[j][0]) st.insert(mp[j]);
if (st.size() == 1) {
if (*st.begin() >= 0) {
for (ll j = v1; (j != l); j = sp[j][0]) isroyal[j] = 0;
for (ll j = v2; (j != l); j = sp[j][0]) isroyal[j] = 0;
}
else {
for (ll j = v1; (j != l); j = sp[j][0]) isroyal[j] = 1;
for (ll j = v2; (j != l); j = sp[j][0]) isroyal[j] = 1;
}
}
else {
if (*st.begin() == -1) {
for (ll j = v1; (j != l); j = sp[j][0]) isroyal[j] = -mp[j];
for (ll j = v2; (j != l); j = sp[j][0]) isroyal[j] = -mp[j];
}
else {
for (ll j = v1; (j != l); j = sp[j][0]) isroyal[j] = 1 - mp[j];
for (ll j = v2; (j != l); j = sp[j][0]) isroyal[j] = 1 - mp[j];
}
}
}
}
};
for (i = 1; i < N; i++) if (isroyal[i]) isroyal[i] = 1;
assert(cnt <= 3 * N);
vector<ll> ans;
for (i = 1; i < N; i++) if (isroyal[i] == 1) ans.push_back(getline(i, sp[i][0]));
assert(ans.size() <= treeres);
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);
cnt++;
assert(cnt <= 29998);
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);
}
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
return ans;
}
Compilation message
simurgh.cpp: In function 'void erase(std::vector<int>&, ll)':
simurgh.cpp:74:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (i = 0; i < v.size(); i++) if (v[i] == a) break;
| ~~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:122:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (m = 0; m < back[k].size(); m++) {
| ~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from simurgh.cpp:6:
simurgh.cpp:219:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
219 | assert(ans.size() <= treeres);
| ~~~~~~~~~~~^~~~~~~~~~
simurgh.cpp: In function 'll p(ll, ll)':
simurgh.cpp:85:1: warning: control reaches end of non-void function [-Wreturn-type]
85 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
656 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
656 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
656 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
400 KB |
correct |
| 2 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
656 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
