| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 155172 |
2019-09-26T18:42:46 Z |
faremy |
Simurgh (IOI17_simurgh) |
C++14 |
|
271 ms |
7328 KB |
#include "simurgh.h"
#include <iostream>
struct Edge
{
Edge(int u, int v, int i) : start(u), end(v), id(i) {}
int start, end, id;
};
const int MAXN = 500;
const int MAXM = MAXN * (MAXN - 1) / 2;
const int LOGN = 9;
std::vector<Edge> graph[MAXN];
int parent[MAXN];
int posInSpanning[MAXM];
std::vector<Edge> spanning;
int previous[MAXN], edgeToPrev[MAXN];
int depth[MAXN];
int ancester[MAXN][LOGN];
std::vector<int> golden;
std::vector<Edge> todo;
std::vector<int> order;
bool seen[MAXN];
bool isRoyal[MAXM];
std::vector<int> royal;
void disjointreset(int nodes)
{
for (int iNode = 0; iNode < nodes; iNode++)
parent[iNode] = iNode;
}
int find(int node)
{
if (node != parent[node])
parent[node] = find(parent[node]);
return parent[node];
}
bool merge(int start, int end)
{
int st = find(start), nd = find(end);
parent[nd] = st;
return (st != nd);
}
void root(int node)
{
for (Edge &edge : graph[node])
if (posInSpanning[edge.id] != -1 && previous[node] != edge.end)
{
depth[edge.end] = depth[node] + 1;
previous[edge.end] = node;
edgeToPrev[edge.end] = edge.id;
isRoyal[edge.id] = true;
root(edge.end);
}
order.emplace_back(node);
}
void setbinlift(int nodes)
{
for (int iNode = 0; iNode < nodes; iNode++)
{
ancester[iNode][0] = previous[iNode];
for (int iExp = 1; iExp < LOGN; iExp++)
ancester[iNode][iExp] = -1;
}
}
int findanc(int node, int exp)
{
if (ancester[node][exp] == -1)
ancester[node][exp] = findanc(findanc(node, exp - 1), exp - 1);
return ancester[node][exp];
}
int lift(int node, int dist)
{
if (dist == 0)
return node;
int exp = 31 - __builtin_clz(dist);
return lift(findanc(node, exp), dist - (1 << exp));
}
int lca(int u, int v)
{
if (depth[u] < depth[v])
std::swap(u, v);
u = lift(u, depth[u] - depth[v]);
if (u == v)
return u;
for (int iExp = LOGN - 1; iExp > -1; iExp--)
if (findanc(u, iExp) != findanc(v, iExp))
{
u = findanc(u, iExp);
v = findanc(v, iExp);
}
return findanc(u, 0);
}
int replace(int edge, int other)
{
golden[posInSpanning[edge]] = other;
int inTree = count_common_roads(golden);
golden[posInSpanning[edge]] = edge;
return inTree;
}
int findval(int node, int stop, int expVal, int edge, bool want)
{
if (depth[node] <= depth[stop])
return -1;
if (find(node) == node)
{
int inTree = replace(edgeToPrev[node], edge);
parent[node] = previous[node];
if (inTree == expVal)
{
todo.emplace_back(0, 0, edgeToPrev[node]);
return findval(previous[node], stop, expVal, edge, true);
}
todo.emplace_back(1, 0, edgeToPrev[node]);
findval(previous[node], stop, expVal, edge, false);
return (expVal < inTree);
}
else
{
if (!want)
{
findval(find(node), stop, expVal, edge, false);
return -1;
}
int inTree = replace(edgeToPrev[node], edge);
findval(find(node), stop, expVal, edge, false);
return (isRoyal[edgeToPrev[node]] ^ (inTree != expVal));
}
}
int count(int node, std::vector<int> &edges, int nodes)
{
disjointreset(nodes);
golden.clear();
for (int edge : edges)
{
merge(graph[node][edge].start, graph[node][edge].end);
golden.emplace_back(graph[node][edge].id);
}
int inTree = 0;
for (Edge &edge : spanning)
if (merge(edge.start, edge.end))
{
inTree += isRoyal[edge.id];
golden.emplace_back(edge.id);
}
return (count_common_roads(golden) - inTree);
}
int search(int left, int right, std::vector<int> &sspace, int node, int nodes)
{
if (right - left == 1)
return left;
std::vector<int> ask;
for (int iEdge = left; iEdge < (left + right) / 2; iEdge++)
ask.emplace_back(sspace[iEdge]);
if (count(node, ask, nodes) > 0)
return search(left, (left + right) / 2, sspace, node, nodes);
return search((left + right) / 2, right, sspace, node, nodes);
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
int roads = u.size();
for (int iRoad = 0; iRoad < roads; iRoad++)
{
graph[u[iRoad]].emplace_back(u[iRoad], v[iRoad], iRoad);
graph[v[iRoad]].emplace_back(v[iRoad], u[iRoad], iRoad);
}
disjointreset(n);
for (int iRoad = 0; iRoad < roads; iRoad++)
{
if (merge(u[iRoad], v[iRoad]))
{
posInSpanning[iRoad] = spanning.size();
spanning.emplace_back(u[iRoad], v[iRoad], iRoad);
golden.emplace_back(iRoad);
}
else
{
posInSpanning[iRoad] = -1;
}
}
int inTree = count_common_roads(golden);
root(0);
setbinlift(n);
disjointreset(n);
for (int iRoad = 0; iRoad < roads; iRoad++)
if (posInSpanning[iRoad] == -1)
{
int anc = lca(u[iRoad], v[iRoad]);
int val = findval(u[iRoad], anc, inTree, iRoad, false);
int x = todo.size();
val = std::max(val, findval(v[iRoad], anc, inTree, iRoad, false));
if (val == -1)
{
if (x == 0 && todo.size() != 0 && u[iRoad] != anc)
{
int cnt = replace(edgeToPrev[u[iRoad]], iRoad);
val = isRoyal[edgeToPrev[u[iRoad]]] ^ (cnt != inTree);
}
else if (x != 0 && x == todo.size() && v[iRoad] != anc)
{
int cnt = replace(edgeToPrev[v[iRoad]], iRoad);
val = isRoyal[edgeToPrev[v[iRoad]]] ^ (cnt != inTree);
}
else
{
val = 0;
}
}
while (!todo.empty())
{
isRoyal[todo.back().id] = val ^ (todo.back().start);
todo.pop_back();
}
}
for (int iNode = 0; iNode < n; iNode++)
{
std::vector<int> searchspace;
for (int iEdge = 0; iEdge < (int)graph[order[iNode]].size(); iEdge++)
if (seen[graph[order[iNode]][iEdge].end] && posInSpanning[graph[order[iNode]][iEdge].id] == -1)
searchspace.emplace_back(iEdge);
int connected = count(order[iNode], searchspace, n);
for (int iRoy = 0; iRoy < connected; iRoy++)
{
int pos = search(0, searchspace.size(), searchspace, order[iNode], n);
isRoyal[graph[order[iNode]][searchspace[pos]].id] = true;
searchspace.erase(searchspace.begin() + pos);
}
seen[order[iNode]] = true;
}
for (int iEdge = 0; iEdge < roads; iEdge++)
if (isRoyal[iEdge])
royal.emplace_back(iEdge);
return royal;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:233:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if (x != 0 && x == todo.size() && v[iRoad] != anc)
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
376 KB |
correct |
| 4 |
Incorrect |
10 ms |
3576 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
376 KB |
correct |
| 4 |
Incorrect |
10 ms |
3576 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
376 KB |
correct |
| 4 |
Incorrect |
10 ms |
3576 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
157 ms |
5384 KB |
correct |
| 4 |
Correct |
255 ms |
7160 KB |
correct |
| 5 |
Correct |
260 ms |
7032 KB |
correct |
| 6 |
Correct |
233 ms |
7160 KB |
correct |
| 7 |
Correct |
223 ms |
7216 KB |
correct |
| 8 |
Correct |
214 ms |
7088 KB |
correct |
| 9 |
Correct |
254 ms |
7328 KB |
correct |
| 10 |
Correct |
247 ms |
7220 KB |
correct |
| 11 |
Correct |
245 ms |
7288 KB |
correct |
| 12 |
Correct |
250 ms |
7276 KB |
correct |
| 13 |
Correct |
2 ms |
380 KB |
correct |
| 14 |
Correct |
252 ms |
7196 KB |
correct |
| 15 |
Correct |
271 ms |
7160 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
376 KB |
correct |
| 4 |
Incorrect |
10 ms |
3576 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
