oj.uz

Submission #49482

# Submission time Handle Problem Language Result Execution time Memory
49482 2018-05-29T14:19:27 Z SpaimaCarpatilor Park (JOI17_park) C++17
77 / 100
 180 ms 2412 KB 
#include "park.h"
#include<bits/stdc++.h>
using namespace std;

int N, ap[1500], cc[1500];
vector < int > v[1500];

void addEdge (int S, int T)
{
    v[S].push_back (T);
    v[T].push_back (S);
}

void findPath (int S, int T, vector < int > possible)
{
    if (S > T)
        swap (S, T);
    int place[N];
    for (int i=0; i<N; i++)
        place[i] = 0;
    place[S] = place[T] = 1;
    if (Ask (S, T, place))
    {
        addEdge (S, T);
        return ;
    }
    int p = 0, u = possible.size () - 1, mij, ras = -1;
    while (p <= u)
    {
        mij = (p + u) >> 1;
        for (int i=0; i<=mij; i++)
            place[possible[i]] = 1;
        bool queryResult = Ask (S, T, place);
        for (int i=0; i<=mij; i++)
            place[possible[i]] = 0;
        if (queryResult) ras = possible[mij], u = mij - 1;
        else p = mij + 1;
    }
    ///ras is definitely on the path from S to T
    while (possible.back () != ras)
        possible.pop_back ();
    possible.pop_back ();
    findPath (S, ras, possible);
    findPath (ras, T, possible);
}

void Detect (int subtaskId, int nn)
{
    N = nn;
    int place[N];
    if (subtaskId == 1)
    {
        memset (place, 0, sizeof (place));
        for (int i=0; i<N; i++)
            for (int j=i + 1; j<N; j++)
            {
                place[i] = place[j] = 1;
                if (Ask (i, j, place))
                    Answer (i, j);
                place[i] = place[j] = 0;
            }
        return ;
    }
    for (int i=1; i<N; i++)
        if (v[i].empty ())
        {
            memset (ap, 0, sizeof (ap));
            int bfsLength = 1;
            cc[1] = 0, ap[0] = 1;
            for (int j=1; j<=bfsLength; j++)
                for (auto it : v[cc[j]])
                    if (ap[it] == 0)
                        ap[it] = 1, cc[++bfsLength] = it;
            int p = 1, u = bfsLength, mij, ras = 0;
            while (p <= u)
            {
                mij = (p + u) >> 1;
                for (int j=0; j<N; j++)
                    if (ap[j] == 0) place[j] = 1;
                    else place[j] = 0;
                for (int j=1; j<=mij; j++)
                    place[cc[j]] = 1;
                if (Ask (cc[1], i, place)) ras = mij, u = mij - 1;
                else p = mij + 1;
            }
            vector < int > others;
            for (int j=0; j<N; j++)
                if (ap[j] == 0 && j != i)
                    others.push_back (j);
            int node = cc[ras];///this one is the closest to i
            findPath (node, i, others);
        }
    for (int i=0; i<N; i++)
        for (auto j : v[i])
            if (i < j)
                Answer (i, j);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 464 KB Output is correct
3 Correct 9 ms 592 KB Output is correct
4 Correct 10 ms 592 KB Output is correct
5 Correct 10 ms 776 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 864 KB Output is correct
2 Correct 145 ms 864 KB Output is correct
3 Correct 123 ms 2412 KB Output is correct
4 Correct 40 ms 2412 KB Output is correct
5 Correct 34 ms 2412 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 2412 KB Output is correct
2 Correct 156 ms 2412 KB Output is correct
3 Correct 154 ms 2412 KB Output is correct
4 Correct 132 ms 2412 KB Output is correct
5 Correct 142 ms 2412 KB Output is correct
6 Correct 141 ms 2412 KB Output is correct
7 Correct 172 ms 2412 KB Output is correct
8 Correct 144 ms 2412 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2412 KB Output is correct
2 Correct 131 ms 2412 KB Output is correct
3 Correct 113 ms 2412 KB Output is correct
4 Correct 88 ms 2412 KB Output is correct
5 Correct 82 ms 2412 KB Output is correct
6 Correct 90 ms 2412 KB Output is correct
7 Correct 59 ms 2412 KB Output is correct
8 Correct 93 ms 2412 KB Output is correct
9 Correct 97 ms 2412 KB Output is correct
10 Correct 117 ms 2412 KB Output is correct
11 Correct 105 ms 2412 KB Output is correct
12 Correct 113 ms 2412 KB Output is correct
13 Correct 66 ms 2412 KB Output is correct
14 Correct 129 ms 2412 KB Output is correct
15 Correct 80 ms 2412 KB Output is correct
16 Correct 180 ms 2412 KB Output is correct
17 Correct 41 ms 2412 KB Output is correct
18 Correct 114 ms 2412 KB Output is correct
19 Correct 52 ms 2412 KB Output is correct
20 Correct 91 ms 2412 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 2412 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -