/*
Time: O(N^4)
Queries: Q <= 30000
Score: 30/100
*/
#include <bits/stdc++.h>
using namespace std;
#include "simurgh.h"
//int count_common_roads(vector<int> r);
struct Arc {
int u, v, i;
};
int nbNodes, nbArcs;
vector<Arc> arcs;
vector<Arc> adj[501];
map<pair<int, int>, int> idx;
bool vu[501];
set<int> roads;
int oldValue = -1;
int query() {
vector<int> quer;
for(int i : roads) quer.push_back(i);
return oldValue = count_common_roads(quer);
}
void traverse(int u, int i) {
if(vu[u]) return;
vu[u] = 1;
if(i != -1) roads.insert(i);
for(Arc a : adj[u])
if(!vu[a.v])
traverse(a.v, a.i);
}
void buildTree() {
for(int i = 0; i < nbNodes; i++) vu[i] = false;
traverse(0, -1);
}
int parent[501*250];
int find(int x) {
return x == parent[x] ? x : (parent[x] = find(parent[x]));
}
void merge(int x, int y) {
parent[find(x)] = find(y);
}
const int ROYAL = 500*250+1;
const int BAD = 500*250+2;
bool good(int i) {
return find(i) == find(ROYAL);
}
bool bad(int i) {
return find(i) == find(BAD);
}
void init() {
for(int i = 0; i < nbArcs; i++) parent[i] = i;
parent[ROYAL] = ROYAL;
parent[BAD] = BAD;
}
vector<int> path, curr;
bool found=0;
void dfs(int u, int target, int p) {
if(u == target) {
found=1;
path = curr;
}
if(found) return;
for(Arc a : adj[u]) {
if(!roads.count(a.i) or a.v == p) continue;
curr.push_back(a.i);
dfs(a.v, target, u);
curr.pop_back();
}
}
vector<int> findCycle(int u, int v) {
path.clear(), curr.clear(), found=0;
dfs(u, v, -1);
return path;
}
map<pair<int, int>, int> memo;
int Query(int id1, int id2) {
if(memo.count({id1, id2})) {
oldValue += memo[{id1, id2}];
return oldValue;
}
else {
int queee(-1);
if(find(id1) == find(id2)) queee = oldValue;
else queee = query();
int tmp = oldValue;
memo[{id1, id2}] = memo[{id2, id1}] = queee - tmp;
return queee;
}
}
int rev[501*250];
int devient(int x){return x==rev[x]?x:(rev[x]=devient(rev[x]));}
void fusion(int x, int y){rev[devient(x)]=devient(y);}
vector<int> act;
vector<int> Path[501][501];
void Dfs(int u, int p, int anc) {
if(vu[u])return;
Path[anc][u] = act;
for(Arc a : adj[u]) {
if(!roads.count(a.i) or a.v == p) continue;
act.push_back(a.i);
Dfs(a.v, u, anc);
act.pop_back();
}
}
void initTree() {
for(int i = 0; i < nbArcs; i++) rev[i] = i;
for(int i = 0; i < nbNodes; i++) {
for(int j = 0; j < nbNodes; j++) vu[j] = 0;
act.clear();
Dfs(i, -1, i);
}
}
vector<int> findCycle2(int u, int v) {
vector<int> cycle;set<int>Cycle;
for(int i : Path[u][v]) {
if(roads.count(devient(i))) {
Cycle.insert(devient(i));
}
}
for(int i:Cycle)cycle.push_back(i);
return cycle;
}
void findSol() {
init();
initTree();
for(Arc a : arcs) {
if(roads.count(a.i)) continue;
if(bad(a.i)) continue;
int i = a.i;
int u = a.u;
int v = a.v;
vector<int> cycle = findCycle2(u, v); //this line has to be optimized to O(n)
for(int id : cycle) {
int old = oldValue;
roads.insert(i);
roads.erase(id);
int nouv = Query(i, id);
if(nouv > old) {
merge(ROYAL, i);
merge(BAD, id);
fusion(id, i);
break;
}
else if(nouv == old) {
merge(id, i);
roads.insert(id);
roads.erase(i);
oldValue = old;
}
else {
merge(id, ROYAL);
merge(i, BAD);
roads.insert(id);
roads.erase(i);
oldValue = old;
break;
}
}
}
for(int i = 0; i < nbArcs; i++) if(bad(i)) roads.erase(i); else if(good(i)) roads.insert(i);
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
nbNodes = n;
nbArcs = (int)u.size();
arcs.clear();
for(int i = 0; i < nbArcs; i++) {
arcs.push_back({u[i], v[i], i});
adj[u[i]].push_back({u[i], v[i], i});
adj[v[i]].push_back({v[i], u[i], i});
}
vector<int> ans;
buildTree();
query();
findSol();
for(int i : roads) ans.push_back(i);
return ans;
}
/*
bool GOLDEN[501*250];
int count_common_roads(vector<int> r) {
int cnt(0);
for(int i:r)if(GOLDEN[i])cnt++;
return cnt;
}
int main() {
int T=1;
while(T--){
int n, m;cin>>n>>m;
vector<int>u(m), v(m);
for(int i=0;i<m;i++){
cin>>u[i]>>v[i];
}
for(int i=0;i<m;i++)GOLDEN[i]=0;
for(int i=0;i<n-1;i++){int s;cin>>s;GOLDEN[s]=1;}
vector<int> sol = find_roads(n, u, v);
for(int i : sol) {
cout << i << " ";
}
cout << endl;
}
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
6264 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
6264 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
6264 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6372 KB |
correct |
| 2 |
Incorrect |
7 ms |
6372 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
6264 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
