| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1065607 |
2024-08-19T09:52:54 Z |
mc061 |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
604 KB |
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p;
vector<int> sz;
int get(int a) {
return p[a] = (a == p[a] ? a : get(p[a]));
}
void merge(int a, int b) {
int x = get(a);
int y = get(b);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
p[x] = y;
sz[y] += sz[x];
}
DSU(int n) {
p.resize(n);
sz.resize(n, 1);
iota(p.begin(), p.end(), 0);
}
};
const int N = 500;
vector<int> graph[N];
bool vis[N]={};
bool isBridge[N*N]={};
bool cant[N][N]={};
bool has_edge[N][N]={};
bool is_ans[N][N]={};
bool road_now[N][N]={};
int road_ind[N][N]={};
int cntv = 0;
int n;
int count_common_roads(const vector<int>& r);
void dfs(int v, int b1, int b2) {
cntv++;
vis[v] = true;
for (int i = 0; i < graph[v].size(); ++i) {
int u = graph[v][i];
if (vis[u] || (u == b1 && v == b2) || (u == b2 && v == b1)) continue;
dfs(u, b1, b2);
}
}
bool is_bridge(int v, int u) {
cntv = 0;
memset(vis, 0, sizeof(vis));
dfs(0, v, u);
assert(cntv <= n);
return cntv != n;
}
void build(int v, vector<int>& comp) {
vis[v] = true;
comp.push_back(v);
for (int u : graph[v]) if (!cant[v][u] && !vis[u]) build(u, comp);
}
vector<int> find_roads(int n_, vector<int> U, vector<int> V) {
n = n_;
vector<array<int, 3>> edges;
for (int i = 0; i < U.size(); ++i) {
int u = U[i], v = V[i];
graph[v].push_back(u);
graph[u].push_back(v);
edges.push_back({u, v, i});
has_edge[u][v] = has_edge[v][u] = true;
road_ind[u][v] = road_ind[v][u] = i;
}
DSU tot(n);
for (int i = 0; i < edges.size(); ++i) {
int u = edges[i][0], v = edges[i][1];
isBridge[i] = is_bridge(u, v);
if (isBridge[i]) cant[u][v] = cant[v][u] = is_ans[v][u] = is_ans[u][v] = true, tot.merge(v, u);
}
memset(vis, 0, sizeof(vis));
vector<vector<int>> comps;
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
comps.push_back({});
build(i, comps[comps.size()-1]);
}
}
vector<vector<int>> edges_from_v(n);
for (vector<int> co : comps) {
random_shuffle(co.begin(), co.end());
memset(road_now, 0, sizeof(road_now));
vector<pair<int, int>> edges_here;
for (int i = 0; i < co.size(); ++i)
edges_from_v[co[i]].clear();
for (int i = 0; i < co.size(); ++i) {
for (int j = i+1; j < co.size(); ++j) {
if (!has_edge[co[i]][co[j]]) continue;
edges_here.push_back({co[i], co[j]});
edges_from_v[co[i]].push_back(co[j]);
edges_from_v[co[j]].push_back(co[i]);
road_now[co[i]][co[j]] = road_now[co[j]][co[i]] = true;
}
}
random_shuffle(edges_here.begin(), edges_here.end());
DSU d(n);
vector<int> outside;
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
if (!road_now[i][j] && has_edge[i][j] && d.get(i) != d.get(j)) {
d.merge(i, j);
outside.push_back(road_ind[i][j]);
}
}
}
stack<int> st;
st.push(co[0]);
while (!st.empty()) {
int v = st.top();
st.pop();
vector<int> plus=outside;
DSU d_here(n);
for (int i = 0; i < edges_here.size(); ++i) {
if (edges_here[i].first == v || edges_here[i].second == v) continue;
if (d_here.get(edges_here[i].first) != d_here.get(edges_here[i].second)) {
d_here.merge(edges_here[i].first, edges_here[i].second);
plus.push_back(road_ind[edges_here[i].first][edges_here[i].second]);
}
}
vector<pair<int, int>> res;
bool included_bad = false;
bool included_good = false;
for (int i = 0; i < edges_from_v[v].size(); ++i) {
int u = edges_from_v[v][i];
if (!(tot.get(v) == tot.get(u) && (included_bad || included_good))) {
plus.push_back(road_ind[v][u]);
res.push_back({count_common_roads(plus), u});
plus.pop_back();
if (tot.get(v) == tot.get(u))
included_bad = true;
}
}
sort(res.begin(), res.end());
for (int i = 0; i < res.size(); ++i) {
bool ok = res[i].first > res[0].first;
if (included_bad && res[i].first > res[0].first) ok = true;
else if (res[0].first == res.back().first) ok = true;
if (!ok) continue;
if (res[i].first == res.back().first && tot.get(res[i].second) != tot.get(v)) {
is_ans[res[i].second][v] = is_ans[v][res[i].second] = true;
tot.merge(v, res[i].second);
st.push(res[i].second);
}
}
}
}
vector<int> res;
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
if (is_ans[i][j]) res.push_back(road_ind[i][j]);
}
}
sort(res.begin(), res.end());
return res;
}
Compilation message
simurgh.cpp: In function 'void dfs(int, int, int)':
simurgh.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < graph[v].size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i = 0; i < U.size(); ++i) {
| ~~^~~~~~~~~~
simurgh.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i = 0; i < edges.size(); ++i) {
| ~~^~~~~~~~~~~~~~
simurgh.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int i = 0; i < co.size(); ++i)
| ~~^~~~~~~~~~~
simurgh.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int i = 0; i < co.size(); ++i) {
| ~~^~~~~~~~~~~
simurgh.cpp:105:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int j = i+1; j < co.size(); ++j) {
| ~~^~~~~~~~~~~
simurgh.cpp:131:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 0; i < edges_here.size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp:141:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (int i = 0; i < edges_from_v[v].size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:152:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (int i = 0; i < res.size(); ++i) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
correct |
| 2 |
Incorrect |
1 ms |
604 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
correct |
| 2 |
Incorrect |
1 ms |
604 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
correct |
| 2 |
Incorrect |
1 ms |
604 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
correct |
| 2 |
Incorrect |
0 ms |
600 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
correct |
| 2 |
Incorrect |
1 ms |
604 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
