Submission #619916

#	Time	Username	Problem	Language	Result	Execution time	Memory
619916		Ozy	Simurgh (IOI17_simurgh)	C++17	0 / 100	24 ms	3512 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 250
#define des first
#define id second

//gurpo reaal
int ufreal[MAX+2];
int greal;
vector<int> goldenway;

//grupo de prueba
int uf[MAX+2],vis[MAX+2],M[MAX+2];
int grupos;
vector<int> prueba,defaul,query,res;

//variables
int n,m;
vector<int> u,v;
vector<pair<int, int> > hijos[MAX+2];


int sube(int a, int uf[]) {
    if (uf[a] == a) return a;
    uf[a] = sube(uf[a],uf);
    return uf[a];
}

bool une(int a, int b, int uf[]) {

    a = sube(a,uf);
    b = sube(b,uf);

    if (a == b) return false;

    if (b < a) swap(a,b);
    uf[b] = a;
    return true;
}


std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
    n = N;
    swap(u,U);
    swap(v,V);
    m = u.size();

    rep(i,0,m-1) {
        hijos[u[i]].push_back({v[i],i});
        hijos[v[i]].push_back({u[i],i});
    }

    rep(i,0,n-1) ufreal[i] = i;
    greal = n;

    rep(act,0,n-1) {

        //si ya forma parte de algo continuo
        if (sube(act,ufreal) != act) continue;

        //borro todo
        rep(i,0,n-1) uf[i] =  ufreal[i];
        prueba.clear();
        if (!goldenway.empty()) for (auto g : goldenway) prueba.push_back(g);
        grupos = greal;

        rep(i,0,m-1) {
            if (u[i] == act || v[i] == act) continue;
            if (une(u[i],v[i],uf)) {
                grupos--;
                prueba.push_back(i);
            }
        }

        defaul.clear();
        res.clear();
        rep(i,0,n-1) {
            vis[i] = -1;
            M[i] = -1;
        }

        int k;
        for (auto h : hijos[act]) {
            k = sube(h.des,uf);
            if (vis[k] == -1) {
                vis[k] = h.id;
                defaul.push_back(h.id);
            }
        }

        int num;
        for (auto h : hijos[act]) {
            k = sube(h.des,uf);
            query.clear();
            for (auto x : prueba) query.push_back(x);
            for (auto d : defaul) {
                if (d == vis[k]) query.push_back(h.id);
                else query.push_back(d);
            }

            num = count_common_roads(query);
            M[k] = max(num , M[k]);
            res.push_back(num);
        }

        num = hijos[act].size();
        rep(i,0,num-1) {
            k = sube(hijos[act][i].des,uf);
            if (res[i] == M[k]) {
                une(act,hijos[act][i].des,ufreal);
                goldenway.push_back(hijos[act][i].id);
                greal--;
            }
        }

    }

    return goldenway;
}

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