#include "simurgh.h"
#include <cstdio>
#include <cstring>
#include <vector>
const int N = 500;
const int E = N * N;
std::vector<std::pair<int, int> > g[N];
int u[N], val[N];
bool know[E], ans[E];
std::vector<int> edg;
int it;
void dfs(int v) {
u[v] = it;
for (int i = 0; i < (int)g[v].size(); ++i) if (!u[g[v][i].first]) {
edg.push_back(g[v][i].second);
dfs(g[v][i].first);
}
}
std::vector<int> find_roads(int n, std::vector<int> u_, std::vector<int> v_) {
for (int i = 0; i < (int)u_.size(); ++i) {
g[u_[i]].push_back(std::make_pair(v_[i], i));
g[v_[i]].push_back(std::make_pair(u_[i], i));
}
for (int i = 0; i < n; ++i) {
memset(u, 0, n << 2);
u[i] = 1;
it = 0;
for (int j = 0; j < n; ++j) if (!u[j]) {
++it;
dfs(j);
}
for (int iit = 1; iit <= it; ++iit) {
for (int j = 0;; ++j) if (u[g[i][j].first] == iit) {
edg.push_back(g[i][j].second);
break;
}
}
for (int iit = 1; iit <= it; ++iit) {
int fi = edg[n - 2 - it + iit];
edg.erase(edg.begin() + n - 2 - it + iit);
int mn = ~(1 << 31), mx = 0, real = -1;
bool askonce = 0;
for (int j = 0; j < (int)g[i].size(); ++j) if (u[g[i][j].first] == iit) {
if (!know[g[i][j].second] || !askonce) {
edg.push_back(g[i][j].second);
val[j] = count_common_roads(edg);
if (know[g[i][j].second]) {
real = val[j] - ans[g[i][j].second];
askonce = 1;
}
mn = std::min(mn, val[j]);
mx = std::max(mx, val[j]);
edg.pop_back();
}
}
if (real == -1) real = mn - (mn == mx);
for (int j = 0; j < (int)g[i].size(); ++j) if (u[g[i][j].first] == iit && !know[g[i][j].second]) {
know[g[i][j].second] = 1;
ans[g[i][j].second] = val[j] != real;
}
edg.insert(edg.begin() + n - 2 - it + iit, fi);
}
edg.clear();
}
std::vector<int> ret;
for (int i = 0; i < (int)u_.size(); ++i) if (ans[i]) ret.push_back(i);
for (int i = 0; i < (int)ret.size(); ++i) printf("%d ", ret[i]);
printf("\n");
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
