#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
//int count_common_roads(vector<int> r);
struct Arc {
int u, v, i;
};
int nbNodes(0), nbArcs(0);
int parent[501];
Arc arcs[501*250];
vector<Arc> adj[501];
int depth[501];
int indice[501][501];
bool vu[501];
int memo[501][501];//-1 if not calc., 0 if same, 1 if x+1, 2 if x-1
set<int> golden;
int oldValue(-1);
const int ROYAL = 500*250+2;
const int NOT_ROYAL = 500*250+1;
int repr[501*250];
int find(int x) {
return x == repr[x] ? x : (repr[x] = find(repr[x]));
}
void merge(int x, int y) {
repr[find(x)] = find(y);
}
int query() {
vector<int>r;
for(int i:golden)r.push_back(i);
return oldValue = count_common_roads(r);
}
void findParent(int u, int p, int d) {
if(vu[u]) return;
vu[u] = 1;
parent[u] = p;
depth[u] = d;
for(Arc a : adj[u])
if(a.v != p)
findParent(a.v, u, d+1);
}
vector<int> cur;
vector<int> ans;
bool ffff=0;
void dfs(int u, int p, int cible) {
if(u == cible) {
ans = cur;
ffff=1;
}
if(ffff)return;
for(Arc a : adj[u]) {
if(!golden.count(a.i) or a.v == p) continue;
cur.push_back(a.i);
dfs(a.v, u, cible);
cur.pop_back();
}
}
vector<int> edges(int u, int v) {
dfs(u, -1, v);
return ans;
}
void buildTree() {
for(int node = 0; node < nbNodes; node++)
if(parent[node] != -1)
golden.insert(indice[node][parent[node]]);
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
nbNodes = n;
nbArcs = (int)u.size();
for(int iArc = 0; iArc < nbArcs; iArc++) {
arcs[iArc].u = u[iArc];
arcs[iArc].v = v[iArc];
arcs[iArc].i = iArc;
adj[u[iArc]].push_back({u[iArc], v[iArc], iArc});
adj[v[iArc]].push_back({v[iArc], u[iArc], iArc});
indice[u[iArc]][v[iArc]] = indice[v[iArc]][u[iArc]] = iArc;
}
for(int i = 0; i < n; i++) vu[i] = 0;
findParent(0, -1, 0);
for(int i = 0; i < 501*250; i++) repr[i] = i;
buildTree();
query();
vector<int> sol;
for(int iA = 0; iA < nbArcs; iA++) {
Arc a = arcs[iA];
if(oldValue == n - 1) break;
if(golden.count(a.i)) continue;
vector<int> arcsPossibles = edges(a.u, a.v);
// cout << a.i << ":\n";
for(int i : arcsPossibles) {
// cout << " " << i << ":\n";
int old = oldValue;
golden.erase(i);
golden.insert(a.i);
query();
// cout << "\t" << old << " " << oldValue << endl;
if(oldValue == old) {
merge(i, a.i);
golden.insert(i);
golden.erase(a.i);
}
else if(oldValue > old) {
merge(NOT_ROYAL, i);
merge(ROYAL, a.i);
break;
}
else {
golden.erase(a.i);
golden.insert(i);
merge(ROYAL, i);
merge(NOT_ROYAL, a.i);
oldValue = old;
break;
}
}
}
for(int i = 0; i < nbArcs; i++)if(find(i) == find(ROYAL))cout << i << " ";cout<<endl;
for(int i : golden) sol.push_back(i);
return sol;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:127:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i = 0; i < nbArcs; i++)if(find(i) == find(ROYAL))cout << i << " ";cout<<endl;
^~~
simurgh.cpp:127:76: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i = 0; i < nbArcs; i++)if(find(i) == find(ROYAL))cout << i << " ";cout<<endl;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
888 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
888 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
888 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
888 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
888 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
