Submission #62642

#	Time	Username	Problem	Language	Result	Execution time	Memory
62642		SpaimaCarpatilor	Simurgh (IOI17_simurgh)	C++17	100 / 100	684 ms	24520 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;

int N, M, id[509][509], x[130009], y[130009], ans[130009], q[130009];
bool traversed[130009];
bool anyEdge[509][509];
vector < int > v[509], h[509];

namespace fixedSTfinder
{
    int ap[509], t[509], low[509], lev[509];
    bool ap2[509];
    void dfs (int nod)
    {
        ap[nod] = 2, low[nod] = nod;
        for (auto it : v[nod])
            if (ap[it] == 0)
                t[it] = nod, lev[it] = lev[nod] + 1,
                h[it].push_back (nod),
                h[nod].push_back (it),
                dfs (it);
            else
            if (ap[it] == 2 && t[nod] != it)
            {
                if (lev[it] < lev[low[nod]])
                    low[nod] = it;
            }
        ap[nod] = 1;
    }

    void findFixedST ()
    {
        t[0] = -1, dfs (0);
        for (int i=1; i<N; i++)
            if (low[i] != i)
            {
                int x = low[i], y = i;
                vector < int > currEdges, starterPack;
                memset (ap2, 0, sizeof (ap2));
                currEdges.push_back (id[x][y]);
                while (y != x)
                    currEdges.push_back (id[y][t[y]]),
                    ap2[y] = 1, y = t[y];
                bool anythingNew = 0;
                for (auto e : currEdges)
                    if (traversed[e] == 0)
                        anythingNew = 1;
                if (!anythingNew)
                    continue;
                for (int j=1; j<N; j++)
                    if (ap2[j] == 0)
                        starterPack.push_back (id[j][t[j]]);
                bool anyKnown = 0;
                int allS = 0, ma = 0, mi = N;
                for (int j=0; j<currEdges.size (); j++)
                {
                    vector < int > curr = starterPack;
                    for (int k=0; k<currEdges.size (); k++)
                        if (k != j)
                            curr.push_back (currEdges[k]);
                    if (traversed[currEdges[j]])
                    {
                        if (anyKnown == 0)
                        {
                            allS = ans[currEdges[j]] + count_common_roads (curr);
                            anyKnown = 1;
                        }
                        q[currEdges[j]] = allS - ans[currEdges[j]];
                    }
                    else q[currEdges[j]] = count_common_roads (curr);
                    mi = min (mi, q[currEdges[j]]);
                    ma = max (ma, q[currEdges[j]]);
                }
                if (mi == ma)
                {
                    for (auto e : currEdges)
                        ans[e] = 0;
                }
                else
                {
                    for (auto e : currEdges)
                        if (q[e] == mi)
                            ans[e] = 1;
                }
                for (auto e : currEdges)
                    traversed[e] = 1;
            }
        for (int i=1; i<N; i++)
            if (traversed[id[i][t[i]]] == 0)
                traversed[id[i][t[i]]] = 1,
                ans[id[i][t[i]]] = 1;///it's critical then
    }
}

namespace edgesFinderGivenFixedST
{
    bool ap[509];
    void dfs (int nod, int &currCost, vector < int > &curr)
    {
        ap[nod] = 1;
        for (auto it : h[nod])
            if (ap[it] == 0)
                curr.push_back (id[nod][it]),
                currCost += ans[id[nod][it]],
                dfs (it, currCost, curr);
    }

    void findEdges (int nod)
    {
        vector < int > possibleEdges;
        for (int i=0; i<N; i++)
            if (anyEdge[nod][i] && !traversed[id[nod][i]])
                possibleEdges.push_back (id[nod][i]),
                traversed[id[nod][i]] = 1;
        for (int l=0; l<possibleEdges.size (); l++)
        {
            int p = l, u = possibleEdges.size () - 1, ras = possibleEdges.size ();
            {
                int mij = possibleEdges.size () - 1, q = 0;
                vector < int > curr;
                memset (ap, 0, sizeof (ap)), ap[nod] = 1;
                for (int i=l; i<=mij; i++)
                {
                    int otherEnd = x[possibleEdges[i]] ^ y[possibleEdges[i]] ^ nod;
                    ap[otherEnd] = 1, curr.push_back (possibleEdges[i]);
                }
                dfs (nod, q, curr);
                for (int i=l; i<=mij; i++)
                {
                    int otherEnd = x[possibleEdges[i]] ^ y[possibleEdges[i]] ^ nod;
                    dfs (otherEnd, q, curr);
                }
                if (count_common_roads (curr) == q)
                    break;
            }
            while (p <= u)
            {
                int mij = (p + u) >> 1, q = 0;
                vector < int > curr;
                memset (ap, 0, sizeof (ap)), ap[nod] = 1;
                for (int i=l; i<=mij; i++)
                {
                    int otherEnd = x[possibleEdges[i]] ^ y[possibleEdges[i]] ^ nod;
                    ap[otherEnd] = 1, curr.push_back (possibleEdges[i]);
                }
                dfs (nod, q, curr);
                for (int i=l; i<=mij; i++)
                {
                    int otherEnd = x[possibleEdges[i]] ^ y[possibleEdges[i]] ^ nod;
                    dfs (otherEnd, q, curr);
                }
                if (count_common_roads (curr) > q) ras = mij, u = mij - 1;
                else p = mij + 1;
            }
            if (ras == possibleEdges.size ()) break;
            ans[possibleEdges[ras]] = 1, l = ras;
        }
    }
}

vector < int > find_roads (int nn, vector < int > uu, vector < int > vv)
{
    N = nn, M = uu.size ();
    for (int i=0; i<M; i++)
        anyEdge[uu[i]][vv[i]] = anyEdge[vv[i]][uu[i]] = 1,
        id[uu[i]][vv[i]] = id[vv[i]][uu[i]] = i,
        x[i] = uu[i], y[i] = vv[i],
        v[x[i]].push_back (y[i]),
        v[y[i]].push_back (x[i]);

    fixedSTfinder::findFixedST ();
    for (int i=0; i<N; i++)
        edgesFinderGivenFixedST::findEdges (i);

    vector < int > finalAns;
    for (int i=0; i<M; i++)
        if (ans[i])
            finalAns.push_back (i);
    return finalAns;
}

Compilation message (stderr)

simurgh.cpp: In function 'void fixedSTfinder::findFixedST()':
simurgh.cpp:56:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j=0; j<currEdges.size (); j++)
                               ~^~~~~~~~~~~~~~~~~~
simurgh.cpp:59:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int k=0; k<currEdges.size (); k++)
                                   ~^~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'void edgesFinderGivenFixedST::findEdges(int)':
simurgh.cpp:116:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int l=0; l<possibleEdges.size (); l++)
                       ~^~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:156:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (ras == possibleEdges.size ()) break;
                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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