#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
struct DSU{
int path[505];
void init(int n){for (int i=0;i<=n;i++) path[i] = i;}
int find(int s){
if (path[s]==s) return s;
return path[s] = find(path[s]);
}
bool merge(int s, int v){
int x = find(s), y = find(v);
if (x==y) return 0;
path[x] = y;
return 1;
}
}dsu;
int adj[505][505], n, val[100100], dfs_chk[100100], cntq;
bool visited[505];
vector<int> U, V, DV, E, F, adj2[505];
void dfs(int s){
visited[s] = 1;
for (int i=0;i<n;i++) if (!visited[i] && adj[s][i]!=-1){
DV.push_back(adj[s][i]);
dfs_chk[adj[s][i]] = 1;
adj2[s].push_back(i);
adj2[i].push_back(s);
dfs(i);
}
}
bool find_path(int s, int e){
if (s==e) return 1;
visited[s] = 1;
for (auto &v:adj2[s]) if (!visited[v]){
E.push_back(adj[s][v]);
if (find_path(v, e)) return 1;
E.pop_back();
}
return 0;
}
int calc(int p, int l, int r){
if (l>r) return 0;
//printf("calc: %d %d %d\n", p, l, r);
dsu.init(n);
vector<int> Q;
for (int i=l;i<=r;i++) if (adj[p][i]!=-1){
Q.push_back(adj[p][i]);
dsu.merge(p, i);
}
int cnt = 0;
for (auto &t:DV) if (dsu.merge(U[t], V[t])){
Q.push_back(t);
if (val[t]==1) cnt++;
}
cntq++;
return count_common_roads(Q) - cnt;
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
cntq = 0;
if (N==2) return {0};
n = N;
U = u, V = v;
fill(adj[0], adj[504]+505, -1);
for (int i=0;i<(int)u.size();i++){
adj[u[i]][v[i]] = i;
adj[v[i]][u[i]] = i;
}
fill(val, val+100100, -1);
fill(dfs_chk, dfs_chk+100100, 0);
fill(visited, visited+505, 0);
DV.clear();
for (int i=0;i<505;i++) adj2[i].clear();
dfs(0);
int cnt0 = count_common_roads(DV);
//for (auto &x:DV) printf("%d ", x);
//printf("\n");
cntq++;
for (int i=0;i<(int)u.size();i++) if (!dfs_chk[i]){
E.clear();
F.clear();
fill(visited, visited+n, 0);
assert(find_path(u[i], v[i]));
//printf("%d: ", i);
//for (auto &x:E) printf("%d ", x);
//printf("\n");
bool flag = 0, flag2 = 0;;
for (auto &t:E) if (val[t]!=-1) flag = 1;
for (auto &t:E) if (val[t]==-1) flag2 = 1;
if (!flag2) continue;
vector<int> Q = DV;
int flag3 = -1, val2 = -1;
int prvE = i;
for (auto &t:E){
if (flag3!=-1 && val[t]!=-1) {F.push_back(INF); continue;}
for (auto iter = Q.begin();iter!=Q.end();iter++) if (*iter==t) {Q.erase(iter); break;}
Q.push_back(prvE);
F.push_back(count_common_roads(Q));
cntq++;
prvE = t;
if (val[t]!=-1) flag3 = t, val2 = F.back();
}
if (!flag){
int mn = min(*min_element(F.begin(), F.end()), cnt0);
int mx = max(*max_element(F.begin(), F.end()), cnt0);
for (int i=0;i<(int)F.size();i++){
if (mn==mx) val[E[i]] = 0;
else if (F[i]==mn) val[E[i]] = 1;
else val[E[i]] = 0;
}
}
else{
assert(flag3!=-1);
if (val[flag3]==0) val2--;
//printf(" %d %d\n", flag3, val2);
for (int i=0;i<(int)F.size();i++){
//printf(" %d", F[i]);
if (F[i]==val2) val[E[i]] = 1;
else if (F[i]!=INF) val[E[i]] = 0;
}
}
//for (int i=0;i<(int)u.size();i++) printf("%d ", val[i]);
//printf("\n");
}
//printf("YES\n");
for (int i=0;i<(int)DV.size();i++) if (val[DV[i]]==-1) val[DV[i]] = 1;
//for (int i=0;i<(int)u.size();i++) printf("%d ", val[i]);
//printf("\n");
vector<int> ans;
for (int i=0;i<n;i++){
int prv = i;
while(calc(i, prv+1, n-1) > 0){
//printf(" %d %d\n", i, prv);
int l = prv+1, r = n-1;
while(r-l > 0){
int m = (l+r)>>1;
if (calc(i, l, m) > 0) r = m;
else l = m+1;
}
ans.push_back(adj[i][l]);
prv = l;
}
}
//printf("ans: ");
//for (auto &x:ans) printf("%d ", x);
//printf("\n");
//printf("YES:simurgh\n");
if ((int)ans.size()!=n-1) exit(1);
assert(count_common_roads(ans)==n-1);
printf("%d\n", cntq);
assert(cntq<=n*12);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1996 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1996 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1996 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
correct |
| 2 |
Incorrect |
1 ms |
1996 KB |
Security Violation! Don't try to hack |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1996 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
