Submission #835459

#	Time	Username	Problem	Language	Result	Execution time	Memory
835459		jasmin	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	252 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;

void find_articpoints(int v, int p, vector<vector<pair<int,int> > >& adi, vector<int>& h, vector<int>& minh, vector<bool>& art){
    minh[v] = h[v];

    for(auto [u, ind]: adi[v]){
        if(u==p) continue;

        if(h[u] < h[v]){
            minh[v] = min(minh[v], h[u]);
            continue;
        }

        h[u] = h[v]+1;
        find_articpoints(u, v, adi, h, minh, art);

        if(minh[u] > h[v]){
            art[v] = true;
        }

        minh[v] = min(minh[v], minh[u]);
    }
}

struct ufind{
    vector<int> chef;

    void init(int n){
        chef.assign(n, 0);
        iota(chef.begin(), chef.end(), 0);
    }

    int find(int a){
        if(chef[a]==a) return a;
        return chef[a] = find(chef[a]);
    }

    bool unite(int a, int b){
        a=find(a); b=find(b);
        if(a==b) return false;

        chef[b]=a;
        return true;
    }
};

int ask(set<int>& r){
    vector<int> edges;
    for(auto e: r){
        edges.push_back(e);
    }

    return count_common_roads(edges);
}

vector<int> find_roads(int n, vector<int> a, vector<int> b) {
	/*vector<int> r(n - 1);
	for(int i = 0; i < n - 1; i++)
		r[i] = i;
	int common = count_common_roads(r);
	if(common == n - 1)
		return r;
	r[0] = n - 1;
	return r;*/
    int m=a.size();
    
    vector<vector<pair<int,int> > > adi(n);
    for(int i=0; i<m; i++){

        adi[a[i]].push_back({b[i], i});
        adi[b[i]].push_back({a[i], i});
    }

    //find articulation points
    vector<bool> art(n, false);
    vector<int> h(n, 0);
    vector<int> minh(n, 0);
    find_articpoints(0, -1, adi, h, minh, art);

    //for every non articulation point
    //build spanningtree without that point with unionfind
    //try every edge
    set<int> golden;
    ufind uf;
    uf.init(n);

    set<int> r;
    for(int v=0; v<n; v++){
        if(art[v]) continue;

        //spanning tree without v
        for(auto e: golden){
            if(a[e]==v || b[e]==v) continue;

            assert(uf.unite(a[e], b[e]));
            r.insert(e);
        }
        for(int i=0; i<m; i++){
            if(a[i]==v || b[i]==v) continue;

            if(uf.unite(a[i], b[i])){
                r.insert(i);
            }
        }

        //ask edges
        vector<int> val;
        int maxi=0;
        for(auto [u, ind]: adi[v]){
            r.insert(ind);

            int x=ask(r);
            val.push_back(x);
            maxi = max(maxi, x);

            r.erase(ind);
        }

        //golden edges
        int s=adi[v].size();
        for(int i=0; i<s; i++){

            if(val[i] == maxi){
                golden.insert(adi[v][i].second);
            }
        }
    }

    //for every articulation point for every component
    // build spanning tree without connection point-component
    // try every edge

    vector<int> ans;
    for(auto e: golden){
        ans.push_back(e);
    }
    return ans;
}

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