| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338322 |
2020-12-23T02:36:19 Z |
SHZhang |
Simurgh (IOI17_simurgh) |
C++14 |
|
23 ms |
4204 KB |
#include <vector>
#include <algorithm>
#include <map>
#include "simurgh.h"
using namespace std;
vector<int> graph[505];
bool vis[505];
int depth[505];
int parent[505];
int prtedge[505];
int u[505], v[505];
int n, m;
vector<pair<int, int> > extra_edge;
vector<int> tree_edge;
map<pair<int, int>, int> edge2id;
bool ans[250005];
void dfs(int node, int prt, int dep)
{
vis[node] = true;
depth[node] = dep;
parent[node] = prt;
for (int i = 0; i < graph[node].size(); i++) {
int nxt = graph[node][i];
if (!vis[nxt]) {
tree_edge.push_back(edge2id[make_pair(node, nxt)]);
dfs(nxt, node, dep + 1);
} else if (nxt != prt && depth[nxt] < dep) {
extra_edge.push_back(make_pair(node, nxt));
}
}
}
vector<int> good_edge;
vector<int> unkn_edge[505];
int uf[505];
int fin(int x)
{
if (uf[x] == x) return x;
return uf[x] = fin(uf[x]);
}
void un(int x, int y)
{
x = fin(x); y = fin(y);
if (x == y) return;
uf[x] = y;
}
int search(vector<int> ids, int known_amt)
{
if (ids.empty()) return 0;
if (known_amt == -1) {
for (int i = 0; i < n; i++) uf[i] = i;
int base_val = 0;
vector<int> query_set;
for (int i = 0; i < ids.size(); i++) {
query_set.push_back(ids[i]);
un(u[ids[i]], v[ids[i]]);
}
for (int i = 0; i < tree_edge.size(); i++) {
int edge = good_edge[i];
if (fin(u[edge]) == fin(v[edge])) continue;
un(u[edge], v[edge]);
query_set.push_back(edge);
if (ans[edge]) base_val++;
}
int query_res = count_common_roads(query_set) - base_val;
known_amt = query_res;
}
if (!known_amt) return 0;
if (ids.size() == 1) {
ans[ids[0]] = true; return 1;
}
vector<int> left, right;
for (int i = 0; i < ids.size(); i++) {
if (i < ids.size() / 2) {
left.push_back(ids[i]);
} else {
right.push_back(ids[i]);
}
}
int left_num = search(left, -1);
search(right, known_amt - left_num);
return known_amt;
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
n = N; m = U.size();
for (int i = 0; i < n; i++) prtedge[i] = -1;
for (int i = 0; i < m; i++) {
u[i] = U[i]; v[i] = V[i];
graph[u[i]].push_back(v[i]);
graph[v[i]].push_back(u[i]);
edge2id[make_pair(u[i], v[i])] = i;
edge2id[make_pair(v[i], u[i])] = i;
}
dfs(0, -1, 0);
vector<int> dfs_tree_qry;
for (int i = 0; i < tree_edge.size(); i++) {
//fprintf(stderr, "tree %d %d\n", tree_edge[i].first, tree_edge[i].second);
dfs_tree_qry.push_back(tree_edge[i]);
}
int tree_base = count_common_roads(dfs_tree_qry);
for (int i = 0; i < extra_edge.size(); i++) {
//fprintf(stderr, "extra %d %d\n", extra_edge[i].first, extra_edge[i].second);
int curnode = extra_edge[i].first;
vector<pair<int, int> > query_edge;
vector<int> query_res;
//int route_on = 0;
bool has_zero = false;
while (curnode != extra_edge[i].second) {
if (prtedge[curnode] == -1) {
prtedge[curnode] = i;
query_edge.push_back(make_pair(curnode, parent[curnode]));
} else {
if (!has_zero && !ans[edge2id[make_pair(curnode, parent[curnode])]]) {
query_edge.push_back(make_pair(curnode, parent[curnode]));
has_zero = true;
}
}
curnode = parent[curnode];
}
if (query_edge.size() - (int)has_zero == 0) {
unkn_edge[extra_edge[i].first].push_back(extra_edge[i].second); continue;
}
good_edge.push_back(edge2id[extra_edge[i]]);
int max_query_res = tree_base;
for (int j = 0; j < query_edge.size(); j++) {
vector<int> query_set;
for (int k = 0; k < n - 1; k++) {
if (dfs_tree_qry[k] != edge2id[query_edge[j]]) {
query_set.push_back(dfs_tree_qry[k]);
}
}
query_set.push_back(edge2id[extra_edge[i]]);
int cnt = count_common_roads(query_set);
query_res.push_back(cnt);
max_query_res = max(max_query_res, cnt);
}
for (int j = 0; j < query_edge.size(); j++) {
if (query_res[j] != max_query_res) {
//printf("%d %d\n", edge2id[extra_edge[i]], edge2id[query_edge[j]]);
ans[edge2id[query_edge[j]]] = true;
}
}
//printf("! %d %d\n", edge2id[extra_edge[i]], max_query_res);
if (tree_base != max_query_res) ans[edge2id[extra_edge[i]]] = true;
}
for (int i = 1; i < n; i++) {
good_edge.push_back(edge2id[make_pair(i, parent[i])]);
if (prtedge[i] == -1) {
ans[edge2id[make_pair(i, parent[i])]] = true;
}
}
for (int i = 0; i < n; i++) {
vector<int> edges;
for (int j = 0; j < unkn_edge[i].size(); j++) {
edges.push_back(edge2id[make_pair(i, unkn_edge[i][j])]);
}
search(edges, -1);
}
vector<int> final_ans;
for (int i = 0; i < m; i++) {
if (ans[i]) {
//fprintf(stderr, "%d\n", i);
final_ans.push_back(i);
}
}
return final_ans;
}
Compilation message
simurgh.cpp: In function 'void dfs(int, int, int)':
simurgh.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int i = 0; i < graph[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'int search(std::vector<int>, int)':
simurgh.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0; i < ids.size(); i++) {
| ~~^~~~~~~~~~~~
simurgh.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < tree_edge.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < ids.size(); i++) {
| ~~^~~~~~~~~~~~
simurgh.cpp:83:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | if (i < ids.size() / 2) {
| ~~^~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (int i = 0; i < tree_edge.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < extra_edge.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp:135:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (int j = 0; j < query_edge.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for (int j = 0; j < query_edge.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp:164:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for (int j = 0; j < unkn_edge[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
correct |
| 2 |
Correct |
1 ms |
364 KB |
correct |
| 3 |
Runtime error |
23 ms |
4204 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
