제출 #1009278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009278		boris_mihov	Simurgh (IOI17_simurgh)	C++17	19 / 100	70 ms	4600 KiB

simurgh

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30