#include "bits/stdc++.h"
#include "simurgh.h"
using namespace std;
set<pair<int,int>> edges , bad;
map<pair<int,int>,int> mp;
set<int> adj[100001],ne[100001];
map<int,int> good;
int vis[100001];
void dfs(int i){
vis[i] = 1;
for(auto j:adj[i]){
if(!vis[j]){
dfs(j);
edges.insert({i,j});
ne[i].insert(j);
ne[j].insert(i);
}else{
bad.insert({i,j});
}
}
}
vector<int> v , an;
void go(int i,int pr,int targ){
v.push_back(i);
if(i==targ){
an = v;
}
for(auto j:ne[i]){
if(j==pr)continue;
go(j,i,targ);
}
v.pop_back();
}
int qu(){
vector<int> r;
for(auto j:edges){
r.push_back(mp[j]);
}
return count_common_roads(r);
}
mt19937 rnd;
vector<int> find_roads(int n,vector<int> u,vector<int> v){
rnd.seed(n);
edges.clear();
for(int i = 0;i<n;i++){
adj[i].clear();
vis[i] =0;
}
for(int i = 0;i<u.size();i++){
adj[u[i]].insert(v[i]);
adj[v[i]].insert(u[i]);
mp[{u[i],v[i]}] = i;
mp[{v[i],u[i]}] = i;
}
set<pair<int,int>> s;
dfs(0);
int cost = qu();
map<int,int> goo;
map<pair<int,int>,int> compared;
while(cost<n-1){
int x = rnd()%bad.size();
auto it = bad.begin();
while(x--)it++;
pair<int,int> p = (*it);
bad.erase(it);
v.clear();an.clear();
go(p.first,-1,p.second);
x = 0;
while(x<int(an.size())-1){
if(goo[mp[make_pair(an[x],an[x+1])]]||compared[{mp[p],mp[make_pair(an[x],an[x+1])]}]){
x =rnd()%(an.size()-1);
}else{
break;
}
}
if(x==int(an.size())-1)continue;
pair<int,int> P = make_pair(an[x],an[x+1]);
compared[{mp[p],mp[P]}] = compared[{mp[P],mp[p]}] = 1;
auto IT = edges.lower_bound(P);
if(IT==edges.end()||(*IT)!=P){
swap(P.first,P.second);
IT = edges.lower_bound(P);
}
edges.erase(IT);
edges.insert(p);
int ncost = qu();
if(ncost>cost){
ne[P.first].erase(P.second);
ne[P.second].erase(P.first);
ne[p.first].insert(p.second);
ne[p.second].insert(p.first);
cost = ncost;
goo[mp[p]] = 1;
continue;
}else if(ncost<cost){
edges.erase(edges.lower_bound(p));
edges.insert(P);
goo[mp[P]] = 1;
}else{
ne[P.first].erase(P.second);
ne[P.second].erase(P.first);
ne[p.first].insert(p.second);
ne[p.second].insert(p.first);
bad.insert(P);
}
}
vector<int> r;
for(auto i:edges){
r.push_back(mp[i]);
}
return r;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i = 0;i<u.size();i++){
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3056 ms |
9820 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3056 ms |
9820 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3056 ms |
9820 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
10076 KB |
correct |
2 |
Execution timed out |
3082 ms |
10076 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3056 ms |
9820 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |