Submission #62615

#	Time	Username	Problem	Language	Result	Execution time	Memory
62615		SpaimaCarpatilor	Simurgh (IOI17_simurgh)	C++17	51 / 100	215 ms	8656 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];

namespace edgesFinder
{
    bool ap[509];
    vector < int > starterPack, currComp;
    void dfs (int nod)
    {
        ap[nod] = 1, currComp.push_back (nod);
        for (auto it : v[nod])
            if (ap[it] == 0)
                starterPack.push_back (id[nod][it]), dfs (it);
    }

    void findEdges (int nod)
    {
        memset (ap, 0, sizeof (ap)), ap[nod] = 1;
        starterPack.clear ();
        vector < vector < int > > currEdges;
        vector < int > representative;
        for (int i=0; i<N; i++)
            if (ap[i] == 0)
            {
                currComp.clear ();
                dfs (i);
                vector < int > curr;
                for (auto j : currComp)
                    if (anyEdge[nod][j])
                        curr.push_back (id[nod][j]);
                currEdges.push_back (curr);
                representative.push_back (curr[0]);
            }
        for (int i=0; i<currEdges.size (); i++)
            if (currEdges[i].size () == 1)
                traversed[representative[i]] = 1, ans[representative[i]] = 1;
            else
            {
                vector < int > curr = starterPack;
                for (int j=0; j<currEdges.size (); j++)
                    if (j != i)
                        curr.push_back (representative[j]);
                int maxi = -1;
                bool anyOther = 0;
                for (auto j : currEdges[i])
                    if (!traversed[j])
                    {
                        curr.push_back (j);
                        q[j] = count_common_roads (curr);
                        if (q[j] > maxi)
                            maxi = q[j];
                        curr.pop_back ();
                    }
                    else
                    if (traversed[j] == 1 && ans[j] == 1 && !anyOther)
                    {
                        anyOther = 1;
                        curr.push_back (j);
                        int currQ = count_common_roads (curr);
                        if (currQ > maxi)
                            maxi = currQ;
                        curr.pop_back ();
                    }
                for (auto j : currEdges[i])
                    if (!traversed[j])
                    {
                        traversed[j] = 1;
                        ans[j] = (maxi == q[j]);
                    }
            }
    }
};

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 + 1] = uu[i], y[i + 1] = vv[i],
        v[x[i + 1]].push_back (y[i + 1]),
        v[y[i + 1]].push_back (x[i + 1]);
    //bool isNew[100009];
    //memset (isNew, 0, sizeof (isNew));
    for (int i=0; i<N; i++)
    {
        edgesFinder::findEdges (i);
        /*printf ("added %d's edges\n", i);
        for (int j=0; j<M; j++)
            if (traversed[j] == 1 && isNew[j] == 0)
            {
                printf ("%d -> %d\n", j, ans[j]);
                isNew[j] = 1;
            }*/
    }
    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 edgesFinder::findEdges(int)':
simurgh.cpp:40:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<currEdges.size (); i++)
                       ~^~~~~~~~~~~~~~~~~~
simurgh.cpp:46:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j=0; j<currEdges.size (); j++)
                               ~^~~~~~~~~~~~~~~~~~

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