oj.uz

Submission #62642

# Submission time Handle Problem Language Result Execution time Memory
62642 2018-07-29T15:24:50 Z SpaimaCarpatilor Simurgh (IOI17_simurgh) C++17
100 / 100
 684 ms 24520 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], 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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 484 KB correct
3 Correct 3 ms 548 KB correct
4 Correct 2 ms 548 KB correct
5 Correct 2 ms 548 KB correct
6 Correct 3 ms 612 KB correct
7 Correct 2 ms 612 KB correct
8 Correct 2 ms 612 KB correct
9 Correct 3 ms 612 KB correct
10 Correct 3 ms 612 KB correct
11 Correct 2 ms 672 KB correct
12 Correct 3 ms 672 KB correct
13 Correct 2 ms 672 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 484 KB correct
3 Correct 3 ms 548 KB correct
4 Correct 2 ms 548 KB correct
5 Correct 2 ms 548 KB correct
6 Correct 3 ms 612 KB correct
7 Correct 2 ms 612 KB correct
8 Correct 2 ms 612 KB correct
9 Correct 3 ms 612 KB correct
10 Correct 3 ms 612 KB correct
11 Correct 2 ms 672 KB correct
12 Correct 3 ms 672 KB correct
13 Correct 2 ms 672 KB correct
14 Correct 4 ms 752 KB correct
15 Correct 5 ms 876 KB correct
16 Correct 5 ms 876 KB correct
17 Correct 6 ms 876 KB correct
18 Correct 4 ms 876 KB correct
19 Correct 5 ms 876 KB correct
20 Correct 4 ms 876 KB correct
21 Correct 5 ms 876 KB correct
22 Correct 4 ms 876 KB correct
23 Correct 4 ms 876 KB correct
24 Correct 4 ms 876 KB correct
25 Correct 3 ms 876 KB correct
26 Correct 4 ms 876 KB correct
27 Correct 5 ms 876 KB correct
28 Correct 3 ms 876 KB correct
29 Correct 3 ms 876 KB correct
30 Correct 4 ms 876 KB correct
31 Correct 5 ms 892 KB correct
32 Correct 6 ms 892 KB correct
33 Correct 4 ms 892 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 484 KB correct
3 Correct 3 ms 548 KB correct
4 Correct 2 ms 548 KB correct
5 Correct 2 ms 548 KB correct
6 Correct 3 ms 612 KB correct
7 Correct 2 ms 612 KB correct
8 Correct 2 ms 612 KB correct
9 Correct 3 ms 612 KB correct
10 Correct 3 ms 612 KB correct
11 Correct 2 ms 672 KB correct
12 Correct 3 ms 672 KB correct
13 Correct 2 ms 672 KB correct
14 Correct 4 ms 752 KB correct
15 Correct 5 ms 876 KB correct
16 Correct 5 ms 876 KB correct
17 Correct 6 ms 876 KB correct
18 Correct 4 ms 876 KB correct
19 Correct 5 ms 876 KB correct
20 Correct 4 ms 876 KB correct
21 Correct 5 ms 876 KB correct
22 Correct 4 ms 876 KB correct
23 Correct 4 ms 876 KB correct
24 Correct 4 ms 876 KB correct
25 Correct 3 ms 876 KB correct
26 Correct 4 ms 876 KB correct
27 Correct 5 ms 876 KB correct
28 Correct 3 ms 876 KB correct
29 Correct 3 ms 876 KB correct
30 Correct 4 ms 876 KB correct
31 Correct 5 ms 892 KB correct
32 Correct 6 ms 892 KB correct
33 Correct 4 ms 892 KB correct
34 Correct 76 ms 2472 KB correct
35 Correct 77 ms 2572 KB correct
36 Correct 58 ms 2572 KB correct
37 Correct 34 ms 2572 KB correct
38 Correct 88 ms 2572 KB correct
39 Correct 73 ms 2572 KB correct
40 Correct 72 ms 2572 KB correct
41 Correct 73 ms 2572 KB correct
42 Correct 76 ms 2572 KB correct
43 Correct 35 ms 2572 KB correct
44 Correct 31 ms 2572 KB correct
45 Correct 33 ms 2572 KB correct
46 Correct 27 ms 2572 KB correct
47 Correct 21 ms 2572 KB correct
48 Correct 9 ms 2572 KB correct
49 Correct 11 ms 2572 KB correct
50 Correct 19 ms 2572 KB correct
51 Correct 45 ms 2572 KB correct
52 Correct 34 ms 2572 KB correct
53 Correct 25 ms 2572 KB correct
54 Correct 45 ms 2572 KB correct
55 Correct 65 ms 2572 KB correct
56 Correct 64 ms 2572 KB correct
57 Correct 64 ms 2572 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2572 KB correct
2 Correct 2 ms 2572 KB correct
3 Correct 274 ms 5244 KB correct
4 Correct 472 ms 7980 KB correct
5 Correct 462 ms 8860 KB correct
6 Correct 490 ms 9916 KB correct
7 Correct 524 ms 10716 KB correct
8 Correct 506 ms 11872 KB correct
9 Correct 456 ms 12664 KB correct
10 Correct 684 ms 13576 KB correct
11 Correct 490 ms 14052 KB correct
12 Correct 445 ms 14060 KB correct
13 Correct 3 ms 14060 KB correct
14 Correct 394 ms 14200 KB correct
15 Correct 462 ms 14200 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 484 KB correct
3 Correct 3 ms 548 KB correct
4 Correct 2 ms 548 KB correct
5 Correct 2 ms 548 KB correct
6 Correct 3 ms 612 KB correct
7 Correct 2 ms 612 KB correct
8 Correct 2 ms 612 KB correct
9 Correct 3 ms 612 KB correct
10 Correct 3 ms 612 KB correct
11 Correct 2 ms 672 KB correct
12 Correct 3 ms 672 KB correct
13 Correct 2 ms 672 KB correct
14 Correct 4 ms 752 KB correct
15 Correct 5 ms 876 KB correct
16 Correct 5 ms 876 KB correct
17 Correct 6 ms 876 KB correct
18 Correct 4 ms 876 KB correct
19 Correct 5 ms 876 KB correct
20 Correct 4 ms 876 KB correct
21 Correct 5 ms 876 KB correct
22 Correct 4 ms 876 KB correct
23 Correct 4 ms 876 KB correct
24 Correct 4 ms 876 KB correct
25 Correct 3 ms 876 KB correct
26 Correct 4 ms 876 KB correct
27 Correct 5 ms 876 KB correct
28 Correct 3 ms 876 KB correct
29 Correct 3 ms 876 KB correct
30 Correct 4 ms 876 KB correct
31 Correct 5 ms 892 KB correct
32 Correct 6 ms 892 KB correct
33 Correct 4 ms 892 KB correct
34 Correct 76 ms 2472 KB correct
35 Correct 77 ms 2572 KB correct
36 Correct 58 ms 2572 KB correct
37 Correct 34 ms 2572 KB correct
38 Correct 88 ms 2572 KB correct
39 Correct 73 ms 2572 KB correct
40 Correct 72 ms 2572 KB correct
41 Correct 73 ms 2572 KB correct
42 Correct 76 ms 2572 KB correct
43 Correct 35 ms 2572 KB correct
44 Correct 31 ms 2572 KB correct
45 Correct 33 ms 2572 KB correct
46 Correct 27 ms 2572 KB correct
47 Correct 21 ms 2572 KB correct
48 Correct 9 ms 2572 KB correct
49 Correct 11 ms 2572 KB correct
50 Correct 19 ms 2572 KB correct
51 Correct 45 ms 2572 KB correct
52 Correct 34 ms 2572 KB correct
53 Correct 25 ms 2572 KB correct
54 Correct 45 ms 2572 KB correct
55 Correct 65 ms 2572 KB correct
56 Correct 64 ms 2572 KB correct
57 Correct 64 ms 2572 KB correct
58 Correct 4 ms 2572 KB correct
59 Correct 2 ms 2572 KB correct
60 Correct 274 ms 5244 KB correct
61 Correct 472 ms 7980 KB correct
62 Correct 462 ms 8860 KB correct
63 Correct 490 ms 9916 KB correct
64 Correct 524 ms 10716 KB correct
65 Correct 506 ms 11872 KB correct
66 Correct 456 ms 12664 KB correct
67 Correct 684 ms 13576 KB correct
68 Correct 490 ms 14052 KB correct
69 Correct 445 ms 14060 KB correct
70 Correct 3 ms 14060 KB correct
71 Correct 394 ms 14200 KB correct
72 Correct 462 ms 14200 KB correct
73 Correct 2 ms 14200 KB correct
74 Correct 461 ms 14264 KB correct
75 Correct 524 ms 14940 KB correct
76 Correct 261 ms 14940 KB correct
77 Correct 449 ms 16344 KB correct
78 Correct 415 ms 17284 KB correct
79 Correct 416 ms 18200 KB correct
80 Correct 471 ms 19164 KB correct
81 Correct 444 ms 19292 KB correct
82 Correct 501 ms 20688 KB correct
83 Correct 363 ms 20688 KB correct
84 Correct 183 ms 20688 KB correct
85 Correct 237 ms 20688 KB correct
86 Correct 142 ms 20688 KB correct
87 Correct 132 ms 20688 KB correct
88 Correct 123 ms 20688 KB correct
89 Correct 110 ms 20688 KB correct
90 Correct 111 ms 20688 KB correct
91 Correct 41 ms 20688 KB correct
92 Correct 15 ms 20688 KB correct
93 Correct 179 ms 21540 KB correct
94 Correct 124 ms 21540 KB correct
95 Correct 119 ms 21540 KB correct
96 Correct 122 ms 21540 KB correct
97 Correct 90 ms 21540 KB correct
98 Correct 114 ms 21540 KB correct
99 Correct 132 ms 21540 KB correct
100 Correct 63 ms 21540 KB correct
101 Correct 19 ms 21540 KB correct
102 Correct 331 ms 23116 KB correct
103 Correct 297 ms 23452 KB correct
104 Correct 321 ms 23840 KB correct
105 Correct 331 ms 24520 KB correct