Submission #1199689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199689		Aviansh	Simurgh (IOI17_simurgh)	C++20	13 / 100	15 ms	328 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);
        }
    }
    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;
    }
    for(int i = 0;i<(1<<m);i++){
        if(__builtin_popcount(i)!=n-1){
            continue;
        }
        dsu ds(n);
        vector<int>curr;
        for(int j = 0;j<m;j++){
            if(i&(1<<j)){
                if(!ds.unite(edges[j][0],edges[j][1])){
                    goto bad;
                }
                curr.push_back(j);
            }
        }
        if(count_common_roads(curr)==n-1){
            return curr;
        }
        bad:
            continue;
    }
    return ans;
}

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