Submission #1199607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199607		Aviansh	Simurgh (IOI17_simurgh)	C++20	0 / 100	3094 ms	5332 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;


struct dsu{
    vector<int>root;
    vector<int>siz;
    dsu(int n){
        root=vector<int>(n);
        iota(root.begin(),root.end(),0);
        siz=vector<int>(n,1);
    }
    bool unite(int x, int y){
        x=findRoot(x);
        y=findRoot(y);
        if(x==y)
            return 0;
        if(siz[x]<siz[y]){
            swap(x,y);
        }
        siz[x]+=siz[y];
        root[y]=x;
        return 1;
    }
    int findRoot(int x){
        if(x==root[x])
            return x;
        return root[x]=findRoot(root[x]);
    }
};

void dfs(int st, vector<array<int,2>>(&g)[], set<int>(&ban), bool vis[]){
    vis[st]=1;
    for(array<int,2>e:g[st]){
        if(vis[e[0]]||ban.find(e[1])!=ban.end())
            continue;
        dfs(e[0],g,ban,vis);
    }
}

int compCount(vector<array<int,2>>(&g)[], set<int>(&ban), int n){
    int ans = 0;
    bool vis[n];
    fill(vis,vis+n,0);
    for(int i = 0;i<n;i++){
        if(!vis[i]){
            ans++;
            dfs(i,g,ban,vis);
        }
    }
    return ans;
}

vector<int> makeTree(vector<array<int,2>>edges, set<int>(&ban), vector<int>req, int n){
    //assuming req is without cycle
    int m = edges.size();
    dsu ds(n);
    vector<int>ans;
    for(int i : req){
        ans.push_back(i);
        assert(ds.unite(edges[i][0],edges[i][1]));
    }
    for(int i = 0;i<m;i++){
        if(ban.find(i)==ban.end()&&ds.unite(edges[i][0],edges[i][1])){
            ans.push_back(i);
        }
    }
    assert(ans.size()==n-1);
    return ans;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    vector<int>ans;
    int m = u.size();
    //each edge: {v,edge_index}
    vector<array<int,2>>g[n];
    vector<array<int,2>>edges(m);
    for(int i = 0;i<m;i++){
        int a = u[i];
        int b = v[i];
        g[a].push_back({b,i});
        g[b].push_back({a,i});
        edges[i][0]=a;
        edges[i][1]=b;
    }
    dsu eds(m);
    for(int i = 0;i<m;i++){
        set<int>ban;
        ban.insert(i);
        if(compCount(g,ban,n)>1){
            ans.push_back(i);
            continue;
        }
        set<int>temp;
        vector<int>req;
        req.push_back(i);
        vector<int>defTree = makeTree(edges,temp,req,n);
        //required edge is first edge in defTree
        int a1 = count_common_roads(defTree);
        defTree.erase(defTree.begin());
        vector<int>newTree = makeTree(edges,ban,defTree,n);
        int a2 = count_common_roads(newTree);
        if(a1>a2){
            ans.push_back(i);
            //cout << "adding: " << i << "\n";
        }
        else if(a1==a2){
            eds.unite(i,newTree[n-2]);
            //cout << "united: " << i << " " << newTree[n-2] << "\n";
        }
    }
    vector<int>sets[m];
    for(int i = 0;i<m;i++){
        sets[eds.findRoot(i)].push_back(i);
    }
    set<int>searable;
    for(int i : ans){
        searable.insert(i);
        for(int j : sets[eds.findRoot(i)]){
            searable.insert(j);
        }
    }
    ans.clear();
    for(int i : searable){
        ans.push_back(i);
    }
    assert(ans.size()==n-1);
    return ans;
}

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