oj.uz

Submission #62625

# Submission time Handle Problem Language Result Execution time Memory
62625 2018-07-29T12:32:24 Z SpaimaCarpatilor Simurgh (IOI17_simurgh) C++17
70 / 100
 285 ms 18088 KB 
#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 > h[509];
void findFixedSTcompleteGraph ()
{
    vector < int > curr;
    for (int i=1; i<N - 1; i++)
        curr.push_back (id[i][i + 1]);
    int maxi = -1;
    for (int i=1; i<N; i++)
    {
        curr.push_back (id[0][i]);
        q[i] = count_common_roads (curr);
        if (q[i] > maxi)
            maxi = q[i];
        curr.pop_back ();
    }
    for (int i=1; i<N; i++)
        traversed[id[0][i]] = 1,
        ans[id[0][i]] = (q[i] == maxi),
        h[0].push_back (i),
        h[i].push_back (0);
}

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 ();
            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]);
    if (N <= 240)
    {
        for (int i=0; i<N; i++)
            edgesFinder::findEdges (i);
    }
    else
    {
        //bool isNew[100009];
        //memset (isNew, 0, sizeof (isNew));
        findFixedSTcompleteGraph ();
        for (int i=0; i<N; i++)
        {
            edgesFinderGivenFixedST::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

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++)
                               ~^~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'void edgesFinderGivenFixedST::findEdges(int)':
simurgh.cpp:122:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int l=0; l<possibleEdges.size (); l++)
                       ~^~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:144:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (ras == possibleEdges.size ()) break;
                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 376 KB correct
