#include "simurgh.h"
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define query count_common_roads
const int maxN = 500;
struct Jmp
{
int to, ind;
operator int&() { return to; }
operator const int&() const { return to; }
};
int in[maxN], out[maxN];
Jmp par[maxN];
int gold[maxN];
vector<int> dfsq;
vector<Jmp> nei[maxN];
vector<int> same[maxN];
pair<int, Jmp> fup[maxN];
inline bool Upper(int u, int v) { return in[u] <= in[v] && out[u] >= out[v]; }
bool used[maxN];
void DFS(int v, Jmp p)
{
cerr << "v: " << v << '\n';
static int time = 0;
used[v] = true;
in[v] = ++time;
par[v] = p;
fup[v] = {-1, {-1, -1}};
for (Jmp to: nei[v])
if (!used[to])
{
dfsq.push_back(to.ind);
DFS(to, {v, to.ind});
if (fup[v].first == -1 || fup[to].first != -1 && in[fup[to].second] <= in[fup[v].second])
fup[v] = fup[to];
}
else if (to != p && (fup[v].first == -1 || in[to] <= in[fup[v].second]))
fup[v] = {v, to};
out[v] = time;
}
void DFS1(int v)
{
for (int to: same[v])
if (gold[to] == -1)
{
gold[to] = gold[v];
DFS1(to);
}
}
vector<int> find_roads(int n, vector<int> us, vector<int> vs)
{
auto OK = [&us, &vs](vector<int> q)
{
vector<bool> used(q.size() + 1);
for (int i = 0; i < q.size(); ++i)
used[us[q[i]]] = used[vs[q[i]]] = true;
return find(used.begin(), used.end(), false) == used.end();
};
for (int i = 0; i < us.size(); ++i)
gold[i] = -1;
for (int i = 0; i < us.size(); ++i)
{
nei[us[i]].push_back({vs[i], i});
nei[vs[i]].push_back({us[i], i});
}
DFS(0, {-1, -1});
if (!OK(dfsq))
throw;
int dfsans = query(dfsq);
for (int i = 0; i < us.size(); ++i)
{
int u = us[i], v = vs[i];
if (in[u] > in[v]) swap(u, v);
if (fup[v].first == -1 || in[fup[v].second] > in[u])
{
gold[i] = 1;
continue;
}
int dfse, backe;
if (par[v] == u)
dfse = par[v].ind, backe = fup[v].second.ind;
else
{
for (backe = 0; ; ++backe)
if (us[backe] == v && vs[backe] == u || us[backe] == u && vs[backe] == v)
break;
dfse = par[v].ind;
}
auto it = find(dfsq.begin(), dfsq.end(), dfse);
*it = backe;
if (!OK(dfsq))
throw;
int curans = query(dfsq);
if (curans == dfsans)
{
same[backe].push_back(dfse);
same[dfse].push_back(backe);
}
else if (curans > dfsans)
gold[backe] = 1, gold[dfse] = 0;
else
gold[backe] = 0, gold[dfse] = 1;
*it = dfse;
}
for (int i = 0; i < us.size(); ++i)
if (gold[i] != -1)
DFS1(i);
for (int i = 0; i < us.size(); ++i)
if (gold[i] == -1)
throw;
vector<int> ans;
for (int i = 0; i < us.size(); ++i)
if (gold[i])
ans.push_back(i);
/*if (ans.size() != n - 1)
throw;*/
/*cerr << "ans: ";
for (int i: ans)
cerr << i << ' ';
cerr << '\n';*/
return ans;
}
Compilation message
simurgh.cpp: In function 'void DFS(int, Jmp)':
simurgh.cpp:38:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (fup[v].first == -1 || fup[to].first != -1 && in[fup[to].second] <= in[fup[v].second])
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp: In lambda function:
simurgh.cpp:60:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q.size(); ++i)
~~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < us.size(); ++i)
~~^~~~~~~~~~~
simurgh.cpp:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < us.size(); ++i)
~~^~~~~~~~~~~
simurgh.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < us.size(); ++i)
~~^~~~~~~~~~~
simurgh.cpp:90:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (us[backe] == v && vs[backe] == u || us[backe] == u && vs[backe] == v)
simurgh.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < us.size(); ++i)
~~^~~~~~~~~~~
simurgh.cpp:113:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < us.size(); ++i)
~~^~~~~~~~~~~
simurgh.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < us.size(); ++i)
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
correct |
| 2 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
