oj.uz

Submission #1009278

# Submission time Handle Problem Language Result Execution time Memory
1009278 2024-06-27T10:51:26 Z boris_mihov Simurgh (IOI17_simurgh) C++17
19 / 100
 70 ms 4600 KB 
#include "simurgh.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>

typedef long long llong;
const int MAXN = 500 + 12;

int idx[MAXN][MAXN];
bool isIn[MAXN][MAXN];
std::vector <int> find_roads(int n, std::vector <int> u, std::vector <int> v) 
{ 
    memset(idx, -1, sizeof(idx));
    for (int i = 0 ; i < u.size() ; ++i)
    {
        idx[u[i]][v[i]] = i;
        idx[v[i]][u[i]] = i;
    }

    std::vector <int> atFirst;
    for (int i = 1 ; i < n ; ++i)
    {
        atFirst.push_back(idx[0][i]);
    }

    if (count_common_roads(atFirst) == n - 1)
    {
        return atFirst;
    }

    int res = MAXN;
    std::vector <int> answers;
    for (int i = 1 ; i < n ; ++i)
    {
        std::vector <int> tree;
        for (int j = 1 ; j + 1 < n ; ++j)
        {
            tree.push_back(idx[j][j + 1]);
        }

        tree.push_back(idx[0][i]);
        answers.push_back(count_common_roads(tree));
        res = std::min(res, answers.back());
    }

    int cntGlobalOnes = 0;
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        isIn[0][i + 1] = (answers[i] > res);
        cntGlobalOnes += isIn[0][i + 1];
    }

    for (int u = 1 ; u < n ; ++u)
    {
        int cntCurrentOnes = 0;
        std::vector <int> newTree;
        for (int i = 1 ; i <= u ; ++i)
        {
            newTree.push_back(idx[0][i]);
            cntCurrentOnes += isIn[0][i];
        }

        for (int i = u + 1 ; i < n ; ++i)
        {
            newTree.push_back(idx[u][i]);
        }

        int currentlyFound = 0;
        int lastOne = u;
        int toBeFound = (count_common_roads(newTree) - cntCurrentOnes);
        while (toBeFound--)
        {
            int l = lastOne, r = n, mid;
            while (l < r - 1)
            {
                mid = (l + r) >> 1;
                std::vector <int> currentTree;
                int binaryOnes = 0;
                for (int i = 1 ; i <= u ; ++i)
                {
                    currentTree.push_back(idx[0][i]);
                    binaryOnes += isIn[0][i];
                }

                for (int i = u + 1 ; i <= mid ; ++i)
                {
                    currentTree.push_back(idx[u][i]);
                }

                for (int i = mid + 1 ; i < n ; ++i)
                {
                    currentTree.push_back(idx[0][i]);
                    binaryOnes += isIn[0][i];
                }

                int ones = count_common_roads(currentTree) - binaryOnes;
                if (ones <= currentlyFound) l = mid;
                else r = mid;
            }

            assert(r < n);
            isIn[u][r] = true;
            lastOne = r;
            currentlyFound++;
        } 
    }

    std::vector <int> sol;
    for (int i = 0 ; i < n ; ++i)
    {
        for (int j = i + 1 ; j < n ; ++j)
        {
            if (isIn[i][j])
            {
                sol.push_back(idx[i][j]);
            }
        }
    }

    return sol;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:17:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0 ; i < u.size() ; ++i)
      |                      ~~^~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB correct
2 Correct 1 ms 1432 KB correct
3 Correct 1 ms 1372 KB correct
4 Incorrect 1 ms 1372 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB correct
2 Correct 1 ms 1432 KB correct
3 Correct 1 ms 1372 KB correct
4 Incorrect 1 ms 1372 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB correct
2 Correct 1 ms 1432 KB correct
3 Correct 1 ms 1372 KB correct
4 Incorrect 1 ms 1372 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB correct
2 Correct 1 ms 1372 KB correct
3 Correct 34 ms 3416 KB correct
4 Correct 50 ms 4440 KB correct
5 Correct 59 ms 4376 KB correct
6 Correct 45 ms 4412 KB correct
7 Correct 50 ms 4436 KB correct
8 Correct 70 ms 4436 KB correct
9 Correct 44 ms 4432 KB correct
10 Correct 49 ms 4448 KB correct
11 Correct 45 ms 4600 KB correct
12 Correct 47 ms 4464 KB correct
13 Correct 1 ms 1372 KB correct
14 Correct 50 ms 4396 KB correct
15 Correct 45 ms 4444 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB correct
2 Correct 1 ms 1432 KB correct
3 Correct 1 ms 1372 KB correct
4 Incorrect 1 ms 1372 KB WA in grader: NO
5 Halted 0 ms 0 KB -