| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1047364 | Ahmed57 | Simurgh (IOI17_simurgh) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 count_common_roads(vector<int> x){
int cnt = 0;
for(int i = 0;i<x.size();i++){
if(good[x[i]])cnt++;
}
return cnt;
}
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++;
}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;
}
int main(){
good[0] = good[1] = good[5] = 1;
for(auto i:find_roads(4, {0, 0, 0, 1, 1, 2},{1, 2, 3, 2, 3, 3})){
cout<<i<<" ";
}
}