| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1052823 |
2024-08-11T02:21:50 Z |
becaido |
Simurgh (IOI17_simurgh) |
C++17 |
|
0 ms |
348 KB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#include "grader.cpp"
#else
#include "simurgh.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 505;
const int MSIZ = SIZE * SIZE / 2;
int n, m;
pair<int, int> ed[MSIZ];
vector<pair<int, int>> adj[SIZE];
int h[SIZE], pa[SIZE], pid[SIZE];
vector<int> tree;
bool is_tree[MSIZ];
int tree_cnt, ty[MSIZ];
struct DSU {
int n;
vector<int> to, h;
void init(int n_) {
n = n_;
to.resize(n + 1);
h.resize(n + 1);
iota(to.begin() + 1, to.end(), 1);
fill(h.begin() + 1, h.end(), 0);
}
int dsu(int x) {
return x == to[x] ? x : (to[x] = dsu(to[x]));
}
bool merge(int a, int b, bool f = 0) {
a = dsu(a), b = dsu(b);
if (a == b) return 0;
if (h[a] < h[b]) swap(a, b);
to[b] = a;
h[a] += (h[a] == h[b]);
if (f) ty[a] = ty[b] = (ty[a] < 2 ? ty[a] : ty[b]);
return 1;
}
} mdsu;
void dfs(int pos) {
for (auto [np, id] : adj[pos]) if (h[np] == 0) {
h[np] = h[pos] + 1;
pa[np] = pos;
pid[np] = id;
tree.pb(id);
is_tree[id] = 1;
dfs(np);
}
}
int que(vector<int> e) {
for (int &id : e) id--;
return count_common_roads(e);
}
int ask(int x, int y) {
vector<int> e;
e.pb(y);
for (int id : tree) if (x != id) e.pb(id);
return que(e);
}
int ask_forest(vector<int> e) {
DSU g;
g.init(n);
for (int id : e) {
auto [x, y] = ed[id];
g.merge(x, y);
}
int cnt = 0;
for (int id : tree) {
auto [x, y] = ed[id];
if (g.merge(x, y)) {
e.pb(id);
cnt -= ty[id];
}
}
cnt += que(e);
return cnt;
}
vector<int> find_roads(int n_, vector<int> u, vector<int> v) {
n = n_, m = u.size();
FOR (i, 1, n) {
adj[i].clear();
h[i] = pa[i] = pid[i] = 0;
}
u.insert(u.begin(), 0);
v.insert(v.begin(), 0);
FOR (i, 1, m) {
is_tree[i] = 0;
u[i]++, v[i]++;
ed[i] = {u[i], v[i]};
adj[u[i]].pb(v[i], i);
adj[v[i]].pb(u[i], i);
}
tree.clear();
h[1] = 1, dfs(1);
tree_cnt = que(tree);
fill(ty + 1, ty + m + 1, 2);
mdsu.init(m);
FOR (i, 1, m) if (is_tree[i] == 0) {
int a = u[i], b = v[i];
if (h[a] > h[b]) swap(a, b);
vector<int> e;
int o = 0;
while (h[a] < h[b]) {
if (ty[mdsu.dsu(pid[b])] == 2) e.pb(pid[b]);
else o = pid[b];
b = pa[b];
}
if (e.size() == 0) continue;
for (int j : e) {
int cnt = ask(j, i);
if (tree_cnt == cnt) mdsu.merge(i, j, 1);
else if (tree_cnt < cnt) ty[mdsu.dsu(i)] = 1, ty[mdsu.dsu(j)] = 0;
else ty[mdsu.dsu(i)] = 0, ty[mdsu.dsu(j)] = 1;
}
if (ty[mdsu.dsu(i)] == 2) {
if (o == 0) ty[mdsu.dsu(i)] = 0;
else {
int cnt = ask(o, i);
if (tree_cnt == cnt) mdsu.merge(o, i, 1);
else ty[mdsu.dsu(i)] = (tree_cnt < cnt);
}
}
}
for (int id : tree) if (ty[mdsu.dsu(id)] == 2) ty[mdsu.dsu(id)] = 1;
FOR (i, 1, m) ty[i] = ty[mdsu.dsu(i)];
DSU g;
g.init(n);
for (int id : tree) {
auto [x, y] = ed[id];
g.merge(x, y);
}
FOR (i, 1, n) {
vector<int> e;
for (auto [j, id] : adj[i]) {
auto [x, y] = ed[id];
if (ty[id] == 2 && g.dsu(x) != g.dsu(y)) e.pb(id);
}
if (e.size() == 0) continue;
auto rec = [&](auto rec, int l, int r, int tot)->void {
if (tot == 0) {
FOR (j, l, r) ty[e[j]] = 0;
return;
}
if (tot == r - l + 1) {
FOR (j, l, r) {
auto [x, y] = ed[e[j]];
ty[e[j]] = 1;
g.merge(x, y);
}
return;
}
int mid = (l + r) / 2, lc;
vector<int> le;
FOR (j, l, mid) le.pb(e[j]);
lc = ask_forest(le);
rec(rec, l, mid, lc);
rec(rec, mid + 1, r, tot - lc);
};
rec(rec, 0, e.size() - 1, ask_forest(e));
}
vector<int> ans;
FOR (i, 1, m) if (ty[i] == 1) ans.pb(i - 1);
return ans;
}
/*
in1
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
correct |
| 2 |
Incorrect |
0 ms |
344 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
