oj.uz

Submission #49481

# Submission time Handle Problem Language Result Execution time Memory
49481 2018-05-29T14:17:48 Z SpaimaCarpatilor Park (JOI17_park) C++17
67 / 100
 232 ms 2508 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];
    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
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 872 KB Output is correct
2 Correct 158 ms 872 KB Output is correct
3 Correct 124 ms 2508 KB Output is correct
4 Correct 41 ms 2508 KB Output is correct
5 Correct 37 ms 2508 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 2508 KB Output is correct
2 Correct 232 ms 2508 KB Output is correct
3 Correct 188 ms 2508 KB Output is correct
4 Correct 112 ms 2508 KB Output is correct
5 Correct 141 ms 2508 KB Output is correct
6 Correct 123 ms 2508 KB Output is correct
7 Correct 123 ms 2508 KB Output is correct
8 Correct 137 ms 2508 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2508 KB Output is correct
2 Correct 113 ms 2508 KB Output is correct
3 Correct 115 ms 2508 KB Output is correct
4 Correct 86 ms 2508 KB Output is correct
5 Correct 85 ms 2508 KB Output is correct
6 Correct 81 ms 2508 KB Output is correct
7 Correct 54 ms 2508 KB Output is correct
8 Correct 97 ms 2508 KB Output is correct
9 Correct 86 ms 2508 KB Output is correct
10 Correct 142 ms 2508 KB Output is correct
11 Correct 91 ms 2508 KB Output is correct
12 Correct 105 ms 2508 KB Output is correct
13 Correct 46 ms 2508 KB Output is correct
14 Correct 110 ms 2508 KB Output is correct
15 Correct 55 ms 2508 KB Output is correct
16 Correct 136 ms 2508 KB Output is correct
17 Correct 43 ms 2508 KB Output is correct
18 Correct 112 ms 2508 KB Output is correct
19 Correct 50 ms 2508 KB Output is correct
20 Correct 90 ms 2508 KB Output is correct

Subtask #5
0 / 23.0

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