| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1080382 |
2024-08-29T09:26:55 Z |
Elias |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
348 KB |
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#ifdef _DEBUG
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v);
int count_common_roads(const std::vector<int> &r);
#else
#include "simurgh.h"
#endif
set<int> trash_edges;
void dfs_spanning(int i, vector<vector<pair<int, int>>> &adj, vector<int> &vis, set<int> &edges)
{
vis[i] = true;
for (auto [c, j] : adj[i])
{
if (vis[c] || trash_edges.count(j))
continue;
edges.insert(j);
dfs_spanning(c, adj, vis, edges);
}
}
bool dfs_cycle(int i, int p, vector<vector<pair<int, int>>> &adj, vector<int> &vis, set<int> &edges)
{
vis[i] = true;
for (auto [c, j] : adj[i])
{
if (c == p)
continue;
if (vis[c] || dfs_cycle(c, i, adj, vis, edges))
{
assert(!trash_edges.count(j));
edges.insert(j);
return true;
}
}
return false;
}
vector<int> U, V;
int N;
int cnt_common_set(set<int> &a)
{
return count_common_roads(vector(a.begin(), a.end()));
}
vector<vector<pair<int, int>>> build_adj(set<int> &edges)
{
vector<vector<pair<int, int>>> adj(N);
for (int i : edges)
{
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
return adj;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
U = u, V = v;
N = n;
vector<vector<pair<int, int>>> adj_all(N);
for (int i = 0; i < u.size(); i++)
{
adj_all[u[i]].push_back({v[i], i});
adj_all[v[i]].push_back({u[i], i});
}
set<int> edges;
set<int> fancy_edges;
vector<int> visited(n);
dfs_spanning(0, adj_all, visited, edges);
int base_count = cnt_common_set(edges);
for (int i = 0; i < u.size(); i++)
{
if (edges.count(i) || fancy_edges.count(i) || trash_edges.count(i))
continue;
edges.insert(i);
auto adj = build_adj(edges);
visited = vector<int>(n);
set<int> cycle_edges;
dfs_cycle(u[i], -1, adj, visited, cycle_edges);
cycle_edges.erase(i);
set<int> stayed;
int action_stayed = 0;
for (int edge : cycle_edges)
{
if (fancy_edges.count(edge))
continue;
edges.erase(edge);
int new_count = cnt_common_set(edges);
if (new_count > base_count)
{
action_stayed = 1;
trash_edges.insert(edge);
break;
}
else if (new_count < base_count)
{
action_stayed = -1;
edges.insert(edge);
fancy_edges.insert(edge);
trash_edges.insert(i);
edges.erase(i);
break;
}
else
{
stayed.insert(edge);
edges.insert(edge);
}
}
if (action_stayed == 0)
{
trash_edges.insert(i);
edges.erase(i);
}
else if (action_stayed == 1)
{
for (int edge : stayed)
{
fancy_edges.insert(edge);
}
}
else if (action_stayed == -1)
{
for (int edge : stayed)
{
trash_edges.insert(edge);
edges.erase(edge);
}
}
vector<int> nodes;
visited = vector<int>(n);
for (auto edge : edges)
{
nodes.push_back(u[edge]);
nodes.push_back(v[edge]);
visited[u[edge]] = true;
visited[v[edge]] = true;
}
for (int node : nodes)
{
dfs_spanning(node, adj_all, visited, edges);
}
}
for (auto edge : edges)
fancy_edges.insert(edge);
return vector(fancy_edges.begin(), fancy_edges.end());
}
#ifdef _DEBUG
using namespace std;
static int MAXQ = 30000;
static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;
static vector<int> parent;
static int find(int node)
{
return (parent[node] == node ? node : parent[node] = find(parent[node]));
}
static bool merge(int v1, int v2)
{
v1 = find(v1);
v2 = find(v2);
if (v1 == v2)
return false;
parent[v1] = v2;
return true;
}
static void wrong_answer()
{
printf("NO\n");
exit(0);
}
static bool is_valid(const vector<int> &r)
{
if (int(r.size()) != n - 1)
return false;
for (int i = 0; i < n - 1; i++)
if (r[i] < 0 || r[i] >= m)
return false;
parent.resize(n);
for (int i = 0; i < n; i++)
{
parent[i] = i;
}
for (int i = 0; i < n - 1; i++)
{
if (!merge(u[r[i]], v[r[i]]))
{
return false;
}
}
return true;
}
static int _count_common_roads_internal(const vector<int> &r)
{
if (!is_valid(r))
wrong_answer();
int common = 0;
for (int i = 0; i < n - 1; i++)
{
bool is_common = goal[r[i]];
if (is_common)
common++;
}
return common;
}
int count_common_roads(const vector<int> &r)
{
q++;
if (q > MAXQ)
wrong_answer();
return _count_common_roads_internal(r);
}
int main()
{
assert(2 == scanf("%d %d", &n, &m));
assert(1 == scanf("%d", &MAXQ));
u.resize(m);
v.resize(m);
for (int i = 0; i < m; i++)
assert(2 == scanf("%d %d", &u[i], &v[i]));
goal.resize(m, false);
for (int i = 0; i < n - 1; i++)
{
int id;
assert(1 == scanf("%d", &id));
goal[id] = true;
}
vector<int> result = find_roads(n, u, v);
if (_count_common_roads_internal(result) != n - 1)
wrong_answer();
printf("OK\n");
for (int i = 0; i < (int)result.size(); i++)
{
if (i)
printf(" ");
printf("%d", result[i]);
}
printf("\n");
return 0;
}
#endif
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < u.size(); i++)
| ~~^~~~~~~~~~
simurgh.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < u.size(); i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
correct |
| 2 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
