Submission #1047366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047366		Ahmed57	Simurgh (IOI17_simurgh)	C++17	30 / 100	3088 ms	37124 KiB

simurgh

#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++;
            }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 (stderr)

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++){
      |                   ~^~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30