Submission #397148

#	Time	Username	Problem	Language	Result	Execution time	Memory
397148		idk321	Simurgh (IOI17_simurgh)	C++11	13 / 100	23 ms	2880 KiB

simurgh

#include "simurgh.h"


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 240;
const int M = 28680;
vector<array<int, 2>> adj[N];
int n;
int m;

int in[N];
int up[N];
int timer;
bool done[N];
bool inRes[N];

void bridges(int node, int par, int pEdge)
{
    in[node] = ++timer;
    up[node] = in[node];

    for (auto next : adj[node])
    {
        if (next[0] == par) continue;
        if (in[next[0]] == 0)
        {
            bridges(next[0], node, next[1]);
            up[node] = min(up[node], up[next[0]]);
        } else
        {
            up[node] = min(up[node], up[next[0]]);
        }
    }

    if (par != -1 && up[node] == in[node])
    {
        done[pEdge] = true;
    }
}

int p[N];

int getRoot(int a)
{
    if (p[a] == a) return a;
    p[a] = getRoot(p[a]);
    return p[a];
}

void join(int a, int b)
{
    a = getRoot(a);
    b = getRoot(b);
    p[b] = a;
}


std::vector<int> find_roads(int XD, std::vector<int> u, std::vector<int> v) {
    n = XD;
    m = u.size();
    for (int i = 0; i < m; i++)
    {
        adj[u[i]].push_back({v[i], i});
        adj[v[i]].push_back({u[i], i});
    }

    bridges(0, -1, -1);

    vector<int> res;
    for (int i = 0; i < m; i++) if (done[i])
    {
         res.push_back(i);
         inRes[i] = true;
    }


    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            p[j] = j;
        }

        vector<int> gold;
        for (int i = 0; i < m; i++)
        {
            if (done[i])
            {
                 join(u[i], v[i]);
                 gold.push_back(i);
            }
        }
        for (int j = 0; j < m; j++)
        {
            if (u[j] != i && v[j] != i && getRoot(u[j]) != getRoot(v[j]))
            {
                join(u[j], v[j]);
                gold.push_back(j);
            }
        }

        int best = 0;

        for (auto next : adj[i])
        {
            if (inRes[next[1]] && !done[next[1]] && getRoot(i) != getRoot(next[0]))
            {
                gold.push_back(next[1]);
                //cout << gold.size() << endl;
                int quer = count_common_roads(gold);
                gold.pop_back();
                best = quer;
                break;
            }
        }

        vector<int> toAdd;
        for (auto next : adj[i])
        {
            if (inRes[next[1]]) continue;
            if (getRoot(i) != getRoot(next[0]))
            {
                gold.push_back(next[1]);
                //cout << gold.size() << endl;
                int quer = count_common_roads(gold);
                gold.pop_back();
                if (quer == best)
                {
                    toAdd.push_back(next[1]);
                } else if (quer > best)
                {
                    best = quer;
                    toAdd.clear();
                    toAdd.push_back(next[1]);
                }
            }
        }

        for (int edge : toAdd)
        {
            res.push_back(edge);
            inRes[edge] = true;
        }
    }



    return res;
}

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