제출 #619940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619940		Ozy	Simurgh (IOI17_simurgh)	C++17	30 / 100	176 ms	3548 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) {

        //borro todo
        rep(i,0,n-1) uf[i] = i;
        prueba.clear();

        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);
            }
        }

        //debbug
        //debug(act);
        //for (auto p : prueba) cout << p << ' ';
        //cout << endl;

        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]) {
                if (une(act,hijos[act][i].des,ufreal)) {
                    goldenway.push_back(hijos[act][i].id);
                    greal--;
                }
            }
        }

    }

    return goldenway;
}

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