3 Correct 3 ms 416 KB correct
4 Correct 2 ms 420 KB correct
5 Correct 3 ms 452 KB correct
6 Correct 2 ms 508 KB correct
7 Correct 3 ms 508 KB correct
8 Correct 3 ms 536 KB correct
9 Correct 3 ms 544 KB correct
10 Correct 2 ms 592 KB correct
11 Correct 2 ms 592 KB correct
12 Correct 3 ms 620 KB correct
13 Correct 3 ms 620 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 376 KB correct
3 Correct 3 ms 416 KB correct
4 Correct 2 ms 420 KB correct
5 Correct 3 ms 452 KB correct
6 Correct 2 ms 508 KB correct
7 Correct 3 ms 508 KB correct
8 Correct 3 ms 536 KB correct
9 Correct 3 ms 544 KB correct
10 Correct 2 ms 592 KB correct
11 Correct 2 ms 592 KB correct
12 Correct 3 ms 620 KB correct
13 Correct 3 ms 620 KB correct
14 Correct 4 ms 748 KB correct
15 Correct 5 ms 748 KB correct
16 Correct 5 ms 748 KB correct
17 Correct 4 ms 748 KB correct
18 Correct 1 ms 748 KB correct
19 Correct 4 ms 748 KB correct
20 Correct 4 ms 748 KB correct
21 Correct 4 ms 748 KB correct
22 Correct 5 ms 748 KB correct
23 Correct 4 ms 748 KB correct
24 Correct 4 ms 748 KB correct
25 Correct 2 ms 748 KB correct
26 Correct 4 ms 748 KB correct
27 Correct 4 ms 748 KB correct
28 Correct 3 ms 796 KB correct
29 Correct 3 ms 796 KB correct
30 Correct 4 ms 796 KB correct
31 Correct 5 ms 876 KB correct
32 Correct 4 ms 876 KB correct
33 Correct 4 ms 876 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 376 KB correct
3 Correct 3 ms 416 KB correct
4 Correct 2 ms 420 KB correct
5 Correct 3 ms 452 KB correct
6 Correct 2 ms 508 KB correct
7 Correct 3 ms 508 KB correct
8 Correct 3 ms 536 KB correct
9 Correct 3 ms 544 KB correct
10 Correct 2 ms 592 KB correct
11 Correct 2 ms 592 KB correct
12 Correct 3 ms 620 KB correct
13 Correct 3 ms 620 KB correct
14 Correct 4 ms 748 KB correct
15 Correct 5 ms 748 KB correct
16 Correct 5 ms 748 KB correct
17 Correct 4 ms 748 KB correct
18 Correct 1 ms 748 KB correct
19 Correct 4 ms 748 KB correct
20 Correct 4 ms 748 KB correct
21 Correct 4 ms 748 KB correct
22 Correct 5 ms 748 KB correct
23 Correct 4 ms 748 KB correct
24 Correct 4 ms 748 KB correct
25 Correct 2 ms 748 KB correct
26 Correct 4 ms 748 KB correct
27 Correct 4 ms 748 KB correct
28 Correct 3 ms 796 KB correct
29 Correct 3 ms 796 KB correct
30 Correct 4 ms 796 KB correct
31 Correct 5 ms 876 KB correct
32 Correct 4 ms 876 KB correct
33 Correct 4 ms 876 KB correct
34 Correct 160 ms 2428 KB correct
35 Correct 184 ms 2428 KB correct
36 Correct 103 ms 2428 KB correct
37 Correct 14 ms 2428 KB correct
38 Correct 159 ms 2428 KB correct
39 Correct 157 ms 2428 KB correct
40 Correct 112 ms 2428 KB correct
41 Correct 179 ms 2468 KB correct
42 Correct 148 ms 2468 KB correct
43 Correct 79 ms 2468 KB correct
44 Correct 65 ms 2468 KB correct
45 Correct 76 ms 2468 KB correct
46 Correct 60 ms 2468 KB correct
47 Correct 29 ms 2468 KB correct
48 Correct 7 ms 2468 KB correct
49 Correct 14 ms 2468 KB correct
50 Correct 31 ms 2468 KB correct
51 Correct 83 ms 2468 KB correct
52 Correct 76 ms 2468 KB correct
53 Correct 59 ms 2468 KB correct
54 Correct 86 ms 2468 KB correct
55 Correct 82 ms 2468 KB correct
56 Correct 108 ms 2468 KB correct
57 Correct 82 ms 2468 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2468 KB correct
2 Correct 2 ms 2468 KB correct
3 Correct 147 ms 4732 KB correct
4 Correct 231 ms 7548 KB correct
5 Correct 279 ms 8524 KB correct
6 Correct 261 ms 9480 KB correct
7 Correct 260 ms 10572 KB correct
8 Correct 221 ms 11288 KB correct
9 Correct 281 ms 12412 KB correct
10 Correct 243 ms 13148 KB correct
11 Correct 248 ms 14076 KB correct
12 Correct 264 ms 15004 KB correct
13 Correct 1 ms 15004 KB correct
14 Correct 273 ms 16036 KB correct
15 Correct 285 ms 16992 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 376 KB correct
3 Correct 3 ms 416 KB correct
4 Correct 2 ms 420 KB correct
5 Correct 3 ms 452 KB correct
6 Correct 2 ms 508 KB correct
7 Correct 3 ms 508 KB correct
8 Correct 3 ms 536 KB correct
9 Correct 3 ms 544 KB correct
10 Correct 2 ms 592 KB correct
11 Correct 2 ms 592 KB correct
12 Correct 3 ms 620 KB correct
13 Correct 3 ms 620 KB correct
14 Correct 4 ms 748 KB correct
15 Correct 5 ms 748 KB correct
16 Correct 5 ms 748 KB correct
17 Correct 4 ms 748 KB correct
18 Correct 1 ms 748 KB correct
19 Correct 4 ms 748 KB correct
20 Correct 4 ms 748 KB correct
21 Correct 4 ms 748 KB correct
22 Correct 5 ms 748 KB correct
23 Correct 4 ms 748 KB correct
24 Correct 4 ms 748 KB correct
25 Correct 2 ms 748 KB correct
26 Correct 4 ms 748 KB correct
27 Correct 4 ms 748 KB correct
28 Correct 3 ms 796 KB correct
29 Correct 3 ms 796 KB correct
30 Correct 4 ms 796 KB correct
31 Correct 5 ms 876 KB correct
32 Correct 4 ms 876 KB correct
33 Correct 4 ms 876 KB correct
34 Correct 160 ms 2428 KB correct
35 Correct 184 ms 2428 KB correct
36 Correct 103 ms 2428 KB correct
37 Correct 14 ms 2428 KB correct
38 Correct 159 ms 2428 KB correct
39 Correct 157 ms 2428 KB correct
40 Correct 112 ms 2428 KB correct
41 Correct 179 ms 2468 KB correct
42 Correct 148 ms 2468 KB correct
43 Correct 79 ms 2468 KB correct
44 Correct 65 ms 2468 KB correct
45 Correct 76 ms 2468 KB correct
46 Correct 60 ms 2468 KB correct
47 Correct 29 ms 2468 KB correct
48 Correct 7 ms 2468 KB correct
49 Correct 14 ms 2468 KB correct
50 Correct 31 ms 2468 KB correct
51 Correct 83 ms 2468 KB correct
52 Correct 76 ms 2468 KB correct
53 Correct 59 ms 2468 KB correct
54 Correct 86 ms 2468 KB correct
55 Correct 82 ms 2468 KB correct
56 Correct 108 ms 2468 KB correct
57 Correct 82 ms 2468 KB correct
58 Correct 3 ms 2468 KB correct
59 Correct 2 ms 2468 KB correct
60 Correct 147 ms 4732 KB correct
61 Correct 231 ms 7548 KB correct
62 Correct 279 ms 8524 KB correct
63 Correct 261 ms 9480 KB correct
64 Correct 260 ms 10572 KB correct
65 Correct 221 ms 11288 KB correct
66 Correct 281 ms 12412 KB correct
67 Correct 243 ms 13148 KB correct
68 Correct 248 ms 14076 KB correct
69 Correct 264 ms 15004 KB correct
70 Correct 1 ms 15004 KB correct
71 Correct 273 ms 16036 KB correct
72 Correct 285 ms 16992 KB correct
73 Correct 3 ms 16992 KB correct
74 Correct 256 ms 18068 KB correct
75 Incorrect 47 ms 18088 KB WA in grader: NO
76 Halted 0 ms 0 KB -